A multi-objective green flexible job shop scheduling method based on improved NSGA-II algorithm
-
摘要: 针对多目标绿色柔性作业车间调度问题，建立了以最小化最大完工时间、总负荷和总能耗为优化目标的多目标优化模型，提出了一种带有自适应交叉变异算子和学习机制的改进NSGA-II多目标优化算法。该算法通过机器和工序的两级编码机制，使用基于全局、局部和随机选择的非支配排序选择策略得到初始种群；采用具有自适应算子的混合交叉变异策略进行迭代，提高算法的全局搜索能力；引入分布函数来改进精英保留策略提高种群的多样性；通过学习机制进行邻域搜索提高算法的局部搜索能力。最后，采用基准测试算例Brandimarte以及Kacem数据集对算法进行测试，结果表明采用改进的NSGA-II算法求解多目标绿色柔性作业车间调度问题具有求解精度高、收敛速度快以及解集多样性好的优点。
-
关键词:
- 柔性作业车间调度问题 /
- 改进NSGA-II /
- 自适应算子 /
- 改进精英保留策略
Abstract: For the multi-objective green flexible job shop scheduling problem, a multi-objective optimization model with minimizing the maximum completion time, total load and total energy consumption as objectives is established, and an improved NSGA-II multi-objective optimization algorithm with adaptive crossover mutation operator and learning mechanism is proposed. In this algorithm, the initial population is obtained by the non-dominated sorting selection strategy based on global, local and random selection through a two-level coding mechanism of machine and process. Hybrid crossover mutation strategy with adaptive operator is adopted to improve the global search performance of the algorithm. A distribution function is introduced to improve the elite preserving strategy and the diversity of population. Neighborhood search is carried out by learning mechanism to improve the local search capability of the algorithm. Finally, Brandimarte and Kacem data sets are used to test the algorithm. The results show that the improved NSGA-II algorithm for solving multi-objective green flexible job-shop scheduling problems has the advantages of high precision, fast convergence and good diversity of solution sets, which can guide the practical production decisions. -
表 1 符号定义表
符号 含义 n 工件数量 m 机器数量 $ {n}_{i} $ 工件i包含的工序数 $ {O}_{i,j} $ 工件i的第j道工序 $ {J}_{i} $ 工件i的工序总和 h 工序的序号 $ {M}_{i,j} $ 工序$ {O}_{i,j} $的可选机器集 $ {t}_{i,j,k} $ 工序$ {O}_{i,j} $在机器k上的加工时间 $ {s}_{i,j} $ 工序$ {O}_{i,j} $的加工开始时间 $ {f}_{i,j} $ 工序$ {O}_{i,j} $的加工完成时间 ${C}_{{\rm{max}}}$ 所有工件的总完工时间 M 一个非常大的正数 $ {e}_{i,j,k} $ 工序$ {O}_{i,j} $在机器$ {M}_{k} $上单位时间加工能耗 $ {p}_{k} $ 机器$ {M}_{k} $在空载情况下的单位时间能耗 $ {f}_{1}\left(x\right) $ 完工时间 $ {f}_{2}\left(x\right) $ 机器总负荷 $ {f}_{3}\left(x\right) $ 总能耗 $ {f}_{4}\left(x\right) $ 瓶颈机器负荷 
下载: 导出CSV
表 3 Kacem算例结果对比表
算例 目标 INSGA-II PCP MBB NSGA-II 8*8 F1 15 16 16 17 16 15 16 15 17 14 17 16 F2 13 11 12 11 12 13 11 13 11 10 15 13 F3 73 77 75 75 78 76 82 73 75 78 73 79 10*10 F1 8 7 7 8 9 8 7 9 F2 6 6 5 7 5 6 7 8 F3 41 42 43 44 43 41 43 41 15*10 F1 16 12 13 11 11 12 15 F2 10 10 10 11 10 11 12 F3 91 93 93 95 98 91 93
下载: 导出CSV
表 4 MK04算例Pareto最优解集表
序号 f1 f2 f3 序号 f1 f2 f3 1 118 333 402.7 13 99 340 390.6 2 112 337 391.8 14 98 336 396.8 3 112 336 392.6 15 98 337 396 4 111 334 404 16 93 343 387.3 5 111 333 404.8 17 93 342 388.1 6 106 340 388.5 18 92 339 393.5 7 106 339 389.3 19 92 340 392.7 8 105 337 393.9 20 91 345 385 9 105 336 394.7 21 91 346 384.2 10 104 333 408.1 22 86 342 390.2 11 100 343 385.2 23 86 343 389.4 12 99 339 391.4 24 85 339 396.6
下载: 导出CSV
-
[1] Liu Z, Guan D, Wei W, et al. Reduced carbon emission estimates from fossil fuel combustion and cement production in China[J]. Nature, 2015, 524(7565): 335-338. doi: 10.1038/nature14677 [2] Li M, Lei D, Cai J. Two-level imperialist competitive algorithm for energy-efficient. hybrid flow shop schedulin- g problem with relative importance of objectives[J]. Swarm and Evolutionary Computation, 2019, 49: 34-43. doi: 10.1016/j.swevo.2019.05.006 [3] Msc M, Phd J B. Multi-objective green flow shop scheduling problem under uncertainty: Estimation of distribution algorithm[J]. Journal of Cleaner Produciton, 2020, 251: 119-734. [4] 杨帆, 方成刚, 洪荣晶, 等. 改进遗传算法在车间调度问题中的应用[J]. 南京工业大学学报:自然科学版, 2021: 1-8. [5] 梁晓磊, 马千慧, 李章洪, 等. 考虑多时间约束和机器效率的柔性作业车间调度问题建模及优化[J]. 制造技术与机床, 2021(10): 114-122. doi: 10.19287/j.cnki.1005-2402.2021.10.023 [6] Chang H C, Liu T K. Optimisation of distributed manufa- cturing flexible job shop scheduling by using hybrid g enetic algorithms[J]. Journal of Intelligent Manufacturing, 2015: 1-14. [7] 文笑雨, 孙海强, 李浩. 基于改进NSGA2的多目标绿色作业车间调度问题研究[J]. 河南理工大学学报:自然科学版, 2020, 39(5): 120-129. [8] 张国辉, 张海军, 张理涛. 改进遗传算法求解低碳约束的柔性车间调度问题[J]. 组合机床与自动化加工技术, 2018(6): 180-184. doi: 10.13462/j.cnki.mmtamt.2018.06.045 [9] Frutos M, Olivera A C, F Tohmé. A memetic algorithm based on a NSGA-II scheme for the flexible job-shop scheduling problem[J]. Annals of Operations Research, 2010, 181(1): 745-765. doi: 10.1007/s10479-010-0751-9 [10] 陈辅斌, 李忠学, 杨喜娟. 基于改进NSGA2算法的多目标柔性作业车间调度[J]. 工业工程, 2018, 21(2): 55-61. doi: 10.3969/j.issn.1007-7375.e17-3276 [11] 杜晓亮, 张楠, 孟凡云, 等. 改进NSGA2算法求解柔性作业车间调度问题[J]. 组合机床与自动化加工技术, 2022(5): 182-186. doi: 10.13462/j.cnki.mmtamt.2022.05.044 [12] Wang J J, Wang L. Decoding methods for the flow shop scheduling with peak power consumption constraints[J]. International Journal of Production Research, 2019, 57(9-10): 3200-3218. [13] Alzahrani J S. Multi-objective job shop scheduling using pre-emptive constraint procedure[J]. American Journal of Modeling and Optimization, 2019, 7(1): 8-13. doi: 10.12691/ajmo-7-1-2 [14] Soto C, Dorronsoro B, Fraire H. Solving the multi-objecti- ve flexible job shop scheduling problem with a novel parallel branch and bound algorithm[J]. Swarm and Evolutionary Computation, 2020, 53: 100632. doi: 10.1016/j.swevo.2019.100632 -
下载:
点击查看大图
图(11) / 表(4)
计量
- 文章访问数: 104
- HTML全文浏览量: 53
- PDF下载量: 36
- 被引次数: 0
