基于改进双种群遗传算法的多目标绿色柔性作业车间调度

Multi-Objective Green Flexible Job Shop Scheduling Based on an Improved Dual-Population Genetic Algorithm

摘要

为使调度计划在不降低加工效率的情况下实现制造生产的降能减排，建立以最大完工时间、机器总能耗和总碳排放量为优化目标的多目标绿色柔性作业车间调度问题数学模型。传统双种群遗传算法在求解上述模型时，由于初始化解集差异化较小导致调度方案重复性高，为解决这一问题提出一种改进双种群遗传算法。首先，采用两段式编码简化算法流程，并提出一种多目标改进全局-局部-随机搜索初始化方法增加种群解集多样性，提出适应度种群分割方法划分种群。之后对两个种群分别进行进化操作，并在合并后进行种群择优以提高下一代种群质量。最后，采用归一化法综合评估，选出最优调度方案。通过改进 Brandimarte 数据集和实例数据对改进双种群遗传算法进行验证对比，结果表明，改进双种群遗传算法在求解多目标绿色柔性作业车间调度问题时具有较大的优势。

Abstract

In order to achieve energy and emission reduction for scheduling plans in manufacturing without reducing processing efficiency, a mathematical model of the multi-objective green flexible job shop scheduling problem is established with the objectives of minimizing makespan, total energy consumption of machines and total carbon emissions. To address the problem that the traditional dual-population genetic algorithm tends to generate highly repetitive scheduling schemes due to the low diversity of the initial population when solving the model, an improved dual population genetic algorithm is proposed. Firstly, a two-stage coding strategy is adopted to simplify algorithm processes, and a multi-objective improved global-local-random search initialization method is proposed to increase the population diversity. Then, a fitness-based population segmentation method is developed to divide the population. Subsequently, evolutionary operations are carried out on the two populations separately, and population selection is conducted after merging to improve the quality of the next generation. Finally, a normalization method is adopted for comprehensive evaluation to select the optimal schedule. Comparative experiments on an improved Brandimarte dataset and a practical case show that the proposed algorithm has great advantages in solving the multi-objective green flexible job shop scheduling problem.

关键词

多目标绿色柔性作业车间 / 全局-局部-随机 (GLR) 搜索初始化方法 / 双种群遗传算法 / 欧氏距离 / 适应度种群分割

Key words

multi-objective flexible job shop / global-local-random (GLR) search initialization / dual population genetic algorithm / Euclidean distance / fitness-based population segmentation

参考文献

[1] 工业和信息化部. 关于印发《“十四五”工业绿色发展规划》的通知[EB/OL]. (2021-12-03) [2025-06-30]. https://www.miit.gov.cn/zwgk/zcwj/wjfb/tz/art/2021/art_4ac49eddca6f43d68ed17465109b6001.html.

[2] 高亮, 张国辉, 王晓娟. 柔性作业车间调度智能算法及其应用[M]. 武汉: 华中科技大学出版社, 2012.

[3] Wang Y, Peng W G, Lu C, et al. A multi-objective cellular memetic optimization algorithm for green scheduling in flexible job shops[J]. Symmetry, 2022, 14(4): 832.

[4] Zhang H L, Xu G J, Pan R L, et al. A novel heuristic method for the energy-efficient flexible job-shop scheduling problem with sequence-dependent set-up and transportation time[J]. Engineering Optimization, 2022, 54(10): 1646-1667.

[5] Liu C, Han Y Y, Wang Y T, et al. Multi-population coevolutionary algorithm for a green multi-objective flexible job shop scheduling problem with automated guided vehicles and variable processing speed constraints[J]. Swarm and Evolutionary Computation, 2024, 91: 101774.

[6] Li R, Gong W Y, Lu C, et al. A learning-based memetic algorithm for energy-efficient flexible job-shop scheduling with type-2 fuzzy processing time[J]. IEEE Transactions on Evolutionary Computation, 2023, 27(3): 610-620.

[7] Liu H X, Zhuang P T, Zhang J S, et al. Optimizing low-carbon job shop scheduling in green manufacturing with the improved NSGAII algorithm[C]// Industrial Engineering and Industrial Management. Cham: Springer, 2024: 76-86.

[8] Wang L, Wang S Y, Xu Y, et al. A bi-population based estimation of distribution algorithm for the flexible job-shop scheduling problem[J]. Computers & Industrial Engineering, 2012, 62(4): 917-926.

[9] 王玉芳, 姚彬彬, 陈凡, 等 . 双种群混合遗传算法求解航空复合材料柔性调度问题[J]. 计算机工程与设计, 2024, 45(10): 3143-3152.

[10] Wang Yufang, Yao Binbin, Chen Fan, et al. Two-population hybrid genetic algorithm for flexible job-shop scheduling problem in aerospace composites[J]. Computer Engineering and Design, 2024, 45(10): 3143-3152.

[11] 李佳磊, 顾幸生. 双种群混合遗传算法求解具有预防性维护的分布式柔性作业车间调度问题[J]. 控制与决策, 2023, 38(2): 475-482.

[12] Li Jialei, Gu Xingsheng. Two-population hybrid genetic algorithm for distributed flexible job-shop scheduling problem with preventive maintenance[J]. Control and Decision, 2023, 38(2): 475-482.

[13] 汪豪, 谢辉, 李艳武. 基于动态双种群 NSGA2 算法的分布式柔性作业车间调度研究[J]. 机电工程, 2024, 41(12): 2252-2260.

