Design of FMS scheduling algorithm based on genetic algorithm
-
摘要: 在柔性制造系统中,合理的排产可以缩短各加工任务的完成时间,提高设备利用率。针对柔性制造系统中的复杂作业车间调度问题,以超期作业数、总超期时间、机床综合负载率、最大机床负载率及作业完工时间作为排产算法的性能指标,利用遗传算法找到最优排产方案。将染色体设计为工序基因链和设备基因链,通过交叉、变异和选择等流程提高染色体的多样性和染色体对调度问题的鲁棒性。通过调整算法相关参数,研究不同参数设置对各项排产算法的性能指标的影响。本研究为基于遗传算法的排产算法的设计及优化提供一种参考。Abstract: In the flexible manufacturing system, a reasonable production scheduling can shorten the completion time of each processing task and improve the utilization rate of equipment. In order to solve the complex job shop scheduling problem in the flexible manufacturing system, the number of overdue jobs, total overdue time, comprehensive load rate of machine tool, maximum load rate of machine tool and job completion time are taken as the performance indicators of scheduling algorithm. The genetic algorithm is used to find the optimal scheduling scheme. The chromosomes are designed as process gene chains and equipment gene chains, and the diversity of chromosomes and the robustness of chromosomes to scheduling problems are improved through crossing, mutation, selection and other processes. By adjusting the relevant parameters of the algorithm, the influences of different parameter settings on the performance indicators of each scheduling algorithm are studied. This study provides a reference for the design and optimization of scheduling algorithm based on the genetic algorithm.
-
Key words:
- flexible manufacturing system /
- production scheduling /
- genetic algorithm /
- chromosome /
- code
-
表 1 工序加工时间
工序 加工设备 M1 M2 M3 M4 M5 M6 M7 M8 b11 5 3 5 3 3 0 10 9 b12 10 0 5 8 3 9 9 6 b13 0 10 0 5 6 2 4 5 b14 0 0 0 0 0 0 0 0 b21 5 7 3 9 8 0 9 0 b22 0 8 5 2 6 7 10 9 b23 0 10 0 5 6 4 1 7 b24 10 8 9 6 4 7 0 0 b31 10 0 0 7 6 5 2 4 b32 0 10 6 4 8 9 10 0 b33 1 4 5 6 0 10 0 7 b34 0 0 0 0 0 0 0 0 b41 3 1 6 5 9 7 8 4 b42 12 11 7 8 10 5 6 9 b43 4 6 2 10 3 9 5 7 b44 0 0 0 0 0 0 0 0 b51 3 6 7 8 9 0 10 0 b52 10 0 7 4 9 8 6 0 b53 0 9 8 7 4 2 6 0 b54 11 9 6 7 5 3 6 0 b61 6 7 1 4 6 9 0 10 b62 11 0 9 9 9 7 6 4 b63 10 5 9 10 11 0 10 0 b64 0 0 0 0 0 0 0 0 b71 5 4 2 6 7 0 10 0 b72 0 9 0 9 11 9 10 5 b73 0 8 9 3 8 6 0 10 b74 0 0 0 0 0 0 0 0 b81 2 8 5 9 0 6 0 10 b82 7 4 7 8 9 0 10 0 b83 9 9 0 8 5 6 7 1 b84 9 0 3 7 1 5 8 0 表 2 实验结果对比
性能指标 第1种方案 第2种方案 第3种方案 作业完工时间/h 17 14 16 超期作业数 3 0 0 总超期时间/h 1 0 0 最大机床负载率/(%) 82 100 75 机床综合负载率/(%) 71 84 73 -
[1] 罗小峰, 胡莹, 余翔. 基于多目标多约束条件下排产算法设计与应用[J]. 制造技术与机床, 2022(4): 159-164. doi: 10.19287/j.mtmt.1005-2402.2022.04.026 [2] Zuo X Q, Mo H W, Wu J P. A robust scheduling method based on a multi-objective immune algorithm[J]. Information Sciences, 2009, 179(19): 3359-3369. doi: 10.1016/j.ins.2009.06.003 [3] Sun J H, Zhang G H, Lu J, et al. A hybrid many-objective evolutionary algorithm for flexible job-shop scheduling problem with transportation and setup times[J]. Computers & Operations Research, 2021, 132: 105263. [4] Caldeira R H, Gnanavelbabu A. Solving the flexible job shop scheduling problem using an improved Jaya algorithm[J]. Computers & Industrial Engineering, 2019, 137: 106064. [5] Shen X N, Han Y, Fu J Z. Robustness measures and robust scheduling for multi-objective stochastic flexible job shop scheduling problems[J]. Soft Computing, 2017, 21(21): 6531-6554. doi: 10.1007/s00500-016-2245-4 [6] 葛显龙, 王伟鑫, 李顺勇. 智能算法及应用[M]. 成都: 西南交通大学出版社, 2017. [7] 王小梅, 任伟娜, 吴琼宇. 基于遗传算法的柔性冲压车间生产调度多目标优化[J]. 锻压技术, 2021, 46(10): 203-209. doi: 10.13330/j.issn.1000-3940.2021.10.032 [8] 黄振国. 基于混合遗传算法的柔性车间动态实时调度研究[D]. 廊坊: 北华航天工业学院, 2022. [9] 陈金广, 马玲叶, 马丽. 求解作业车间调度问题的改进遗传算法[J]. 计算机系统应用, 2021, 30(5): 190-195. doi: 10.15888/j.cnki.csa.007921 [10] 屈新怀, 王娇, 丁必荣, 等. 贪婪初始种群的遗传算法求解柔性作业车间调度[J]. 合肥工业大学学报: 自然科学版, 2021, 44(9): 1153-1156, 1171.