Improved Whale Optimization Algorithm of Scheduling Problem for Low Carbon Workshop
-
摘要: 针对传统柔性作业车间调度问题只考虑完工时间,设备利用率,完工成本等因素的局限,构建了以碳排放成本和完工时间成本加权和最小为目标的低碳柔性作业车间调度问题模型,并设计了一种改进的鲸鱼优化算法对其进行求解。首先,采用等长的两段式编码方式来表示柔性作业车间调度问题,引入基于ROV规则的转换机制,实现鲸鱼个体位置向量与调度解之间的相互转换。其次,采用基于一定比例的全局搜索、局部搜索和随机搜索的混合式种群初始化方法,生成一定质量的初始种群,同时设计了非线性收敛因子和自适应惯性权重系数来加强算法协调全局搜索和局部寻优的能力。再次,引入自适应调整搜索策略以提高算法跳出局部最优的能力。最后,通过实验数据验证了改进鲸鱼算法在求解低碳柔性作业车间调度问题方面的有效性。
-
关键词:
- 柔性作业车间调度问题 /
- 碳排放量 /
- 鲸鱼优化算法 /
- 个体位置向量
Abstract: Owing to the traditional flexible job shop scheduling problem (FJSP) has the limitations which only consider completion time, equipment utilization, and completion cost et al as the criterion, a low carbon FJSP model with the criterion of minimizing the weighted sum of carbon consumption cost and completion-time cost has been established, and an improved whale optimization algorithm (IWOA) has been proposed. Firstly, a two-segment string is used to describe the FJSP, and a conversion method based on the ranked-order-value (ROV) rule has been introduced to implement the conversion between the whale individual position vector and the scheduling solution. Secondly, a hybrid population initialization strategy based on a certain proportion of global search, local search and random search is used to generate the initial population with certain quality, and then, a nonlinear convergence factor (NFC) and an adaptive weight (AW) are introduced to coordinate the abilities of exploitation and exploration of the algorithm. Thirdly, an adaptive adjustment search strategy is employed to enhance the ability of exploitation of the algorithm. Finally, the experimental data have verified the effectiveness of the improved whale algorithm in solving the low-carbon FJSP. -
表 1 6×7的FJSP加工信息
工件 工序 加工时间(min)/单位时间内碳排放量(kg) M1 M2 M3 M4 M5 M6 M7 J1 O11 - 16/1.7 - 16/1.3 - 15/1.1 - O12 17/1.2 18/2.9 - 14/2.1 - - 16/1.6 O13 20/1.9 - 20/1.8 - 18/1.4 13/2 - O14 20/3 - 17/1.9 - 13/2.5 - 19/2 J2 O21 - 17/2.6 - 18/2.1 - 14/1.8 - O22 17/2.6 - 18/2.2 - 22/1.4 - - O23 19/2.5 17/1.8 - 21/2.1 19/2.4 17/2.1 19/2.5 J3 O31 18/2.2 - - 20/1.6 - - - O32 18/1.7 - 17/2 23/2.2 - 19/1.9 - O33 - 22/2.1 20/2 - - - 17/1.4 J4 O41 - - - - 16/1.7 - 18/1.6 O42 - - - 25/1.3 20/1.5 21/1.4 - J5 O51 19/2.1 - 18/2.2 - 16/2.5 - - O52 - 12/2.6 9/2.2 - - 10/2.1 - O53 - - - 10/1.9 13/1.7 - 8/2.2 O54 13/2.7 16/2.2 - - 14/1.5 - 12/1.9 O55 20/1.6 - - 19/2.3 - 22/2.4 - J6 O61 10/1.8 9/2.1 11/1.6 9/1.5 - 9/2.2 10/1.5 O62 - - 17/1.8 - 11/2.1 - - O63 14/2.3 - - 10/2.4 - 9/2.5 - O64 - 13/2.1 11/1.9 - - - 10/1.1 -
[1] 雷德明.基于新型教学优化算法的低碳柔性作业车间调度[J].控制与决策, 2017, 32(9):1621-1627 http://d.old.wanfangdata.com.cn/Periodical/kzyjc201709011Lei D M. Novel teaching-learning-based optimization algorithm for low carbon scheduling of flexible job shop[J]. Control and Decision, 2017, 32(9):1621-1627(in Chinese) http://d.old.wanfangdata.com.cn/Periodical/kzyjc201709011 [2] Ding J Y, Song S J, Wu C. Carbon-efficient scheduling of flow shops by multi-objective optimization[J]. European Journal of Operational Research, 2016, 248(3):758-771 doi: 10.1016/j.ejor.2015.05.019 [3] Mansouri S A, Aktas E, Besikci U. Green scheduling of a two-machine flowshop:trade-off between makespan and energy consumption[J]. European Journal of Operational Research, 2016, 248(3):772-788 http://cn.bing.com/academic/profile?id=bef1ba4990e094934ed75ec873ed0e20&encoded=0&v=paper_preview&mkt=zh-cn [4] Luo H, Du B, Huang G Q, et al. Hybrid flow shop scheduling considering machine electricity consumption cost[J]. International Journal of Production Economics, 2013, 146(2):423-439 doi: 10.1016/j.ijpe.2013.01.028 [5] 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[J]. Journal of Cleaner Production, 2016, 112:3361-3375 doi: 10.1016/j.jclepro.2015.09.097 [6] Yin L J, Li X Y, Gao L, et al. Energy-efficient job shop scheduling problem with variable spindle speed using a novel multi-objective algorithm[J]. Advances in Mechanical Engineering, 2017, 9(4):1-21 http://cn.bing.com/academic/profile?id=db909832ac95b85f4be6feacbb6b2cc5&encoded=0&v=paper_preview&mkt=zh-cn [7] Li J Q, Sang H Y, Han Y Y, et al. Efficient multi- objective optimization algorithm for hybrid flow shop scheduling problems with setup energy consumptions[J]. Journal of Cleaner Production, 2018, 181:584-598 doi: 10.1016/j.jclepro.2018.02.004 [8] 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 doi: 10.1109/ACCESS.2018.2866133 [9] 姜天华.基于灰狼优化算法的低碳车间调度问题[J].计算机集成制造系统, 2018, 24(10):2428-2435 http://d.old.wanfangdata.com.cn/Periodical/jsjjczzxt201810006Jiang T H. Low-carbon workshop scheduling problem based on grey wolf optimization[J]. Computer Integrated Manufacturing Systems, 2018, 24(10):2428-2435(in Chinese) http://d.old.wanfangdata.com.cn/Periodical/jsjjczzxt201810006 [10] Zhang C Y, Gu P H, Jiang P Y. Low-carbon scheduling and estimating for a flexible job shop based on carbon footprint and carbon efficiency of multi-job processing[J]. Proceedings of the Institution of Mechanical Engineers, Part B:Journal of Engineering Manufacture, 2015, 229(2):328-342 doi: 10.1177/0954405414527959 [11] Lei D M, Zheng Y L, Guo X P. A shuffled frog-leaping algorithm for flexible job shop scheduling with the consideration of energy consumption[J]. International Journal of Production Research, 2017, 55(11):3126-3140 doi: 10.1080/00207543.2016.1262082 [12] Mirjalili S, Lewis A. The whale optimization algorithm[J]. Advances in Engineering Software, 2016, 95:51-67 doi: 10.1016/j.advengsoft.2016.01.008 [13] Mafarja M M, Mirjalili S. Hybrid whaleoptimization algorithm with simulated annealing for featureselection[J]. Neurocomputing, 2017, 260:302-312 doi: 10.1016/j.neucom.2017.04.053 [14] Aljarah I, Faris H, Mirjalili S. Optimizing connection weights in neural networks using the whale optimization algorithm[J]. Soft Computing, 2018, 22(1):1-15 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=11c8467be5ea51c2c6ab2c9d59266f58 [15] Abdel-Basset M, Manogaran G, El-Shahat D, et al. A hybrid whale optimization algorithm based on local search strategy for the permutation flow shop scheduling problem[J]. Future Generation Computer Systems, 2018, 85:129-145 doi: 10.1016/j.future.2018.03.020 [16] Jiang T H, Zhang C, Zhu H Q, et al. Energy-Efficient scheduling for a job shop using an improved whale optimization algorithm[J]. Mathematics, 2018, 6(11):220-239 doi: 10.3390/math6110220 [17] Yuan Y, Xu H, Yang J D. A hybrid harmony search algorithm for the flexible job shop scheduling problem[J]. Applied Soft Computing Journal, 2013, 13(7):3259-3272 doi: 10.1016/j.asoc.2013.02.013 [18] 张国辉, 高亮, 李培根, 等.改进遗传算法求解柔性作业车间调度问题[J].机械工程学报, 2009, 45(7):145-151 http://d.old.wanfangdata.com.cn/Periodical/jxgcxb200907023Zhang G H, Gao L, Li P G, et al. Improved genetic algorithm for the flexible job-shop scheduling problem[J]. Journal of Mechanical Engineering, 2009, 45(7):145-151(in Chinese) http://d.old.wanfangdata.com.cn/Periodical/jxgcxb200907023 [19] 何庆, 魏康园, 徐钦帅.基于混合策略改进的鲸鱼优化算法[J].计算机应用研究, 2019, 36(12):3647-3651, 3665 http://d.old.wanfangdata.com.cn/Periodical/jsjyyyj201912027He Q, Wei K Y, Xu Q S. Mixed strategy based improved whale optimization algorithm[J]. Application Research of Computers, 2019, 36(12):3647-3651, 3665(in Chinese) http://d.old.wanfangdata.com.cn/Periodical/jsjyyyj201912027 [20] 周敏, 李太勇.粒子群优化算法中的惯性权值非线性调整策略[J].计算机工程, 2011, 37(5):204-206 doi: 10.3969/j.issn.1000-3428.2011.05.069Zhou M, Li T Y. Nonlinear adjustment strategy of inertia weight in particle swarm optimization algorithm[J]. Computer Engineering, 2011, 37(5):204-206(in Chinese) doi: 10.3969/j.issn.1000-3428.2011.05.069 [21] Kaveh A, Ilchi Ghazaan M. Enhanced whale optimization algorithm for sizing optimization of skeletal structures[J]. Mechanics Based Design of Structures and Machines, 2017, 45(3):345-362 doi: 10.1080/15397734.2016.1213639 [22] Kacem I, Hammadi S, Borne P. Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part C:Applications and Reviews, 2002, 32(1):1-13 doi: 10.1109/TSMCC.2002.1009117 [23] Ziaee M. A heuristic algorithm for solving flexible job shop scheduling problem[J]. The International Journal of Advanced Manufacturing Technology, 2014, 71(1-4):519-528 doi: 10.1007/s00170-013-5510-z [24] Brandimarte P. Routing and scheduling in a flexible job shop by tabu search[J]. Annals of Operations Research, 1993, 41(3):157-183 doi: 10.1007/BF02023073 [25] Nouiri M, Bekrar A, Jemai A, et al. An effective and distributed particle swarm optimization algorithm for flexible job-shop scheduling problem[J]. Journal of Intelligent Manufacturing, 2018, 29(3):603-615 doi: 10.1007/s10845-015-1039-3