[14] Wang Hao, Xie Hui, Li Yanwu. Distributed flexible job shop scheduling based on dynamic dual population NSGA2 algorithm[J]. Journal of Mechanical & Electrical Engineering, 2024, 41(12): 2252-2260.

[15] Pan Z X, Lei D M, Wang L. A bi-population evolutionary algorithm with feedback for energy-efficient fuzzy flexible job shop scheduling[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2021, 52(8): 5295-5307.

[16] Jiang T H, Deng G L. Optimizing the low-carbon flexible job shop scheduling problem considering energy consumption[J]. IEEE Access, 2018, 6: 46346-46355.

[17] 徐新胜, 吴松泽, 杜文, 等 . 考虑低碳的柔性作业车间分批调度方法[J/OL]. 中国机械工程, 2025: 1-16 [2025-06-30]. http://kns.cnki.net/kcms/detail/42.1294.TH.20250325.1330.015.html.

[18] Xu Xinsheng, Wu Songze, Du Wen, et al. Consideration of low-carbon flexible job shop batch scheduling methods[J/OL]. China Mechanical Engineering, 2025: 1-16 [2025-06-30]. http://kns.cnki.net/kcms/detail/42.1294.TH.20250325.1330.015.html.

[19] 黄学文, 陈绍芬, 周阗玉, 等 . 求解柔性作业车间调度的遗传算法综述[J]. 计算机集成制造系统, 2022, 28(2): 536-551.

[20] Huang Xuewen, Chen Shaofen, Zhou Tianyu, et al. Survey on genetic algorithms for solving flexible job-shop scheduling problem[J]. Computer Integrated Manufacturing Systems, 2022, 28(2): 536-551.

[21] 张国辉, 高亮, 李培根, 等 . 改进遗传算法求解柔性作业车间调度问题[J]. 机械工程学报, 2009, 45(7): 145-151.

[22] Zhang Guohui, Gao Liang, Li Peigen, et al. Improved genetic algorithm for the flexible job-shop scheduling problem[J]. Journal of Mechanical Engineering, 2009, 45(7): 145-151.

[23] 张文豪, 施展. 基于欧式距离与灰色预测模型的机床主轴剩余寿命研究[J]. 制造业自动化, 2019, 41(3): 93-96.

[24] Zhang Wenhao, Shi Zhan. Research on residual life of machine tool spindle based on Euclidean distance and grey prediction model[J]. Manufacturing Automation, 2019, 41(3): 93-96.

[25] 程子安, 童鹰, 申丽娟, 等 . 双种群混合遗传算法求解柔性作业车间调度问题[J]. 计算机工程与设计, 2016, 37(6): 1636-1642.

[26] Cheng Zian, Tong Ying, Shen Lijuan, et al. Double population hybrid genetic algorithm for solving flexible job shop scheduling problem[J]. Computer Engineering and Design, 2016, 37(6): 1636-1642.

[27] 刘志硕, 林思萌, 李艳华. 基于旅客出行需求的同城机场群航班协同规划方法[J]. 北京交通大学学报, 2025, 49(1): 148-157.

[28] Liu Zhishuo, Lin Simeng, Li Yanhua. Flight collaborative planning method for metropolitan multi-airport systems based on passenger travel demand[J]. Journal of Beijing Jiaotong University, 2025, 49(1): 148-157.

[29] 张国辉, 李志霄, 张利平, 等 . 基于强化学习协同进化算法求解柔性作业车间节能调度问题[J/OL]. 计算机应用研究, 2025: 1-11[2025-06-30]. https://doi.org/10.19734/j.issn.1001-3695.2024.11.0479.

[30] Zhang Guohui, Li Zhixiao, Zhang Liping, et al. Reinforcement learning based co-evolutionary algorithm for solving flexible job shop energy efficient scheduling problem[J/OL]. Application Research of Computers, 2025: 1-11[2025-06-30]. https://doi.org/10.19734/j.issn.1001-3695.2024.11.0479.

[31] 陈锐, 陈勇, 王宸, 等 . 改进 NSGA-Ⅲ的高维多目标柔性作业车间低碳调度方法研究[J]. 制造技术与机床, 2024(10): 165-173.

[32] Chen Rui, Chen Yong, Wang Chen, et al. Research on low-carbon scheduling method for high-dimensional multi-objective flexible job shop improved by NSGA-Ⅲ[J]. Manufacturing Technology & Machine Tool, 2024(10): 165-173.

[33] Brandimarte P. Routing and scheduling in a flexible job shop by tabu search[J]. Annals of Operations Research, 1993, 41(3): 157-183.

[34] 田志强, 姜兴宇, 杨国哲, 等 . 一种面向航天复杂构件的柔性作业车间能耗优化调度问题研究[J]. 机械工程学报, 2023, 59(8): 273-287.

[35] Tian Zhiqiang, Jiang Xingyu, Yang Guozhe, et al. Energy efficient scheduling of flexible job shop with aerospace complex components[J]. Journal of Mechanical Engineering, 2023, 59(8): 273-287.

[36] Wang B L, Huang K, Li T K. Two-stage hybrid flowshop scheduling with simultaneous processing machines[J]. Journal of Scheduling, 2018, 21(4): 387-411.

[37] 周滨, 常芸祥. 环保工艺在船舶涂装工艺技术改造中的应用[J]. 船舶物资与市场, 2024, 32(9): 58-60.