面向可持續生產(chǎn)中多任務(wù)調度的雙重增強模因算法
doi: 10.16383/j.aas.c230446
-
1.
湖南大學(xué)電氣與信息工程學(xué)院 長(cháng)沙 410082
-
2.
同濟大學(xué)電子與信息工程學(xué)院 上海 201804
基金項目: 湖南創(chuàng )新型省份建設科技重大專(zhuān)項 (2021GK1010), 國家自然科學(xué)基金 (62293510), 湖南省自然科學(xué)基金 (2023JJ30162), 岳麓山工業(yè)創(chuàng )新中心重大項目 (2023YCII0102), 湖南省教育廳科學(xué)研究項目?jì)?yōu)秀青年項目 (23B0029) 資助
Dual-enhanced Memetic Algorithm for Multi-task Scheduling in Sustainable Production
-
1.
College of Electrical and Information Engineering, Hunan University, Changsha 410082
-
2.
College of Electronics and Information Engineering, Tongji University, Shanghai 201804
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)
-
摘要: 從經(jīng)濟、環(huán)境和社會(huì )3個(gè)維度, 全面提升生產(chǎn)調度方案的可持續性具有重要意義. 針對并行機生產(chǎn)場(chǎng)景, 建立考慮機器指派、加工順序、人員安排以及開(kāi)關(guān)機控制等4種決策任務(wù)的調度模型. 為實(shí)現對復雜決策空間的高效尋優(yōu), 提出一種融合兩種局部?jì)?yōu)化策略的雙重增強模因算法(Dual-enhanced memetic algorithm, DMA)求解模型. 從隨機更新角度, 針對不同決策任務(wù), 構造單步變鄰域搜索(One-step variable neighborhood search, 1S-VNS)策略. 從定向優(yōu)化角度, 分析目標和關(guān)鍵任務(wù)之間的匹配關(guān)系, 提出一種可持續目標導向策略(Sustainable goals-oriented strategy, SGS). 考慮到兩種優(yōu)化策略的不同特點(diǎn), 單步變鄰域搜索策略作用于整個(gè)種群, 目標導向策略強化種群中的精英個(gè)體, 實(shí)現對輸出解集的雙重優(yōu)化. 仿真實(shí)驗結果表明, 雙重優(yōu)化策略能有效地增強算法性能, 并且所提算法在非支配解的多樣性和收斂性上具有優(yōu)越性.
-
關(guān)鍵詞:
- 可持續生產(chǎn) /
- 多任務(wù)調度 /
- 優(yōu)化策略 /
- 模因算法
Abstract: It is of great significance to comprehensively enhance the sustainability of production scheduling with economic, environmental and social demand. A scheduling model for parallel machine production is established with consideration of four decision tasks: Machine assignment, processing sequence, personnel arrangement, and on/off machine control. To solve this complex problem, a dual-enhanced memetic algorithm (DMA) that integrates two local optimization strategies is proposed. In a random manner, a one-step variable neighborhood search (1S-VNS) suitable for decision-making tasks is designed. For targeted optimization, a sustainable goals-oriented strategy (SGS) is constructed after analyzing the matching relationship between objectives and key tasks. Based on the different characteristics of the two optimization strategies, the 1S-VNS acts on the entire population, and the SGS strengthens the elite individuals, achieving dual optimization of the output solution set. The simulation experimental results show that the dual optimization strategies effectively enhance the algorithm performance, and the proposed DMA has superiority in diversity and convergence of non-dominated solutions. -
圖 1 任務(wù)對應的個(gè)體編碼說(shuō)明圖
Fig. 1 An example graph of individual coding corresponding for tasks
圖 2 社會(huì )維度目標導向的優(yōu)化策略作用效果說(shuō)明圖
Fig. 2 Explanation of the effectiveness of optimization strategy guided by social dimension goal
圖 3 經(jīng)濟維度目標導向的優(yōu)化策略作用效果說(shuō)明圖
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 各個(gè)工件的基本加工數據
A1 Basic machining data for each job
工件 機器 工人 加工時(shí)間$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 機器單位空閑能耗以及開(kāi)關(guān)機能耗
A2 Unit idle energy consumption and on/off energy consumption of machines
機器 空閑單位能耗$p^{\rm{idle}}$ 開(kāi)關(guān)機時(shí)間$t_{\rm{on/off}}$ 開(kāi)關(guān)機能耗$H_{\rm{turn}}$ $M1$ 1 2 2 $M2$ 3 3 9 $M3$ 3 3 6
下載: 導出CSV
亚洲第一网址_国产国产人精品视频69_久久久久精品视频_国产精品第九页<button id="qm3rj"><thead id="qm3rj"></thead></button> <samp id="qm3rj"></samp> <source id="qm3rj"><menu id="qm3rj"><pre id="qm3rj"></pre></menu></source> <video id="qm3rj"><code id="qm3rj"></code></video> <tt id="qm3rj"><track id="qm3rj"></track></tt> -
[1] 國家制造強國建設戰略咨詢(xún)委員會(huì ). 中國制造2025藍皮書(shū) (2018). 北京: 電子工業(yè)出版社, 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] 李遠征, 倪質(zhì)先, 段鈞韜, 徐磊, 楊濤, 曾志剛. 面向高比例新能源電網(wǎng)的重大耗能企業(yè)需求響應調度. 自動(dòng)化學(xué)報, 2023, 49(4): 754?768Li 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] 范厚明, 郭振峰, 岳麗君, 馬夢(mèng)知. 考慮能耗節約的集裝箱碼頭雙小車(chē)岸橋與AGV聯(lián)合配置及調度優(yōu)化. 自動(dòng)化學(xué)報, 2021, 47(10): 2412?2426Fan 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] 賈兆紅, 王燕, 張以文. 求解差異機器平行批調度的雙目標協(xié)同蟻群算法. 自動(dòng)化學(xué)報, 2020, 46(6): 1121?1135Jia 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] 潘子肖, 雷德明. 基于問(wèn)題性質(zhì)的分布式低碳并行機調度算法研究. 自動(dòng)化學(xué)報, 2020, 46(11): 2427?2438Pan 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] 雷德明, 楊冬婧. 基于新型蛙跳算法的低碳混合流水車(chē)間調度. 控制與決策, 2020, 35(6): 1329?1337Lei 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] 耿凱峰, 葉春明, 吳紹興, 劉麗. 分時(shí)電價(jià)下多目標綠色可重入混合流水車(chē)間調度. 中國機械工程, 2020, 31(12): 1469?1480Geng 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] 王飛, 孟凡超, 鄭宏珍. 基于禁忌搜索和遺傳算法的云倉儲分配優(yōu)化. 計算機集成制造系統, 2022, 28(1): 208?216Wang 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)
計量
- 文章訪(fǎng)問(wèn)數: 392
- HTML全文瀏覽量: 59
- PDF下載量: 143
- 被引次數: 0
