Design and application of scheduling algorithm based on multi-objective and multi- constraint
-
摘要: 针对机加企业实际生产中面临的双工位、相邻设备和委外工序等多约束条件下的多目标生产排程问题,分析排程所需满足的各生产要素,建立最优化生产排程数学模型,提出动态交叉变异算子改进遗传算法,在以三段式编码为基础的传统排程算法中引入分子和裂变分子,利用染色体偏移,提高排程紧凑性的同时加快算法收敛速度,得出加权系数优化后的排产结果,最后通过算例求解并运用于实际生产中,大大提高生产排程效率。Abstract: Aiming at the multi-objective production scheduling problem faced by machining enterprises under multi-constraint conditions such as dual-station, adjacent equipment and out-of-command process, the production factors required for scheduling are analyzed, and the mathematical model of optimal production scheduling is established. An improved genetic algorithm based on dynamic crossover and mutation operator is proposed. Molecular and fission molecules are introduced into the traditional scheduling algorithm based on three-stage coding. Chromosome offset is used to improve the compactness of scheduling and accelerate the convergence speed of algorithm. The scheduling results optimized by weighting coefficient are obtained. Finally, an example is solved and applied to actual production, which greatly improves the efficiency of production scheduling.
-
Key words:
- multiple constraints /
- multiple objectives /
- genetic algorithm /
- chromosome offset
-
表 1 机加排程问题信息
排产要素 生产排
程方案订单时间段
工序时间段
设备时间段
人员时间段
零件加工时段订单 工序 设备 双工位 排班 产能 人员 表 2 工序可选设备
工艺路线 工序 可选设备 GY-01169 01 01-016/01-017/01-018/01-019 02 10-017/10-018/10-028/10-029/10-036/
10-037/10-038/10-039GY-01152 01 02-016 02 01-022/01-058/10-023/10-063 03 01-022 04 10-019/10-020/10-024/10-025/10-026 05 06-009/06-010/06-012/06-013/06-014/06-015 06 04-006 GY-05584 01 01-016/01-017/01-018/01-019 02 01-016/01-017/01-018/01-019 03 06-009/06-010/06-012/06-013/06-014/06-015 04 04-006 GY-01167 01 01-016/01-017/01-018/01-019 02 01-016/01-017/01-018/01-019 03 06-009/06-010/06-012/06-013/06-014/06-015 04 04-006 GY-01163 01 10-005/10-017/10-018/10-028/10-029/10-036/
10-037/10-038/10-039GY-01165 01 10-017/10-018/10-028/10-029/10-036/10-037/10-038/10-039/10-056/10-057/10-058/10-059/10-061/10-062 GY-01884 01 01-012/01-013/01-052/01-053/01-058/01-063 02 10-017/10-018/10-028/10-029/10-036/10-037/10-038/10-039/10-056/10-057/10-058/10-059/10-061/10-062 03 04-001 GY-02179 01 03-011/03-014/03-01 02 10-056/10-058 03 01-012/01-013/01-052/01-053/01-058/01-063 04 04-003 GY-03720 01 02-016 02 01-020/01-021/01-034/01-035 03 01-020/01-021/01-034/01-035 04 10-017/10-018/10-028/10-029/10-036/
10-037/10-038/10-039表 3 设备单位生产节拍
设备 01-012 01-013 01-016 01-017 01-018 单位节拍/min 10.0/8.33 10.0/8.33 10.0/9.09 10.0/9.09 10.0/9.09 设备 01-019 01-020 01-021 01-022 01-034 单位节拍/min 10.0/9.09 8.33 8.33 9.09 8.33 设备 01-035 01-052 01-053 01-058 01-063 单位节拍/min 8.33 10.0/8.33 10.0/8.33 10.0/8.33 10.0/8.33 设备 02-016 03-011 03-014 03-017 06-009 单位节拍/min 2.50 3.33 3.33 3.33 8.33 设备 06-010 06-012 06-013 06-014 06-015 单位节拍/min 3.13 8.13/3.13 8.33/3.13 8.33/3.13 8.33/3.13 设备 10-005 10-017 10-018 10-019 10-020 单位节拍/min 5.0 6.25/5.0 7.69/6.25 8.33 8.33 设备 10-023 10-024 10-025 10-026 10-028 单位节拍/min 9.09 8.33 8.33 8.33 8.33/5.0 设备 10-029 10-036 10-037 10-038 10-039 单位节拍/min 6.25/5.0 6.25/5.0 6.25/5.0 8.33/7.69 9.33/5.0 设备 10-056 10-057 10-058 10-059 10-061 单位节拍/min 25.0/8.33 8.33/7.69 25.0/8.33 8.33/7.69 8.33/7.69 设备 10-062 10-063 04-001 04-003 04-006 单位节拍/min 7.69 8.33 7.69 6.25 5.0 表 4 结果对比
性能指标 传统排程 改进排程 最短完成时间 1.0 1.10 按时交货率 1.0 1.13 48 h达成率 1.0 1.28 设备连续性 1.0 0.98 排产速度 1.0 1.48 -
[1] 金嘉诚, 张月霞, 戴佐俊. 离散车间多目标调度算法探究[J]. 电脑与电信, 2017(12): 10-13,47. [2] 周秋艳, 肖满生, 张龙信, 等. 多约束条件下生产排程智能优化技术[J/OL]. 计算机科学, 2021(3): 1-13. [3] 朱筱蓉, 张兴华, 李纬. 一种求解Job-Shop调度问题的量子遗传算法[J]. 机械与电子, 2008(4): 6-10. doi: 10.3969/j.issn.1001-2257.2008.04.002 [4] Li S Y, Zhong S, Pei Z, et al. Multi-objective reconfigurable production line scheduling for smart home appliances[J]. Journal of Systems Engineering and Electronics, 2021, 32(2): 297-317. [5] Li Y B, Huang W X, Wu R, et al. An improved artificial bee colony algorithm for solving multi-objective low-carbon flexible job shop scheduling problem[J]. Applied Soft Computing Journal, 2020, 95: 106544. [6] Kamal A M, Ikramullah B S, Rubeena K, et al. Recent research trends in genetic algorithm based flexible job shop scheduling problems[J]. Mathematical Problems in Engineering, 2018: 1-32. [7] Agarwal M, Srivastava G M S. Genetic algorithm-enabled particle swarm optimization (psoga)-based task scheduling in cloud computing environment[J]. International Journal of Information Technology & Decision Making, 2018, 17(4): 1237-1267. [8] 王玉芳, 缪昇, 马铭阳, 等. 改进混合遗传算法的作业车间调度研究[J]. 现代制造工程, 2021(5): 32-38. [9] 张超勇, 饶运清, 刘向军, 等. 基于POX交叉的遗传算法求解Job-Shop调度问题[J]. 中国机械工程, 2004, 15(23): 83-87. [10] 荆巍巍, 章磊, 田俊. 基于自适应NSGA-Ⅱ算法的柔性车间多目标生产调度[J]. 组合机床与自动化加工技术, 2020(8): 151-155,160.