Low-carbon Scheduling of Multi-objective Flexible Job-shop Based on Improved NSGA-Ⅱ

doi:10.3969/j.issn.1004-132X.2022.21.006

Abstract

Abstract: To solve the low-carbon scheduling problems of multi-objective flexible job-shops taking equipment energy consumption， tool wear and cutting fluid consumption as carbon emission sources and energy consumption and labor cost as processing cost， a low-carbon scheduling model was formulated to minimize carbon emission， makespan and processing cost， and an improved elitist NSGA-Ⅱ was proposed to solve the problem. Firstly， the chromosome composition was dynamically adjusted by encoding based on Tent chaotic map and greedy decoding based on analytic hierarchy process to improve the quality of the initial population. Then， an adaptive genetic strategy was proposed based on genetic parameters， which adjusted the crossover and mutation rates according to the population evolution stage and the population non dominated state dynamically. Finally， based on external archives an improved elite retention strategy was designed to improve the population diversity in the later stages of the algorithm and retain high-quality individuals in the evolution processes. The effectiveness of the improved algorithm was verified by standard scheduling examples and a practical case.

Key words: low-carbon, flexible job-shop, multi-objective scheduling, non-dominated sorting genetic algorithm（NSGA-Ⅱ）

摘要： 为解决以设备能耗、刀具磨损和切削液消耗为碳排放来源，能耗和人工费用为加工成本的多目标柔性作业车间低碳调度问题，建立以最小化碳排放量、最长完工时间和加工成本为目标的低碳调度模型，提出一种改进带精英策略的非支配遗传算法（NSGA-Ⅱ）并进行求解。首先通过基于Tent混沌映射的编码与融合了层次分析法（AHP）的贪婪解码来动态调整染色体组成，提高初始种群质量；然后提出了一种基于遗传参数的自适应遗传策略，根据种群进化阶段与种群非支配状态动态调整交叉、变异率；最后设计了一种基于外部档案集的改进精英保留策略，提高了算法后期的种群多样性并保留了进化过程中的优质个体。通过标准调度算例与实际案例验证了改进算法的有效性。

关键词: 低碳, 柔性作业车间, 多目标调度, 非支配排序遗传算法

CLC Number:

TP18

JIANG Yixiao , JI Weixi, HE Xin, SU Xuan. Low-carbon Scheduling of Multi-objective Flexible Job-shop Based on Improved NSGA-Ⅱ[J]. China Mechanical Engineering, 2022, 33(21): 2564-2577.

姜一啸, 吉卫喜, 何鑫, 苏璇. 基于改进非支配排序遗传算法的多目标柔性作业车间低碳调度[J]. 中国机械工程, 2022, 33(21): 2564-2577.

References

