Improved genetic algorithm for flexible flow shop scheduling
-
摘要: 针对最小化最大完工时间的柔性流水车间调度问题，文章提出了多目标选择的改进的遗传算法（MTGA），设计了针对该问题的一维的编码与解码方法，采用对立的方法进行种群的初始化。针对遗传算法，交叉操作进行整个工序的交叉向最优解靠拢加快了算法的收敛速度，变异操作中对所有的工序操作顺序进行整体变异，选择操作将种群分成多份做到向多个较优解靠拢，扩大了算法的搜索范围，降低了陷入局部最优的概率，并应用了两套交叉和变异概率增加算法灵活性。通过多个已有算法进行对比验证了算法的有效性。Abstract: Aiming at the flexible flow shop scheduling problem that minimizes the maximum completion time, this paper proposes an improved genetic algorithm bases on multiple target of selection(MTGA). A one-dimensional encoding and decoding method for this problem is designed, and an opposing method is used to initialize the population. For the genetic algorithm, the crossover operation of the whole process is closer to the optimal solution, which accelerates the convergence speed of the algorithm, the overall variation of the operation sequence of all processes in the mutation operation, and the selection operation divides the population into multiple parts to achieve multiple optimal solutions, which increases the search range of the algorithm and reduces the probability of falling into the local optimal. Two sets of crossover and variation probabilities are applied to increase the flexibility of the algorithm. The effectiveness of the algorithm is verified by comparison with multiple existing algorithms.
-
表 1 工作时间
工件 工序 S1 S2 S3 S4 S5 S6 S7 S8 S9 J1 61 77 82 17 104 96 56 58 29 J2 89 28 29 52 103 98 45 76 36 J3 55 103 58 89 5 10 21 16 87 J4 66 31 61 60 35 83 62 56 48 J5 66 84 62 77 59 60 49 62 15 J6 39 51 83 75 95 101 69 165 91 J7 80 80 36 77 53 97 15 48 91 J8 45 96 92 58 35 28 67 47 42 J9 72 60 48 35 68 71 84 36 47 J10 75 63 28 94 48 29 57 61 12 
下载: 导出CSV
表 2 运算结果
序号 算法名称 MTGA NSAGA CAPSO WOA- LFDE GGA ex1 920 919 928 932 921 ex2 923 934 922 934 923 ex3 919 945 919 926 922 ex4 923 931 937 932 931 ex5 919 940 940 923 921 ex6 935 933 938 920 926 ex7 922 934 935 939 929 ex8 920 932 926 923 922 ex9 923 932 948 924 919 ex10 919 926 932 933 932
下载: 导出CSV
表 4 机器数量类型汇总
索引 机器数量 1 33 133 2 13 333 3 33 233 4 3 333 133 333 5 1 333 333 333 6 3 333 233 333
下载: 导出CSV
表 5 大规模实验结果
exp MTGA NSAGA CAPSO WOA-LFDE GGA $ {{C}}_{\rm{a}\rm{v}\rm{e}} $(Std) $ {{C}}_{\rm{m}\rm{i}\rm{n}} $ $ {{C}}_{\rm{a}\rm{v}\rm{e}} $(Std) $ {{C}}_{\rm{m}\rm{i}\rm{n}} $ $ {{C}}_{\rm{a}\rm{v}\rm{e}} $(Std) $ {{C}}_{\rm{m}\rm{i}\rm{n}} $ $ {{C}}_{\rm{a}\rm{v}\rm{e}} $(Std) $ {{C}}_{\rm{m}\rm{i}\rm{n}} $ $ {{C}}_{\rm{a}\rm{v}\rm{e}} $(Std) $ {{C}}_{\rm{m}\rm{i}\rm{n}} $ 10-5-1 588(0) 588 588(0.4) 588 589(2.7) 588 589(1.4) 588 588(0) 588 10-5-2 581(0) 581 581(0) 581 581(0) 581 581(0) 581 581(0) 581 10-5-3 401(6.7) 393 418(17) 415 413(3.9) 406 416(1.2) 416 406(8.8) 397 15-5-1 843(1.2) 843 851(1.7) 848 848(2.9) 845 847(4.9) 843 846(1.0) 845 15-5-2 685(0) 685 685(0) 685 685(1.2) 685 685(0) 685 685(0) 685 15-5-3 497(6.6) 492 519(5.0) 514 511(6.0) 505 518(2.2) 517 506(7.0) 502 15-10-4 1119(0.5) 1119 1134(5.7) 1127 1145(7.8) 1137 1132(8.2) 1122 1130(9.1) 1122 15-10-5 1087(0) 1087 1087(0) 1087 1089(2.8) 1087 1087(0) 1087 1087(0) 1087 15-10-6 830(9.1) 822 868(7.8) 859 858(16.7) 838 840(9.6) 843 840(9.0) 828 20-10-4 1166(2.3) 1164 1183(9.4) 1171 1199(17.7) 1190 1185(10.4) 1175 1171(11.9) 1165 20-10-5 1205(1.0) 1204 1215(6.6) 1206 1220(1.2) 1220 1223(10.0) 1206 1210(7.1) 1204 20-10-6 918(18.3) 877 957(8.5) 940 945(7.3) 936 941(12.9) 916 925(10.9) 907
下载: 导出CSV
-
[1] Chen H,Fang Z,Zhong C. Research on hybrid flow-shop scheduling based on improved genetic algorithm[C]. IEEE 18th Conference on Industrial Electronics and Applications (ICIEA),2023:1315-1320. [2] Liao C J. An approach using particle swarm optimization and bottleneck heuristic to solve hybrid flow shop scheduling problem[J]. Applied Soft Computing,2012,12(6):1755-1764. doi: 10.1016/j.asoc.2012.01.011 [3] Li M,Wang G G,Yu H. Sorting-based discrete artificial bee colony algorithm for solving fuzzy hybrid flow shop green scheduling problem[J]. Mathematics,2021,9(18):22-50. [4] Chen N L,Xie N M. An elite genetic algorithm for flexible job shop scheduling problem with extracted grey processing time[J]. Applied Soft Computing,2022,131:109783. doi: 10.1016/j.asoc.2022.109783 [5] Bao T,Yan H. Improved genetic algorithm for production scheduling in machine tool manufacturing plants[C]. 2023 IEEE 3rd International Conference on Information Technology Big Data and Artificial Intelligence (ICIBA),2023:910-915. [6] 杨森,刘新平,李克文. 基于自适应遗传算法的改进及实现[J]. 计算机与数字工程,2022,50(8):1647-1651. doi: 10.3969/j.issn.1672-9722.2022.08.004 [7] Shao W S,Shao Z,Pi D. Multi-objective evolutionary algorithm based on multiple neighborhoods local search for multi-objective distributed hybrid flow shop scheduling problem[J]. Expert Systems with Applications,2021,183:115453. doi: 10.1016/j.eswa.2021.115453 [8] Rubén Ruiz,José Antonio Vázquez-Rodríguez. The hybrid flow shop scheduling problem[J]. European Journal of Operational Research,2010,205(1):1-18. doi: 10.1016/j.ejor.2009.09.024 [9] Chen H,Fang Z,Zhong C. Research on hybrid flow-shop scheduling based on improved genetic algorithm[C]. 2023 IEEE 18th Conference on Industrial Electronics and Applications (ICIEA),2023:1315-1320. [10] 宋存利. 求解混合流水车间调度的改进贪婪遗传算法[J]. 系统工程与电子技术,2019,41(5):1079-1086. doi: 10.3969/j.issn.1001-506X.2019.05.21 [11] Duan Y,Chen N,Chang L,et al. CAPSO:Chaos Adaptive Particle Swarm Optimization Algorithm[C]. IEEE Access,2022,10:29393-29405. [12] Liu M,Yao X F. Hybrid whale optimization algorithm enhanced with Lévy flight and differrential evolution for job shop scheduling problems[J]. Applied Soft Computing,2020,87:105954. doi: 10.1016/j.asoc.2019.105954 [13] 田野. 粒子群优化算法及其应用研究[D]. 长春:吉林大学,2011. [14] Carlier J,Néron E. An exact method for solving the multiprocessor flowshop[J]. RAIRO - Operations Research,2000,34(1):1-25. -
下载:
点击查看大图
图(13) / 表(5)
计量
- 文章访问数: 40
- HTML全文浏览量: 9
- PDF下载量: 7
- 被引次数: 0
