Distributed assembly permutation flowshop scheduling problem based on IIGA
-
摘要: 针对分布式装配置换流水车间调度问题，提出一种改进的迭代贪婪算法进行求解。首先，以最小化总流经时间为优化目标建立数学模型，提出一种改进的迭代贪婪算法，采用结合CDS（campbell dudek smith）和NEH（nawaz-enscore-ham）的启发式方法以生成较高质量的初始解，提高种群的多样性；其次，针对可重构产品与作业设计破坏和重构过程，将移除的序列插入指定位置，采用本地搜索策略获得新的解决方案；最后，通过不同规模的仿真实验对本文所提算法与其他四种智能算法进行对比，实验结果表明改进的迭代贪婪算法在求解分布式装配置换流水车间调度方面具有高效性和稳定性。Abstract: In this paper, an improved iterative greedy algorithm is proposed to solve the distributed assembly Permutation Flowshop Scheduling Problem. First, establish a mathematical model with the optimization goal of minimizing the total elapsed time and an improved iterative greedy algorithm is proposed, which uses a heuristic method combining CDS (campbell dudek smith) and NEH (nawaz-enscore-ham) to generate higher-quality initial solutions and improve population diversity; Secondly, design the destruction and reconstruction process for reconfigurable products and jobs, insert the removed sequence into the specified position, and use the local search strategy to obtain new solutions; Finally, the algorithm proposed in this paper is compared with other four intelligent algorithms through simulation experiments of different scales. The experimental results show that the improved iterative greedy algorithm has high efficiency and stability in solving distributed assembly replacement flow shop scheduling.
-
表 2 各算法ARD结果对比
Number n×m×f×s CMA HBBO HDIWO gILS IIGA ARD 运行时间/s ARD 运行时间/s ARD 运行时间/s ARD 运行时间/s ARD 运行时间/s 1 100×5×4×30 0.19 87.56 0.15 78.32 0.09 73.60 0.06 55.36 0.04 54.66 2 100×5×4×40 0.53 90.32 0.48 85.63 0.32 83.22 0.28 79.50 0.18 75.98 3 100×5×4×50 0.60 98.52 0.50 89.50 0.36 83.55 0.32 74.20 0.21 76.25 4 100×5×6×30 0.12 85.63 0.08 76.55 0.05 70.65 0.04 58.50 0.02 53.85 5 100×5×6×40 0.36 80.22 0.31 75.60 0.23 80.62 0.19 62.54 0.10 59.70 6 100×5×6×50 0.17 87.32 0.13 81.10 0.11 76.11 0.08 66.58 0.02 62.46 7 100×5×8×30 0.07 75.63 0.05 73.55 0.03 69.60 0.02 60.10 0.00 57.20 8 100×5×8×40 0.13 77.66 0.09 72.24 0.06 68.50 0.04 65.32 0.04 55.35 9 100×5×8×50 0.15 71.50 0.12 72.66 0.09 65.20 0.05 59.11 0.01 59.40 10 100×10×4×30 0.42 185.56 0.36 177.69 0.15 179.43 0.11 140.20 0.09 133.86 11 100×10×4×40 0.75 189.66 0.69 187.40 0.35 155.38 0.30 136.27 0.12 122.56 12 100×10×4×50 0.84 185.66 0.78 184.25 0.50 167.50 0.45 139.85 0.12 135.74 13 100×10×6×30 0.31 187.25 0.31 177.60 0.11 159.66 0.08 129.40 0.06 130.20 14 100×10×6×40 0.35 189.50 0.33 176.20 0.21 171.50 0.16 132.50 0.09 130.41 15 100×10×6×50 0.41 186.49 0.37 174.55 0.33 165.48 0.30 133.70 0.11 128.60 16 100×10×8×30 0.07 178.55 0.07 174.69 0.05 168.25 0.04 135.30 0.02 130.22 17 100×10×8×40 0.16 183.66 0.13 179.50 0.07 163.54 0.05 140.87 0.03 135.26 18 100×10×8×50 0.53 190.65 0.48 172.14 0.42 171.52 0.33 156.50 0.13 148.55 
下载: 导出CSV
-
[1] Sara H, Rubén R, Carlos A R. The distributed assembly permutation flowshop scheduling problem[J]. International Journal of Production Research, 2013, 51(17): 5292-5308. doi: 10.1080/00207543.2013.807955 [2] Lin J, Wang Z J, Li X D. A backtracking search hyper-heuristic for the distributed assembly flow-shop scheduling problem[J]. Swarm and Evolutionary Computation, 2017, 36: 124-135. doi: 10.1016/j.swevo.2017.04.007 [3] Pan Q K, Gao L, Li X Y, et al. Effective constructive heuristics and meta-heuristics for the distributed assembly permutation flowshop scheduling problem[J]. Applied Soft Computing Journal, 2019, 81: 105492. doi: 10.1016/j.asoc.2019.105492 [4] 黄佳琳, 张丫丫, 顾幸生. 基于改进生物地理学优化算法的分布式装配置换流水车间调度问题[J]. 华东理工大学学报:自然科学版, 2020, 46(6): 758-769. doi: 10.14135/j.cnki.1006-3080.20190828001 [5] Fernandez-Viagas V, Perez-Gonzalez P, Framinan J M. The distributed permutation flow shop to minimise the total flowtime[J]. Computers & Industrial Engineering, 2018, 118: 464-477. [6] Pan Q K, Gao L, Wang L, et al. Effective heuristics and metaheuristics to minimize total flowtime for the distributed permutation flowshop problem[J]. Expert Systems With Applications, 2019, 124: 309-324. doi: 10.1016/j.eswa.2019.01.062 [7] Sang H Y, Pan Q K, Li J Q, et al. Effective invasive weed optimization algorithms for distributed assembly permutation flowshop problem with total flowtime criterion[J]. Swarm and Evolutionary Computation, 2019, 44: 64-73. doi: 10.1016/j.swevo.2018.12.001 [8] 张梓琪, 钱斌, 胡蓉, 等. 基于多维EDA算法的低碳分布式装配流水车间调度[J/OL]. 控制与决策: 1-10[2022-03-11]. https://doi.org/ 10.13195/j.kzyjc.2020.1475. [9] Jacobs L W, Brusco M J. A local-search heuristic for large set-covering problems[J]. Naval Research Logistics, 1995, 42(7): 1129–1140. [10] Lin S W, Ying K C, Huang C Y Minimising makespan in distributed permutation flowshops using a modified iterated greedy algorithm[J]. International Journal of Production Research, 2013, 51(16): 5029–5038. [11] Fernandez-Viagas V, Framinan J M. A bounded-searchiterated greedy algorithm for the distributed permutationflowshop scheduling problem[J]. International Journal ofProduction Research, 2015, 53(4): 1111-1123. doi: 10.1080/00207543.2014.948578 [12] Huang Y Y, Pan Q K, Huang J P, et al. An improved iterated greedy algorithm for the distributed assembly permutation flowshop scheduling problem[J]. Computers & Industrial Engineering, 2021, 152: 107021. [13] 钱斌, 刘荻飞, 胡蓉, 等. 混合迭代贪婪算法求解准时生产分布式流水线调度问题[J/OL]. 控制与决策: 1-10[2021-10-05]. https://doi.org/ 10.13195/j.kzyjc.2021.0426. [14] 姚康, 唐秋华, 张子凯, 等. 考虑序列相关调整时间的多目标置换流水车间调度算法[J]. 武汉科技大学学报, 2021, 44(6): 452-458. [15] WANG S Y, WANG L. An estimation of distribution algorithm-based memetic algorithm for the distributed assembly permutation flow-shop scheduling problem[J]. IEEE Transactions on Systems, Man, and Cybernetics:Systems, 2016, 46(1): 139-149. doi: 10.1109/TSMC.2015.2416127 [16] Deng J, Wang L, Wang S, et al. A competitive memetic algorithm for the distributed two-stage assembly flow-shop scheduling problem[J]. International Journal of Production Research, 2016, 54(12): 3561-3577. doi: 10.1080/00207543.2015.1084063 [17] Huang Y Y, Pan Q, Hu X L, et al. An iterated local search algorithm for distributed assembly permutation flowshop problem[C].2020 39th Chinese Control Conference (CCC). IEEE, 2020: 1548-1552. -
下载:
点击查看大图
图(9) / 表(2)
计量
- 文章访问数: 130
- HTML全文浏览量: 20
- PDF下载量: 21
- 被引次数: 0