［1］GAREY M R， SETHI J R. The Complexity of Flowshop and Jobshop Scheduling［J］. Mathematics of Operations Research， 1976， 1（2）：117-129.
［2］王凌，王晶晶，吴楚格. 绿色车间调度优化研究进展［J］. 控制与决策， 2018， 33（3）：385-391.
WANG Ling， WANG Jingjing， WU Chuge. Research Progress of Green Job Shop Scheduling Optimization［J］. Control and Decision， 2018， 33（3）：385-391.
［3］周守为，朱军龙. 助力“碳达峰、碳中和”战略的路径探索［J］. 天然气工业， 2021， 41（12）：1-8.
ZHOU Shouwei， ZHU Junlong. Contribute to The Path Exploration of “Carbon Peak and Carbon Neutralization” Strategy［J］. Natural Gas Industry， 2021， 41（12）：1-8.
［4］刘彩洁，徐志涛，张钦，等. 分时电价下基于NSGA-Ⅱ的柔性作业车间绿色调度［J］. 中国机械工程， 2020， 31（5）：576-585.
LIU Caijie， XU Zhitao， ZHANG Qin， et al. Green Scheduling of Flexible Job Shop Based on NSGA-Ⅱ under TOU Prower Price［J］. China Mechanical Engineering， 2020， 31（5）：576-585.
［5］WU X， SUN Y. A Green Scheduling Algorithm for Flexible Job Shop with Energy-saving Measures［J］. Journal of Cleaner Production， 2018， 172（3）：3249-3264.
［6］ASSIA S， ABBASSI I E， BARKANY A E， et al. Green Scheduling of Jobs and Flexible Periods of Maintenance in a Two-machine Flowshop to Minimize Makespan， a Measure of Service Level and Total Energy Consumption［J］. Advances in Operations Research， 2020， 2020：1-9.
［7］杨冬婧，雷德明. 新型蛙跳算法求解总能耗约束FJSP［J］. 中国机械工程， 2018， 29（22）：2682-2689.
YANG Dongjing， LEI Deming. A New Leapfrog Algorithm to Solve the Total Energy Consumption Constraint FJSP［J］. China Mechanical Engineering， 2018， 29（22）：2682-2689.
［8］李明，雷德明. 考虑准备时间和关键目标的柔性作业车间低碳调度研究［J］. 机械工程学报， 2019， 55（21）：139-149.
LI Ming， LEI Deming. Research on Low Carbon Scheduling of Flexible Job Shop Considering Preparation Time and Key Objectives［J］. Journal of Mechanical Engineering， 2019， 55（21）：139-149.
［9］DEB K， PRATAP A， AGARWAL S， et al. A Fast and Elitist Multiobjective Genetic Algorithm：NSGA-Ⅱ［J］. Transactions on Evolutionary Computation， 2002， 6（2）：182-197.
［10］HAN Y， CHEN X， XU M， et al. A Study on Multi-objective Flexible Job Shop Scheduling Problem Using a Non-dominated Sorting Genetic Algorithm［J］. Mechanisms and Machine Science， 2021， 105：745-755.
［11］LI H， DUAN J， ZHANG Q. Multi-objective Integrated Scheduling Optimization of Semi-combined Marine Crankshaft Structure Production Workshop for Green Manufacturing［J］. Transactions of the Institute of Measurement and Control， 2020， 43（12）：579-596.
［12］JIANG X. Improved NSGA-Ⅱ for the Job-shop Multi-objective Scheduling Problem［J］. International Journal of Performability Engineering， 2018， 14（5）：891-898.
［13］CHEN F，LI Z X， YANG X. Multi-objective Flexible Job Shop Scheduling Based on Improved NSGA2 Algorithm［J］. Industrial Engineering Journal， 2018， 21（2）：55-61.
［14］宋存利. 求解多目标混合流水车间调度的改进NSGA-Ⅱ［J］. 计算机集成制造系统, 2022, 28(6):1777-1789.
SONG Cunli. Improved NSGA-Ⅱ Algorithm for Hybrid Flow Shop Scheduling Problem with Multi-objective［J］. Computer Integrated Manufacturing Systems, 2022, 28(6):1777-1789.
［15］LIANG X， LIU Y， HUANG M. Improved NSGA2 Algorithm to Solve Multi-objective Flexible Job Shop Scheduling Problem［C］∥ IEEE 8th International Conference on Computer Science and Network Technology（ICCSNT）. Dalian， 2020：22-25.
［16］李益兵，黄炜星，吴锐. 基于改进人工蜂群算法的多目标绿色柔性作业车间调度研究［J］. 中国机械工程， 2020， 31（11）：1344-1350.
LI Yibing， HUANG Weixing， WU Rui. Research on Multi-objective Green Flexible Job Shop Scheduling Based on Improved Artificial Bee Colony Algorithm［J］. China Mechanical Engineering， 2020， 31（11）：1344-1350.
［17］李聪波，崔龙国，刘飞，等. 面向高效低碳的数控加工参数多目标优化模型［J］. 机械工程学报， 2013， 49（9）：87-96.
LI Congbo， CUI Longguo， LIU Fei， et al. Multi-objective Optimization Model of NC Machining Parameters for High Efficiency and Low Carbon［J］. Journal of Mechanical Engineering， 2013， 49（9）：87-96.
［18］蔡酉勇，吉卫喜，张朝阳，等. 制造资源实时状态驱动的离散制造车间低碳调度研究［J］. 机械科学与技术， 2020， 39（3）：446-455.
CAI Youyong， JI Weixi， ZHANG Chaoyang， et al. Research on Low Carbon Scheduling of Discrete Manufacturing Workshop Driven by Real-time State of Manufacturing Resources［J］. Mechanical Science and Technology， 2020， 39（3）：446-455.
［19］唐世浩，朱启疆. 遗传算法中初始种群与交叉、变异率对解的影响及其解决方案［J］. 科技通报， 2001， 17（3）：1-7.
TANG Shihao， ZHU Qijiang. Influence of Initial Population， Crossover and Mutation Rate on Solution in Genetic Algorithm and Its Solution［J］. Bulletin of Science and Technology， 2001， 17（3）：1-7.
［20］张娜，赵泽丹，包晓安，等. 基于改进的Tent混沌万有引力搜索算法［J］. 控制与决策， 2020， 35（4）：893-900.
ZHANG Na， ZHAO Zedan， BAO Xiaoan， et al. Improved Tent Chaotic Universal Gravitation Search Algorithm［J］. Control and Decision Making， 2020， 35（4）：893-900.
［21］郑金华，邹娟. 多目标进化算法及其应用［M］. 北京：科学出版社， 2007：57-63.
ZHENG Jinhua， ZOU Juan. Multi-objective Evolutionary Algorithm and Its Application［M］. Beijing：Science Press， 2007：57-63.
［22］王嵘冰，徐红艳，郭军. 自适应的非支配排序遗传算法［J］. 控制与决策， 2018， 33（12）：2191-2196.
WANG Rongbing， XU Hongyan， GUO Jun. Adaptive Non-dominated Sorting Genetic Algorithm［J］. Control and Decision， 2018， 33（12）：2191-2196.
［23］孔祥勇，高立群，欧阳海滨，等. 双向随机多策略变异的自适应差分进化算法［J］. 计算机集成制造系统， 2014， 20（8）：1948-1958.
KONG Xiangyong， GAO Liqun， OUYANG Haibin， et al. Adaptive Differential Evolution Algorithm for Bidirectional Random Multi Strategy Mutation［J］. Computer Integrated Manufacturing Systems， 2014， 20（8）：1948-1958.
［24］王凯，王荣鹏，刘宇，等. 基于Pareto最优原理的钻机钻进参数多目标优化［J］. 中国机械工程， 2017， 28（13）：1580-1587.
WANG Kai， WANG Rongpeng， LIU Yu， et al. Multi-objective Optimization of Drilling Parameters of Drilling Rig Based on Pareto Optimization Principle［J］. China Mechanical Engineering， 2017， 28（13）：1580-1587.
［25］BRANDIMARTE P. Routing and Scheduling in a Flexible Job Shop by Tabu Search［J］. Annals of Operations Research， 1993， 41（3）：157-183.
［26］JAIN H， WEB K. An Evolutionary Many-objective Optimization Algorithm Using Reference-point Based Nondominated Sorting Approach， Part Ⅱ：Handling Constraints and Extending to an Adaptive Approach［J］. IEEE Transactions on Evolutionary Computation， 2014， 18（4）：602-622.
［27］ZITZLER E， THIELE L. Multiobjective Evolutionary Algorithms：a Comparative Case Study and the Strength Pareto Approach［J］. IEEE Transactions on Evolutionary Computation， 1999， 3（4）：257-271.
［28］SCHOTT J R. Fault Tolerant Design Using Single and Multi-criteria Genetic Algorithms［J］. Masters Thesis， Massachusetts Institute of Technology， 1995， 37（1）：1-13.
［29］BROCKHOFF D， FRIEDRICH T， NEUMANN F. Analyzing Hypervolume Indicator Based Algorithms［J］. Springer-Verlag， 2008， 5199：651-660.
［30］张超勇，董星，王晓娟，等. 基于改进非支配排序遗传算法的多目标柔性作业车间调度［J］. 机械工程学报， 2010， 46（11）：156-164.
ZHANG Chaoyong， DONG Xing， WANG Xiaojuan， et al. Multi-objective Flexible Job Shop Scheduling Based on Improved Non Dominated Sorting Genetic Algorithm［J］. Journal of Mechanical Engineering， 2010， 46（11）：156-164.
［31］YE T， XIANG X， ZHANG X， et al. Sampling Reference Points on the Pareto Fronts of Benchmark Multi-objective Optimization Problems［C］∥2018 IEEE Congress on Evolutionary Computation（CEC）. Rio de Janeiro， 2018：1-6.

