Research on Flexible Job Shop Scheduling Problem With Total Energy Consumption Constraint
-
摘要: 针对具有总能耗约束的柔性作业车间调度问题（Flexible job shop scheduling problem，FJSP），提出一种基于帝国竞争算法（Imperialist competitive algorithm，ICA）和变邻域搜索（Variable neighborhood search，VNS）的双阶段算法，该算法在总能耗不超过给定阈值的条件下最小化Makespan和总延迟时间.由于能耗约束不是总能满足且阈值往往难以事先给定，为此，第一阶段，首先，将原问题转化为具有Makespan、总延迟时间和总能耗的三目标FJSP，然后，利用初始帝国构建和帝国竞争的新策略设计一种ICA对问题求解，并根据ICA的结果确定总能耗阈值；第二阶段，应用解的比较新策略、非劣解集更新方法和当前解周期性更新，构建VNS对原问题求解.计算实验和结果分析表明，两阶段算法对于所研究的问题搜索能力强.Abstract: A two-phase algorithm based on imperialist competitive algorithm (ICA) and variable neighborhood search (VNS) is proposed for the flexible job shop scheduling problem (FJSP) with total energy consumption constraint. The goal is to minimize the makespan and total tardiness under the condition that total energy consumption does not exceed a given threshold. Energy consumption constraint is not always met and a threshold is difficult to be decided in advance, so in the first phase, the original problem is converted into FJSP with makespan, total tardiness and total energy consumption, and an ICA is used to solve the converted problem based on some new strategies for initial empires and imperialist competition. An energy consumption threshold is obtained in terms of the results of ICA. In the second phase, a VNS is presented for the original FJSP by using new methods for comparing solutions and updating the non-dominated set and renewing current solution periodically. Computational experiments are conducted and the result shows that the two-phase algorithm has strong search ability for the considered FJSP.1) 本文责任编委 鲁仁全
-
表 1 $\delta $的设置
Table 1 The setting on $\delta $
$\delta $ Instances $\delta $ Instances $[0.5, 0.7]$ MK01, MK03-05 $[1.0, 1.5]$ DP1-12 $[0.3, 0.5]$ MK02, 06, 08-10 $[1.2, 1.6]$ MK11-15 $[0, 1, 0.3]$ Ka4$\times $5, 10$\times $7, 15$\times $10 $[0.7, 0.9]$ MK07 $[1.2, 1.7]$ DP13-18 $[0.05, 0.2]$ Ka10$\times $10 
下载: 导出CSV
表 2 阈值的确定
Table 2 Decision on threshold
所有$Q_i $ 大于$\bar {Q}$的$Q_i $ 剩余的$Q_i $ 216.7, 198.9, 227.3, 218.0 230.2, 231.6 231.6, 245.9 230.2, 224.6, 231.6, 244.4 244.4, 237.7 237.7 218.9, 208.2, 237.7, 221.4 253.4, 245.9 253.4 223.1, 253.4, 245.9, 232.4 232.4, 254.1 232.4 207.6, 254.1, 284.1, 216.4 284.1 284.1
下载: 导出CSV
表 3 总能耗阈值和三种算法的ATEC和MTEC
Table 3 Total energy consumption threshold and ATEC and MTEC of three algorithms
Instance $Q_{EC} $ 两阶段算法 NSGA-Ⅱ VNS ATEC MTEC ATEC MTEC ATEC MTEC Ka4$\times $5 152.3 96.154 95.259 96.080 95.259 95.259 95.259 Ka10$\times $7 245.9 196.27 185.41 194.39 193.26 200.52 193.50 Ka10$\times $10 159.5 124.81 121.26 130.29 128.24 132.17 124.26 Ka15$\times $10 443.3 313.85 302.87 325.01 321.45 365.49 354.56 MK01 682.4 653.38 650.79 666.54 664.84 655.55 654.41 MK02 550.7 509.51 496.17 525.17 519.14 508.72 506.36 MK03 3 597 314 8.6 3 128.2 3 311.5 3 291.1 3 278.4 3 235.5 MK04 1 191 1 083.4 1 064.4 1 097.5 1 078.4 1 086.4 1 074.9 MK05 2 748 2 628.1 2 619.8 2 588.0 2 578.7 2 648.4 2 631.6 MK06 2 349 2 162.8 2 145.9 2 189.4 2 168.5 2 127.0 2 106.3 MK07 1 728 1 504.2 1 486.0 1 567.6 1 561.1 1 524.6 1 517.7 MK08 10 156 9 786.4 9 713.1 10 004 9 976.4 9 747.8 9 747.8 MK09 9 082 8 627.0 8 604.9 8 996.0 8 961.3 8 622.3 8 572.3 MK10 9 728 8 537.1 8 536.2 8 991.6 8 955.6 9 022.7 8 972.6 MK11 12 890 12 415 12 276 12 640 12 577 12 417 12 353 MK12 14 933 14 291 14 220 14 314 14 148 14 214 14 109 MK13 14 202 13 131 13 104 13 845 13 763 13 382 13 310 MK14 16 985 14 916 14 856 15 307 15 239 15 020 14 981 MK15 17 000 13 793 13 656 13 877 13 786 13 643 13 612 DP1 34 534 33 829 33 745 34 117 34 026 33 902 33 758 DP2 40 332 38 574 38 394 38 874 38 813 38 654 38 512 DP3 36 428 35 271 35 086 35 701 35 504 35 367 35 215 DP4 36 880 36 171 35 656 36 077 35 742 36 225 36 089 DP5 40 085 38 815 38 766 39 428 39 252 38 882 38 619 DP6 37 091 35 882 35 729 36 445 36 162 36 185 35 897 DP7 26 373 60 667 60 542 61 033 60 989 60 707 60 673 DP8 52 422 49 948 49 870 50 638 50 627 50 722 50 527 DP9 64 539 62 395 62 232 63 458 63 202 63 282 62 966 DP10 60 350 58 580 58 133 59 242 59 145 59 277 59 070 DP11 57 613 55 548 55 373 56 332 56 260 56 118 55 612 DP12 60 711 58 022 57 981 59 288 58 947 58 260 58 220 DP13 86 142 84 382 84 335 85 046 85 027 85 200 85 062 DP14 83 000 80 940 80 803 82 332 82 135 81 889 81 787 DP15 73 000 70 977 70 631 72 033 71 854 71 800 71 702 DP16 80 468 78 790 78 584 79 976 79 878 79 417 79 266 DP17 86 677 84 886 84 798 85 963 85 675 85 394 85 324 DP18 86 330 84 114 83 685 84 951 84 785 85 045 84 679
下载: 导出CSV
表 4 三种算法的计算结果
Table 4 Computational results of three algorithms
Instance DIR $\rho _l $ 两阶段算法 NSGA-Ⅱ VNS 两阶段算法 NSGA-Ⅱ VNS Ka4$\times $5 1.235 0.890 1.125 0.307 0.222 0.370 Ka10$\times $7 15.10 0.000 20.65 0.000 1.000 0.000 Ka10$\times $10 0.00 40.34 0.086 0.969 0.000 0.031 Ka15$\times $10 0.256 9.456 35.88 0.889 0.111 0.000 MK01 0.446 6 121 7.305 0.694 0.000 0.306 MK02 0.00 3 731 9.326 1.000 0.00 0.00 MK03 0.000 51.90 30.71 1.000 0.00 0.00 MK04 2 763 2 930 1 652 0.600 0.150 0.250 MK05 3.119 59.04 7.024 0.667 0.000 0.333 MK06 18.15 45.79 0.00 0.00 0.00 1.000 MK07 0.000 31.49 9.899 1.000 0.00 0.00 MK08 0.000 25.04 10.86 1.000 0.00 0.00 MK09 0.000 49.76 10.23 1.000 0.00 0.00 MK10 0.000 38.24 18.00 1.000 0.00 0.00 MK11 13.42 3 265 1 325 0.588 0.000 0.412 MK12 0.00 3 701 1 542 1.000 0.00 0.00 MK13 0.000 64.40 32.30 1.000 0.00 0.00 MK14 0.000 60.04 23.99 1.000 0.00 0.00 MK15 0.297 39.99 19.86 0.944 0.000 0.056 DP1 0.00 2 528 1 324 1.000 0.00 0.00 DP2 7.507 39.16 4.663 0.550 0.000 0.45 DP3 1.424 37.62 5.638 0.915 0.000 0.085 DP4 1 427 2 911 7 302 0.750 0.000 0.250 DP5 5.861 50.89 4.452 0.583 0.000 0.417 DP6 0.000 52.16 12.64 1.000 0.00 0.00 DP7 0.000 33.53 19.41 1.000 0.00 0.00 DP8 0.652 42.3 20.47 0.988 0.000 0.012 DP9 0.000 66.43 34.33 1.000 0.00 0.00 DP10 0.543 4 836 11.20 0.950 0.000 0.050 DP11 0.000 34.21 14.03 1.000 0.00 0.00 DP12 2.597 67.65 4.814 0.667 0.000 0.333 DP13 0.00 3 326 20.31 1.000 0.00 0.00 DP14 0.258 46.08 1264 0.981 0.000 0.019 DP15 0.000 46.20 19.04 1.000 0.00 0.00 DP16 0.000 67.34 44.41 1.000 0.00 0.00 DP17 0.000 34.69 16.09 1.000 0.00 0.00 DP18 0.000 39.64 21.59 1.000 0.00 0.00
下载: 导出CSV
表 5 三种算法的计算时间
Table 5 Comparisons on the computational times of three algorithms
Instance Running time (s) Instance Running time (s) 两阶段算法 NSGA-Ⅱ VNS 两阶段算法 NSGA-Ⅱ VNS Ka4$\times $5 0.688 0.666 0.272 DP1 10.74 10.85 13.03 Ka10$\times $7 1.901 3.341 1.795 DP2 12.91 11.35 14.52 Ka10$\times $10 1.879 3.323 1.984 DP3 11.59 10.96 14.67 Ka15$\times $10 3.339 4.337 3.417 DP4 11.83 11.49 11.76 MK01 2.791 4.068 3.136 DP5 11.21 10.94 11.73 MK02 2.799 4.037 3.358 DP6 10.84 11.18 11.47 MK03 7.351 7.595 8.498 DP7 18.33 18.09 19.68 MK04 4.110 5.141 4.895 DP8 18.26 17.46 19.84 MK05 6.740 5.335 6.600 DP9 17.02 17.80 18.79 MK06 7.654 6.037 7.419 DP10 18.73 17.84 20.16 MK07 5.238 6.072 5.325 DP11 17.58 18.02 19.78 MK08 14.18 13.98 15.31 DP12 17.75 17.92 19.82 MK09 12.54 14.84 14.87 DP13 31.54 31.94 28.87 MK10 12.51 13.16 14.82 DP14 30.24 32.14 27.82 MK11 12.29 12.27 12.39 DP15 29.41 31.70 28.97 MK12 12.84 13.44 14.93 DP16 31.74 33.56 27.42 MK13 13.20 13.62 15.08 DP17 31.13 41.84 28.07 MK14 16.63 16.77 18.95 DP18 29.38 32.96 28.71 MK15 16.14 16.60 18.65
下载: 导出CSV
-
[1] Brucker R, Schlie R. Job-shop scheduling with multi-purpose machines. Computing, 1990, 45(4):369-375 doi: 10.1007/BF02238804 [2] Kacem I, Hammadi S, Borne P. Pareto-optimality approach for flexible job-shop scheduling problems:hybridization of evolutionary algorithms and fuzzy logic. Mathematics and Computers in Simulation, 2002, 60(3-5):245-276 doi: 10.1016/S0378-4754(02)00019-8 [3] Gao J, Gen M, Sun L Y, Zhao X H. A hybrid of genetic algorithm and bottleneck shifting for multiobjective flexible job shop scheduling problems. Computers & Industrial Engineering, 2007, 53(1):149-162 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=2a96c53ae0265c4f5ac1c25a3529ef27 [4] Chiang T C, Lin H J. A simple and effective evolutionary algorithm for multiobjective flexible job shop scheduling. International Journal of Production Economics, 2013, 141(1):87-98 doi: 10.1016/j.ijpe.2012.03.034 [5] Yuan Y, Xu H. Multiobjective flexible job shop scheduling using memetic algorithms. IEEE Transaction on Automation Science & Engineering, 2015, 12(1):336-353 http://d.old.wanfangdata.com.cn/NSTLQK/NSTL_QKJJ0234915959/ [6] Rohaninejad M, Kheirkhah A, Fattahi P, Vahedi-Nouri B. A hybrid multi-objective genetic algorithm based on the ELECTRE method for a capacitated flexible job shop scheduling problem. The International Journal of Advanced Manufacturing Technology, 2015, 77(1-4):51-66 doi: 10.1007/s00170-014-6415-1 [7] Li J Y, Huang Y, Niu X W. A branch population genetic algorithm for dual-resource constrained job shop scheduling problem. Computers & Industrial Engineering, 2016, 102:113-131 http://www.sciencedirect.com/science/article/pii/S0360835216303813 [8] Ahmadi E, Zandieh M, Farrokh M, Emami S M. A multi objective optimization approach for flexible job shop scheduling problem under random machine breakdown by evolutionary algorithms. Computers & Operations Research, 2016, 73:56-66 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=80f01cd8a69ff45e37a8aab25b3d7ff3 [9] Shen X N, Han Y, Fu J Z. Robustness measures and robust scheduling for multi-objective stochastic flexible job shop scheduling problems. Soft Computing, 2017, 21(21):6531-6554 doi: 10.1007/s00500-016-2245-4 [10] Rohaninejad M, Sahraeian R, Nouri B V. Multi-objective optimization of integrated lot-sizing and scheduling problem in flexible job shops. RAIRO-Operations Research, 2015, 50(3):587-609 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=fbd7e8b974e989af6947a2f05ce099b5 [11] Singh M R, Singh M, Mahapatra S S, Jagadev N. Particle swarm optimization algorithm embedded with maximum deviation theory for solving multi-objective flexible job shop scheduling problem. International Journal of Advanced Manufacturing Technology, 2016, 85(9-12):2353-2366 doi: 10.1007/s00170-015-8075-1 [12] Gao K Z, Suganthan P N, Pan Q K, Chua T J, Cai T X, Chong C S. Pareto-based grouping discrete harmony search algorithm for multi-objective flexible job shop scheduling. Information Sciences, 2014, 289:76-90 doi: 10.1016/j.ins.2014.07.039 [13] Li J Q, Pan Q K, Tasgetiren M F. A discrete artificial bee colony algorithm for the multi-objective flexible job-shop scheduling problem with maintenance activities. Applied Mathematical Modelling, 2014, 38(3):1111-1132 doi: 10.1016/j.apm.2013.07.038 [14] Li J Q, Pan Q K, Suganthan P N, Chua T J. A hybrid tabu search algorithm with an efficient neighborhood structure for the flexible job shop scheduling problem. International Journal of Advanced Manufacturing Technology, 2011, 52(5-8):683-698 doi: 10.1007/s00170-010-2743-y [15] Jia S, Hu Z H. Path-relinking tabu search for the multi-objective flexible job shop scheduling problem. Computers & Operations Research, 2014, 47:11-26 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=8633135d13caf01d3bd4a8eba7e48685 [16] Bagheri A, Zandieh M. Bi-criteria flexible job-shop scheduling with sequence-dependent setup times-variable neighborhood search approach. Journal of Manufacturing Systems, 2011, 30(1):8-15 doi: 10.1016/j.jmsy.2011.02.004 [17] Li J Q, Pan Q K, Xie S X. An effective shuffled frog-leaping algorithm for multi-objective flexible job shop scheduling problems. Applied Mathematics and Computation, 2012, 218(18):9353-9371 doi: 10.1016/j.amc.2012.03.018 [18] Wang L, Wang S Y, Liu M. A Pareto-based estimation of distribution algorithm for the multi-objective flexible job-shop scheduling problem. International Journal of Production Research, 2013, 51(12):3574-3592 doi: 10.1080/00207543.2012.752588 [19] Tang D B, Dai M. Energy-efficient approach to minimizing the energy consumption in an extended job-shop scheduling problem. Chinese Journal of Mechanical Engineering, 2015, 28(5):1048-1055 doi: 10.3901/CJME.2015.0617.082 [20] Liu Y, Tiwari A. An investigation into minimising total energy consumption and total completion time in a flexible job shop for recycling carbon fiber reinforced polymer. Procedia CIRP, 2015, 29:722-727 doi: 10.1016/j.procir.2015.01.063 [21] He Y, Li Y F, Wu T, Sutherland J W. An energy-responsive optimization method for machine tool selection and operation sequence in flexible machining job shops. Journal of Cleaner Production, 2015, 87:245-254 doi: 10.1016/j.jclepro.2014.10.006 [22] 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 [23] 蒋增强, 左乐.低碳策略下的多目标柔性作业车间调度.计算机集成制造系统, 2015, 21(4):1023-1031 http://d.old.wanfangdata.com.cn/Periodical/jsjjczzxt201504017Jiang Zeng-Qiang, Zuo Le. Multi-objective flexible job-shop scheduling based on low-carbon strategy. Computer Integrated Manufacturing Systems, 2015, 21(4):1023-1031 http://d.old.wanfangdata.com.cn/Periodical/jsjjczzxt201504017 [24] 唐立力.求解低碳调度问题的改进型候鸟优化算法.计算机工程与应用, 2016, 52(17):166-171 doi: 10.3778/j.issn.1002-8331.1510-0255Tang Li-Li. Improved migrating birds optimization algorithm to solve low-carbon scheduling problem. Computer Engineering and Applications, 2016, 52(17):166-171 doi: 10.3778/j.issn.1002-8331.1510-0255 [25] Yin L J, Li X Y, Gao L, Lu C, Zhang Z. A novel mathematical model and multi-objective method for the low-carbon flexible job shop scheduling problem. Sustainable Computing:Informatics and Systems, 2017, 13:15-30 doi: 10.1016/j.suscom.2016.11.002 [26] 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. International Journal of Production Research, 2017, 55(11):3126-3140 doi: 10.1080/00207543.2016.1262082 [27] 雷德明.基于新型教学优化算法的低碳柔性作业车间调度.控制与决策, 2017, 32(9):1621-1627 http://d.old.wanfangdata.com.cn/Periodical/kzyjc201709011Lei De-Ming. Novel teaching-learning-based optimization algorithm for low carbon scheduling of flexible job shop. Control and Decision, 2017, 32(9):1621-1627 http://d.old.wanfangdata.com.cn/Periodical/kzyjc201709011 [28] Deb K, Pratap A, Agarwal S, Meyarivan T. A fast and elitist multiobjective genetic algorithm:NSGA-Ⅱ. IEEE Transactions on Evolutionary Computation, 2002, 6(2):182-197 doi: 10.1109/4235.996017 [29] Hosseini S, Khaled A A. A survey on the imperialist competitive algorithm metaheuristic:implementation in engineering domain and directions for future research. Applied Soft Computing, 2014, 24:1078-1094 doi: 10.1016/j.asoc.2014.08.024 [30] Lian K L, Zhang C Y, Gao L, Shao X Y. Single row facility layout problem using an imperialist competitive algorithm. In:Proceedings of the 41st International Conference on Computers & Industrial Engineering. Los Angeles, USA:Elsevier, 2011. 578-586 [31] Hosseini S, Khaled A A, Vadlamani S. Hybrid imperialist competitive algorithm, variable neighborhood search, and simulated annealing for dynamic facility layout problem. Neural Computing and Applications, 2014, 25(7-8):1871-1885 doi: 10.1007/s00521-014-1678-x [32] Karimi N, Zandieh M, Najafl A A. Group scheduling in flexible flow shops:a hybridised approach of imperialist competitive algorithm and electromagnetic-like mechanism. International Journal of Production Research, 2011, 49(16):4965-4977 doi: 10.1080/00207543.2010.481644 [33] Behnamian J, Zandieh M. A discrete colonial competitive algorithm for hybrid flow shop scheduling to minimize earliness and quadratic tardiness penalties. Expert Systems with Applications, 2011, 38(12):14490-14498 doi: 10.1016/j.eswa.2011.04.241 [34] Goldansaz S M, Jolai F, Anaraki A H Z. A hybrid imperialist competitive algorithm for minimizing makespan in a multi-processor open shop. Applied Mathematical Modelling, 2013, 37(23):9603-9616 doi: 10.1016/j.apm.2013.05.002 [35] Naderi B, Yazdani M. A model and imperialist competitive algorithm for hybrid flow shops with sublots and setup times. Journal of Manufacturing Systems, 2014, 33(4):647-653 doi: 10.1016/j.jmsy.2014.06.002 [36] Matic A, Osmani V, Mayora-Ibarra O. Analysis of social interactions through mobile phones. Mobile Networks and Applications, 2012, 17(6):808-819 doi: 10.1007/s11036-012-0400-4 [37] Karimi S, Ardalan Z, Naderi B, Mohammadi M. Scheduling flexible job-shops with transportation times:mathematical models and a hybrid imperialist competitive algorithm. Applied Mathematical Modelling, 2017, 41:667-682 doi: 10.1016/j.apm.2016.09.022 [38] Zhou W, Yan J J, Li Y, Xia C M, Zheng J R. Imperialist competitive algorithm for assembly sequence planning. International Journal of Advanced Manufacturing Technology, 2013, 67(9-12):2207-2216 doi: 10.1007/s00170-012-4641-y [39] Wang B X, Guan Z L, Li D S, Zhang C Y, Chen L. Two-sided assembly line balancing with operator number and task constraints:a hybrid imperialist competitive algorithm. International Journal of Advanced Manufacturing Technology, 2014, 74(5-8):791-805 doi: 10.1007/s00170-014-5816-5 [40] 张鑫龙, 郑秀万, 肖汉, 李伟.一种求解旅行商问题的新型帝国竞争算法.控制与决策, 2016, 31(4):586-592 http://d.old.wanfangdata.com.cn/Periodical/kzyjc201604002Zhang Xin-Long, Zheng Xiu-Wan, Xiao Han, Li Wei. A new imperialist competitive algorithm for solving TSP problem. Control and Decision, 2016, 31(4):586-592 http://d.old.wanfangdata.com.cn/Periodical/kzyjc201604002 [41] Lei D M. Simplified multi-objective genetic algorithms for stochastic job shop scheduling. Applied Soft Computing, 2011, 11(8):4991-4996 doi: 10.1016/j.asoc.2011.06.001 [42] Afruzi E N, Najafi A A, Roghanian E, Mazinani M. A multi-objective imperialist competitive algorithm for solving discrete time, cost and quality trade-off problems with mode-identity and resource-constrained situations. Computers & Operations Research, 2014, 50:80-96 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=458b4c42f5fcfd3da9ca411187242f38 [43] Bayareh M, Mohammadi M. Multi-objective optimization of a triple shaft gas compressor station using Imperialist Competitive Algorithm. Applied Thermal Engineering, 2016, 109:384-400 doi: 10.1016/j.applthermaleng.2016.08.089 [44] Kemmoé S, Lamy D, Tchernev N. A job-shop with an energy threshold issue considering operations with consumption peaks. IFAC-PagesOnLine, 2015, 28(3):788-793 http://www.sciencedirect.com/science/article/pii/S2405896315004188 [45] Brandimarte P. Routing and scheduling in a flexible job shop by tabu search. Annals of Operations Research, 1993, 41(3):157-183 doi: 10.1007/BF02023073 [46] Dauzére-Pérés S, Paulli J. An integrated approach for modeling and solving the general multiprocessor job-shop scheduling problem using tabu search. Annals of Operations Research, 1997, 70:281-306 doi: 10.1023/A:1018930406487 [47] Knowles J, Corne D. On metrics for comparing nondominated sets. In:Proceedings of the 2002 Congress on Evolutionary Computation. Honolulu, HI, USA:IEEE, 2002. 711-716 [48] Lei D M. Pareto archive particle swarm optimization for multi-objective fuzzy job shop scheduling problems. International Journal of Advanced Manufacturing Technology, 2008, 37(1-2):157-165 doi: 10.1007/s00170-007-0945-8 -
