Dual-enhanced Memetic Algorithm for Multi-task Scheduling in Sustainable Production
-
摘要: 从经济、环境和社会3个维度, 全面提升生产调度方案的可持续性具有重要意义. 针对并行机生产场景, 建立考虑机器指派、加工顺序、人员安排以及开关机控制等4种决策任务的调度模型. 为实现对复杂决策空间的高效寻优, 提出一种融合两种局部优化策略的双重增强模因算法(Dual-enhanced memetic algorithm, DMA)求解模型. 从随机更新角度, 针对不同决策任务, 构造单步变邻域搜索(One-step variable neighborhood search, 1S-VNS)策略. 从定向优化角度, 分析目标和关键任务之间的匹配关系, 提出一种可持续目标导向策略(Sustainable goals-oriented strategy, SGS). 考虑到两种优化策略的不同特点, 单步变邻域搜索策略作用于整个种群, 目标导向策略强化种群中的精英个体, 实现对输出解集的双重优化. 仿真实验结果表明, 双重优化策略能有效地增强算法性能, 并且所提算法在非支配解的多样性和收敛性上具有优越性.Abstract: It is of great significance to comprehensively enhance the sustainability of production scheduling with economic, environmental and social demand. A scheduling model for parallel machine production is established with consideration of four decision tasks: Machine assignment, processing sequence, personnel arrangement, and on/off machine control. To solve this complex problem, a dual-enhanced memetic algorithm (DMA) that integrates two local optimization strategies is proposed. In a random manner, a one-step variable neighborhood search (1S-VNS) suitable for decision-making tasks is designed. For targeted optimization, a sustainable goals-oriented strategy (SGS) is constructed after analyzing the matching relationship between objectives and key tasks. Based on the different characteristics of the two optimization strategies, the 1S-VNS acts on the entire population, and the SGS strengthens the elite individuals, achieving dual optimization of the output solution set. The simulation experimental results show that the dual optimization strategies effectively enhance the algorithm performance, and the proposed DMA has superiority in diversity and convergence of non-dominated solutions.
-
表 1 MMA与MOA、MMA_1、MMA_2、MMA_3的性能指标结果
Table 1 Results for MMA, MOA, MMA_1, MMA_2 and MMA_3
案例 $ IGD$ $R_{{\mathrm{nd}}} $ MOA MMA_1 MMA_2 MMA_3 MMA MOA MMA_1 MMA_2 MMA_3 MMA 7&4&2 0.79 0.66 0.63 0.39 0.24 0.10 0.39 0.55 0.70 0.87 7&5&3 0.79 0.65 0.58 0.86 0.33 0.13 0.39 0.47 0.42 0.72 8&4&2 0.97 0.53 0.52 0.50 0.36 0.00 0.41 0.43 0.46 0.71 8&5&3 0.74 0.63 0.53 0.57 0.47 0.00 0.14 0.40 0.35 0.61 9&4&2 0.87 0.71 0.69 0.63 0.39 0.13 0.08 0.19 0.31 0.71 9&5&3 0.64 0.57 0.63 0.59 0.35 0.00 0.19 0.11 0.32 0.75 10&4&2 0.97 0.69 0.66 0.78 0.41 0.00 0.13 0.33 0.23 0.70 10&5&3 0.70 0.67 0.55 0.59 0.44 0.00 0.07 0.38 0.29 0.67 20&10&6 0.69 0.64 0.67 0.69 0.43 0.07 0.23 0.14 0.09 0.66 20&10&8 0.67 0.82 0.80 0.73 0.36 0.15 0.02 0.11 0.13 0.70 20&12&8 0.68 0.77 0.47 0.75 0.49 0.50 0.10 0.63 0.23 0.62 20&12&10 0.48 0.90 0.53 0.72 0.40 0.68 0.08 0.58 0.12 0.68 40&10&6 0.85 0.94 0.64 0.90 0.32 0.10 0.00 0.29 0.00 0.71 40&10&8 0.92 0.91 0.62 0.65 0.31 0.05 0.08 0.28 0.12 0.78 40&12&8 0.86 0.69 0.74 0.85 0.39 0.09 0.17 0.11 0.10 0.69 40&12&10 0.77 0.78 0.71 0.81 0.43 0.14 0.13 0.17 0.12 0.67 表 2 DMA与MMA、MMA&SGS的性能指标结果
Table 2 Results for DMA, MMA and MMA&SGS
案例 $ IGD$ $R_{{\mathrm{nd}}} $ MMA MMA&SGS DMA MMA MMA&SGS DMA 7&4&2 0.00 0.00 0.00 1.00 1.00 1.00 7&5&3 0.35 0.49 0.38 0.87 0.70 0.86 8&4&2 0.45 0.51 0.39 0.71 0.48 0.76 8&5&3 0.29 0.44 0.34 0.74 0.49 0.72 9&4&2 0.61 0.57 0.41 0.62 0.52 0.73 9&5&3 0.52 0.80 0.39 0.65 0.36 0.77 10&4&2 0.80 0.80 0.36 0.47 0.46 0.77 10&5&3 0.57 0.85 0.43 0.42 0.30 0.71 20&10&6 0.71 0.57 0.41 0.20 0.69 0.74 20&10&8 0.65 0.51 0.43 0.12 0.70 0.73 20&12&8 0.71 0.44 0.47 0.22 0.74 0.72 20&12&10 0.85 0.39 0.42 0.22 0.79 0.75 40&10&6 0.80 0.59 0.39 0.11 0.28 0.79 40&10&8 0.71 0.58 0.37 0.16 0.33 0.72 40&12&8 0.73 0.83 0.42 0.19 0.30 0.71 40&12&10 0.74 0.65 0.40 0.22 0.26 0.73 表 3 DMA与V-NSGA-II、IABC、MA的性能指标结果
Table 3 Results for DMA, V-NSGA-II, IABC and MA
案例 $IGD$ $R_{{\mathrm{nd}}}$ V-NSGA-II IABC MA DMA V-NSGA-II IABC MA DMA 7&4&2 0.85 0.67 0.48 0.15 0.00 0.15 0.70 0.87 7&5&3 0.74 0.85 0.66 0.24 0.00 0.08 0.22 0.82 8&4&2 0.65 0.76 0.41 0.32 0.20 0.08 0.43 0.76 8&5&3 0.78 0.80 0.32 0.25 0.32 0.24 0.44 0.87 9&4&2 0.41 0.63 0.56 0.36 0.39 0.34 0.37 0.76 9&5&3 0.86 0.61 0.57 0.13 0.15 0.20 0.35 0.86 10&4&2 0.52 0.31 0.49 0.22 0.21 0.31 0.27 0.77 10&5&3 0.63 0.56 0.52 0.20 0.12 0.22 0.45 0.78 20&10&6 0.85 0.88 0.69 0.21 0.07 0.05 0.15 0.83 20&10&8 0.83 0.91 0.72 0.18 0.02 0.00 0.11 0.86 20&12&8 0.79 0.84 0.74 0.31 0.05 0.00 0.23 0.71 20&12&10 0.82 0.93 0.69 0.30 0.03 0.00 0.35 0.74 40&10&6 0.78 0.81 0.55 0.11 0.00 0.00 0.15 0.85 40&10&8 0.62 0.89 0.61 0.29 0.14 0.00 0.14 0.73 40&12&8 0.59 0.87 0.53 0.23 0.11 0.00 0.15 0.77 40&12&10 0.62 0.83 0.50 0.31 0.09 0.00 0.18 0.71 A1 各个工件的基本加工数据
A1 Basic machining data for each job
工件 机器 工人 加工时间$t$ 加工单位能耗$p^{\rm{prc}}$ $J1$ $M1$ $W1$ 3 8 $J1$ $M1$ $W2$ 6 6 $J1$ $M2$ $W1$ 4 6 $J1$ $M2$ $W2$ 2 4 $J1$ $M3$ $W1$ 6 5 $J1$ $M3$ $W2$ 6 6 $J2$ $M1$ $W1$ 4 7 $J2$ $M1$ $W2$ 2 5 $J2$ $M2$ $W1$ 3 5 $J2$ $M2$ $W2$ 4 8 $J2$ $M3$ $W1$ 4 3 $J2$ $M3$ $W2$ 3 8 $J3$ $M1$ $W1$ 5 8 $J3$ $M1$ $W2$ 5 7 $J3$ $M2$ $W1$ 3 3 $J3$ $M2$ $W2$ 2 4 $J3$ $M3$ $W1$ 3 5 $J3$ $M3$ $W2$ 3 7 $J4$ $M1$ $W1$ 4 3 $J4$ $M1$ $W2$ 4 7 $J4$ $M2$ $W1$ 2 3 $J4$ $M2$ $W2$ 3 6 $J4$ $M3$ $W1$ 6 5 $J4$ $M3$ $W2$ 2 7 $J5$ $M1$ $W1$ 6 7 $J5$ $M1$ $W2$ 5 8 $J5$ $M2$ $W1$ 4 8 $J5$ $M2$ $W2$ 4 5 $J5$ $M3$ $W1$ 3 7 $J5$ $M3$ $W2$ 4 4 A2 机器单位空闲能耗以及开关机能耗
A2 Unit idle energy consumption and on/off energy consumption of machines
机器 空闲单位能耗$p^{\rm{idle}}$ 开关机时间$t_{\rm{on/off}}$ 开关机能耗$H_{\rm{turn}}$ $M1$ 1 2 2 $M2$ 3 3 9 $M3$ 3 3 6 -
[1] 国家制造强国建设战略咨询委员会. 中国制造2025蓝皮书 (2018). 北京: 电子工业出版社, 2018.National Manufacturing Power Construction Strategy Advisory Committee. China Manufacturing 2025 Bluebook (2018). Beijing: Publishing House of Electronics Industry, 2018. [2] Bertolini M, Leali F, Mezzogori D, Renzi C. A keyword, taxonomy and cartographic research review of sustainability concepts for production scheduling in manufacturing systems. Sustainability, 2023, 15(8): Article No. 6884 doi: 10.3390/su15086884 [3] Akbar M, Irohara T. Scheduling for sustainable manufacturing: A review. Journal of Cleaner Production, 2018, 205: 866−883 doi: 10.1016/j.jclepro.2018.09.100 [4] Catanzaro D, Pesenti R, Ronco R. Job scheduling under time-of-use energy tariffs for sustainable manufacturing: A survey. European Journal of Operational Research, 2023, 308(3): 1091−1109 doi: 10.1016/j.ejor.2023.01.029 [5] 李远征, 倪质先, 段钧韬, 徐磊, 杨涛, 曾志刚. 面向高比例新能源电网的重大耗能企业需求响应调度. 自动化学报, 2023, 49(4): 754−768Li Yuan-Zheng, Ni Zhi-Xian, Duan Jun-Tao, Xu Lei, Yang Tao, Zeng Zhi-Gang. Demand response scheduling of major energy-consuming enterprises based on a high proportion of renewable energy power grid. Acta Automatica Sinica, 2023, 49(4): 754−768 [6] 范厚明, 郭振峰, 岳丽君, 马梦知. 考虑能耗节约的集装箱码头双小车岸桥与AGV联合配置及调度优化. 自动化学报, 2021, 47(10): 2412−2426Fan Hou-Ming, Guo Zhen-Feng, Yue Li-Jun, Ma Meng-Zhi. Joint configuration and scheduling optimization of dual-trolley quay crane and AGV for container terminal with considering energy saving. Acta Automatica Sinica, 2021, 47(10): 2412−2426 [7] 贾兆红, 王燕, 张以文. 求解差异机器平行批调度的双目标协同蚁群算法. 自动化学报, 2020, 46(6): 1121−1135Jia Zhao-Hong, Wang Yan, Zhang Yi-Wen. A bi-objective synergy optimization algorithm of ant colony for scheduling on non-identical parallel batch machines. Acta Automatica Sinica, 2020, 46(6): 1121−1135 [8] Tonelli F, Bruzzone A A G, Paolucci M, Carpanzano E, Nicolò G, Giret A, et al. Assessment of mathematical programming and agent-based modelling for off-line scheduling: Application to energy aware manufacturing. CIRP Annals, 2016, 65(1): 405−408 doi: 10.1016/j.cirp.2016.04.119 [9] Alotaibi A, Lohse N, Vu T M. Dynamic agent-based bi-objective robustness for tardiness and energy in a dynamic flexible job shop. Procedia CIRP, 2016, 57: 728−733 doi: 10.1016/j.procir.2016.11.126 [10] Zhou G H, Chen Z H, Zhang C, Chang F T. An adaptive ensemble deep forest based dynamic scheduling strategy for low carbon flexible job shop under recessive disturbance. Journal of Cleaner Production, 2022, 337: Article No. 130541 doi: 10.1016/j.jclepro.2022.130541 [11] 潘子肖, 雷德明. 基于问题性质的分布式低碳并行机调度算法研究. 自动化学报, 2020, 46(11): 2427−2438Pan Zi-Xiao, Lei De-Ming. Research on property-based distributed low carbon parallel machines scheduling algorithm. Acta Automatica Sinica, 2020, 46(11): 2427−2438 [12] 雷德明, 杨冬婧. 基于新型蛙跳算法的低碳混合流水车间调度. 控制与决策, 2020, 35(6): 1329−1337Lei De-Ming, Yang Dong-Jing. A novel shuffled frog-leaping algorithm for low carbon hybrid flow shop scheduling. Control and Decision, 2020, 35(6): 1329−1337 [13] 耿凯峰, 叶春明, 吴绍兴, 刘丽. 分时电价下多目标绿色可重入混合流水车间调度. 中国机械工程, 2020, 31(12): 1469−1480Geng Kai-Feng, Ye Chun-Ming, Wu Shao-Xing, Liu Li. Multi-objective green re-entrant hybrid flow shop scheduling under time-of-use electricity tariffs. China Mechanical Engineering, 2020, 31(12): 1469−1480 [14] Liang Y L, Guo C X, Li K J, Li M Y. Economic scheduling of compressed natural gas main station considering critical peak pricing. Applied Energy, 2021, 292: Article No. 116937 doi: 10.1016/j.apenergy.2021.116937 [15] Giret A, Trentesaux D, Prabhu V. Sustainability in manufacturing operations scheduling: A state of the art review. Journal of Manufacturing Systems, 2015, 37: 126−140 doi: 10.1016/j.jmsy.2015.08.002 [16] Wu X Q, Che A. A memetic differential evolution algorithm for energy-efficient parallel machine scheduling. Omega, 2019, 82: 155−165 doi: 10.1016/j.omega.2018.01.001 [17] Lu H, Qiao F. A sustainable parallel-machine scheduling problem with time constraint based on hybrid metaheuristic algorithm. In: Proceedings of the Chinese Automation Congress (CAC). Shanghai, China: IEEE, 2020. 1506−1510 [18] Dai M, Tang D B, Giret A, Salido M A, Li W D. Energy-efficient scheduling for a flexible flow shop using an improved genetic-simulated annealing algorithm. Robotics and Computer-Integrated Manufacturing, 2013, 29(5): 418−429 doi: 10.1016/j.rcim.2013.04.001 [19] Mouzon G, Yildirim M B, Twomey J. Operational methods for minimization of energy consumption of manufacturing equipment. International Journal of Production Research, 2007, 45(18−19): 4247−4271 doi: 10.1080/00207540701450013 [20] Akbar M, Irohara T. NSGA-Ⅱ variants for solving a social-conscious dual resource-constrained scheduling problem. Expert Systems With Applications, 2020, 162: Article No. 113754 doi: 10.1016/j.eswa.2020.113754 [21] Neri F, Cotta C. Memetic algorithms and memetic computing optimization: A literature review. Swarm and Evolutionary Computation, 2012, 2: 1−14 doi: 10.1016/j.swevo.2011.11.003 [22] Amaya J E, Cotta P C, Fernández Leiva A J. Memetic and hybrid evolutionary algorithms. Springer Handbook of Computational Intelligence. Berlin Heidelberg: Springer, 2015. 1047−1060 [23] Geng K F, Ye C M, Liu L. Research on multi-objective hybrid flow shop scheduling problem with dual resource constraints using improved memetic algorithm. IEEE Access, 2020, 8: 104527−104542 doi: 10.1109/ACCESS.2020.2999680 [24] Zhu H, Deng Q W, Zhang L K, Hu X, Lin W H. Low carbon flexible job shop scheduling problem considering worker learning using a memetic algorithm. Optimization and Engineering, 2020, 21(4): 1691−1716 doi: 10.1007/s11081-020-09494-y [25] Zhang R, Chiong R. Solving the energy-efficient job shop scheduling problem: A multi-objective genetic algorithm with enhanced local search for minimizing the total weighted tardiness and total energy consumption. Journal of Cleaner Production, 2016, 112: 3361−3375 doi: 10.1016/j.jclepro.2015.09.097 [26] Costa A, Cappadonna F A, Fichera S. A hybrid genetic algorithm for job sequencing and worker allocation in parallel unrelated machines with sequence-dependent setup times. The International Journal of Advanced Manufacturing Technology, 2013, 69(9−12): 2799−2817 doi: 10.1007/s00170-013-5221-5 [27] Fanjul-Peyro L, Ruiz R. Iterated greedy local search methods for unrelated parallel machine scheduling. European Journal of Operational Research, 2010, 207(1): 55−69 doi: 10.1016/j.ejor.2010.03.030 [28] Guo P, Cheng W M, Wang Y. A general variable neighborhood search for single-machine total tardiness scheduling problem with step-deteriorating jobs. Journal of Industrial and Management Optimization, 2014, 10(4): 1071−1090 doi: 10.3934/jimo.2014.10.1071 [29] Fontes D B M M, Homayouni S M, Gonçalves J F. A hybrid particle swarm optimization and simulated annealing algorithm for the job shop scheduling problem with transport resources. European Journal of Operational Research, 2023, 306(3): 1140−1157 doi: 10.1016/j.ejor.2022.09.006 [30] 王飞, 孟凡超, 郑宏珍. 基于禁忌搜索和遗传算法的云仓储分配优化. 计算机集成制造系统, 2022, 28(1): 208−216Wang Fei, Meng Fan-Chao, Zheng Hong-Zhen. Distribution and optimization of cloud warehousing based on tabu search algorithm. Computer Integrated Manufacturing Systems, 2022, 28(1): 208−216 [31] Bezerra S N, Souza M J F, de Souza S R. A variable neighborhood search-based algorithm with adaptive local search for the vehicle routing problem with time windows and multi-depots aiming for vehicle fleet reduction. Computers and Operations Research, 2023, 149: Article No. 106016 [32] Sun K X, Zheng D B, Song H H, Cheng Z W, Lang X D, Yuan W D, et al. Hybrid genetic algorithm with variable neighborhood search for flexible job shop scheduling problem in a machining system. Expert Systems With Applications, 2023, 215: Article No. 119359 doi: 10.1016/j.eswa.2022.119359 [33] Wagner S, Mönch L. A variable neighborhood search approach to solve the order batching problem with heterogeneous pick devices. European Journal of Operational Research, 2023, 304(2): 461−475 doi: 10.1016/j.ejor.2022.03.056 [34] Guo H F, Zhang L S, Ren Y P, Li Y, Zhou Z W, Wu J Z. Optimizing a stochastic disassembly line balancing problem with task failure via a hybrid variable neighborhood descent-artificial bee colony algorithm. International Journal of Production Research, 2023, 61(7): 2307−2321 doi: 10.1080/00207543.2022.2069524 [35] Li Y B, Huang W X, Wu R, Guo K. An improved artificial bee colony algorithm for solving multi-objective low-carbon flexible job shop scheduling problem. Applied Soft Computing, 2020, 95: Article No. 106544 doi: 10.1016/j.asoc.2020.106544