[1]	SUN Yongguo, JIN Xin, XUE Dong, SHAN Jianping, SHI Xiaochun. Optimal Design of Slip Oil Pump Impeller Structures Based on NSGA-Ⅱ [J]. China Mechanical Engineering, 2024, 35(03): 559-569.
[2]	LIANG Xianglin, SONG Yuchuan, LEI Qi, SUN Aihong. Research on Flexible Job-shop Scheduling Problems Considering Optimization of Worker Number Allocation#br# [J]. China Mechanical Engineering, 2023, 34(17): 2065-2076.
[3]	YANG Jie, HU Qi, XIAO Ting, ZHANG Wenying, ZHANG Chaoyong. Energy Efficiency Modeling, Process Parameter Optimization and Sequencing Modeling Optimization of Cold Rolling Continuous Annealing Units Based on Energy Consumptions [J]. China Mechanical Engineering, 2020, 31(14): 1724-1732.
[4]	LI Yibing1,2;HUANG Weixing1;WU Rui1. Research on Multi-objective Green Flexible Job-shop Scheduling Based on Improved ABC Algorithm [J]. China Mechanical Engineering, 2020, 31(11): 1344-1350,1385.
[5]	YANG Yu;HUANG Min;WANG Zhenyu;ZHU Qibing. Solving Bi-objective FJSP Using Limited Stable Matching Strategy [J]. China Mechanical Engineering, 2018, 29(14): 1743-1750.
[6]	LI Yanwei;WANG Xiaogang;LI Yugui;HAN Peisheng. Hot Rolling Clad Symmetrical Billet for Producing High-chromiun Cast Iron/Low-carbon Steel Wear Resistant Composite Boards [J]. China Mechanical Engineering, 2018, 29(11): 1364-1368,1374.
[7]	HONG Huanhuan, ZHAO Yanwei, CHEN Weigang. Modeling of Multi-dimensional Correlation Function and Its Applications for Low Carbon Case Retrieval [J]. China Mechanical Engineering, 2017, 28(06): 688-694.
[8]	ZHU Chuanjun, QIU Wen, ZHANG Chaoyong, JIN Liangliang. Multi-objective Flexible Job Shop Dynamic Scheduling Strategy Aiming at Scheduling Stability and Robustness [J]. China Mechanical Engineering, 2017, 28(02): 173-182.
[9]	Wang Junliang, Zhang Jie, Qin Wei, Yin Li, Chen Dingfang. Robust Scheduling on Flexible Job Shop with Uncertain Processing Time [J]. China Mechanical Engineering, 2015, 26(5): 627-632.
[10]	Peng Jiangang, Liu Mingzhou, Zhang Xi, Zhang Mingxin, Ge Maogen. Discrete Free Search Based on Pareto-optimality for Multi-objective Flexible Job-shop Scheduling Problem [J]. China Mechanical Engineering, 2015, 26(5): 620-626.
[11]	Ba Li, Li Yan, Cao Yuan, Yang Mingshun, Liu Yong. Research on Flexible Job-shop Scheduling Problem with Consideration of Batch Splitting and Assembly [J]. China Mechanical Engineering, 2015, 26(23): 3200-3207.
[12]	Peng Jiangang, Liu Mingzhou, Zhang Mingxin, Zhang Xi. Review on Scheduling Algorithms for MOFJSP [J]. China Mechanical Engineering, 2014, 25(23): 3244-3254.
[13]	Guo Dengyue, Cheng Kai, Ding Hui, Yan Jihong, Ma Yunhui. An Investigation on Quantitative Analysis of Carbon Footprint in Centreless Grinding Process and Its Key Factors [J]. China Mechanical Engineering, 2014, 25(11): 1478-1485.
[14]	. Multi-granularity and Hierarchy Low-carbon Efficiency Analysis Method for Products [J]. China Mechanical Engineering, 2013, 24(17): 2390-2397.
[15]	CHEN Yong, RUAN Nie-Cong, LU Jian-Sha, WANG E-Liang. Flexible Job-Shop Scheduling Algorithm of Large Parts Based on Cellular Automata and Improved GA [J]. China Mechanical Engineering, 2012, 23(2): 177-184,190.