2.845

2023影响因子

(CJCR)

  • 中文核心
  • EI
  • 中国科技核心
  • Scopus
  • CSCD
  • 英国科学文摘

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

面向可持续生产中多任务调度的双重增强模因算法

卢弘 王耀南 乔非 方遒

卢弘, 王耀南, 乔非, 方遒. 面向可持续生产中多任务调度的双重增强模因算法. 自动化学报, 2024, 50(4): 731−744 doi: 10.16383/j.aas.c230446
引用本文: 卢弘, 王耀南, 乔非, 方遒. 面向可持续生产中多任务调度的双重增强模因算法. 自动化学报, 2024, 50(4): 731−744 doi: 10.16383/j.aas.c230446
Lu Hong, Wang Yao-Nan, Qiao Fei, Fang Qiu. Dual-enhanced memetic algorithm for multi-task scheduling in sustainable production. Acta Automatica Sinica, 2024, 50(4): 731−744 doi: 10.16383/j.aas.c230446
Citation: Lu Hong, Wang Yao-Nan, Qiao Fei, Fang Qiu. Dual-enhanced memetic algorithm for multi-task scheduling in sustainable production. Acta Automatica Sinica, 2024, 50(4): 731−744 doi: 10.16383/j.aas.c230446

面向可持续生产中多任务调度的双重增强模因算法

doi: 10.16383/j.aas.c230446
基金项目: 湖南创新型省份建设科技重大专项 (2021GK1010), 国家自然科学基金 (62293510), 湖南省自然科学基金 (2023JJ30162), 岳麓山工业创新中心重大项目 (2023YCII0102), 湖南省教育厅科学研究项目优秀青年项目 (23B0029) 资助
详细信息
    作者简介:

    卢弘:湖南大学电气与信息工程学院博士后. 2022 年获得同济大学博士学位. 主要研究方向为生产调度与智能优化. E-mail: luhong@hnu.edu.cn

    王耀南:中国工程院院士, 湖南大学电气与信息工程学院教授. 1995 年获得湖南大学博士学位. 主要研究方向为机器人学, 智能控制和图像处理. E-mail: yaonan@hnu.edu.cn

    乔非:同济大学电子与信息工程学院教授. 1997 年获得同济大学博士学位. 主要研究方向为复杂制造计划与调度, 智能生产系统以及能源管理与优化. E-mail: fqiao@tongji.edu.cn

    方遒:湖南大学电气与信息工程学院副教授. 2017 年获得同济大学博士学位. 主要研究方向为复杂工业过程建模与优化. 本文通信作者. E-mail: qfang@hnu.edu.cn

Dual-enhanced Memetic Algorithm for Multi-task Scheduling in Sustainable Production

Funds: Supported by Special Funding Support for the Construction of Innovative Provinces in Hunan Province (2021GK1010), National Natural Science Foundation of China (62293510), Hunan Provincial Natural Science Foundation (2023JJ30162), Major Project of Yuelushan Industrial Innovation Center (2023YCII0102), and Hunan Provincial Department of Education Scientific Research Project (23B0029)
More Information
    Author Bio:

    LU Hong Postdoctor at the College of Electrical and Information Engineering, Hunan University. He received his Ph.D. degree from Tongji University in 2022. His research interest covers production scheduling and intelligent optimization

    WANG Yao-Nan Academician at Chinese Academy of Engineering, professor at the College of Electrical and Information Engineering, Hunan University. He received his Ph.D. degree from Hunan University in 1995. His research interest covers robotics, intelligent control, and image processing

    QIAO Fei Professor at the College of Electronics and Information Engineering, Tongji University. She received her Ph.D. degree from Tongji University in 1997. Her research interest covers complex manufacturing planning and scheduling, intelligent production systems, and energy management and optimization

    FANG Qiu Associate professor at the College of Electrical and Information Engineering, Hunan University. He received his Ph.D. degree from Tongji University in 2017. His research interest covers modeling and optimization of complex industrial processes. Corresponding author of this paper

  • 摘要: 从经济、环境和社会3个维度, 全面提升生产调度方案的可持续性具有重要意义. 针对并行机生产场景, 建立考虑机器指派、加工顺序、人员安排以及开关机控制等4种决策任务的调度模型. 为实现对复杂决策空间的高效寻优, 提出一种融合两种局部优化策略的双重增强模因算法(Dual-enhanced memetic algorithm, DMA)求解模型. 从随机更新角度, 针对不同决策任务, 构造单步变邻域搜索(One-step variable neighborhood search, 1S-VNS)策略. 从定向优化角度, 分析目标和关键任务之间的匹配关系, 提出一种可持续目标导向策略(Sustainable goals-oriented strategy, SGS). 考虑到两种优化策略的不同特点, 单步变邻域搜索策略作用于整个种群, 目标导向策略强化种群中的精英个体, 实现对输出解集的双重优化. 仿真实验结果表明, 双重优化策略能有效地增强算法性能, 并且所提算法在非支配解的多样性和收敛性上具有优越性.
  • 图  1  任务对应的个体编码说明图

    Fig.  1  An example graph of individual coding corresponding for tasks

    图  2  社会维度目标导向的优化策略作用效果说明图

    Fig.  2  Explanation of the effectiveness of optimization strategy guided by social dimension goal

    图  3  经济维度目标导向的优化策略作用效果说明图

    Fig.  3  Explanation of the effectiveness of optimization strategy guided by economic dimension goal

    图  4  MMA与MOA、MMA_1、MMA_2、MMA_3性能指标的均值和95%置信区间

    Fig.  4  Mean and 95% confidence interval of performance indicators of MMA, MOA, MMA_1, MMA_2 and MMA_3

    图  5  DMA与MMA、MMA&SGS性能指标的均值和95%置信区间

    Fig.  5  Mean and 95% confidence interval of performance indicators of DMA, MAA and MMA&SGS

    图  6  DMA与V-NSGA-II、IABC、MA性能指标的均值和95%置信区间

    Fig.  6  Mean and 95% confidence interval of performance indicators of DMA, V-NSGA-II, IABC and MA

    图  7  DMA与V-NSGA-II、IABC、MA获得的Pareto前沿

    Fig.  7  Pareto frontiers obtained by DMA, V-NSGA-II, IABC and MA

    表  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
    下载: 导出CSV

    表  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
    下载: 导出CSV

    表  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
    下载: 导出CSV

    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
    下载: 导出CSV

    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
    下载: 导出CSV
  • [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−768

    Li 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−2426

    Fan 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−1135

    Jia 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−2438

    Pan 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−1337

    Lei 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−1480

    Geng 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−216

    Wang 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
  • 加载中
图(7) / 表(5)
计量
  • 文章访问数:  380
  • HTML全文浏览量:  58
  • PDF下载量:  142
  • 被引次数: 0
出版历程
  • 收稿日期:  2023-07-20
  • 录用日期:  2024-01-23
  • 网络出版日期:  2024-03-29
  • 刊出日期:  2024-04-26

目录

    /

    返回文章
    返回