Một thuật toán memetic đa mục tiêu dựa trên nhiều khu hàng xóm cho vấn đề lập lịch nhà máy dòng linh hoạt phân tán tiết kiệm năng lượng

Neural Computing and Applications - Tập 34 - Trang 22303-22330 - 2022
Weishi Shao1,2, Zhongshi Shao3, Dechang Pi2,4
1School of Computer and Electronic Information / School of Artificial Intelligence, Nanjing Normal University, Nanjing, China
2College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing, China
3School of Computer Science, Shaanxi Normal University, Xi’an, China
4Collaborative Innovation Center of Novel Software Technology and Industrialization, Nanjing, China

Tóm tắt

Bài báo này tập trung vào vấn đề lập lịch nhà máy dòng linh hoạt phân tán tiết kiệm năng lượng (EEDFFSP) với tốc độ máy biến đổi. EEDFFSP cần giải quyết bốn bài toán con: phân công nhà máy, xác định trình tự công việc tại mỗi giai đoạn, lựa chọn máy, và lựa chọn tốc độ cho mỗi công việc trên một máy. Một thuật toán memetic đa mục tiêu dựa trên nhiều khu hàng xóm (MMMA) được đề xuất để tối ưu hóa tổng độ trễ có trọng số và tiêu thụ năng lượng. MMMA sử dụng một sơ đồ mã hóa hai cấp bao gồm một hoán vị công việc và một ma trận tốc độ. Một chiến lược giải mã hiệu quả cao được sử dụng để giảm không gian tìm kiếm của các bài toán con. Trong giai đoạn ban đầu, một phương pháp khởi tạo dựa trên NEH (Nawaz-Enscore-Ham) có trọng số được phát triển để tạo ra một quần thể ban đầu. Hai toán tử tìm kiếm toàn cục gen được thiết kế để thực hiện sự phát triển khám phá. Sau đó, một số khu hàng xóm đa dạng bao gồm một số thao tác điều chỉnh hoán vị trong hoặc giữa các nhà máy, một chiến lược tiết kiệm năng lượng, và một chiến lược điều chỉnh tốc độ được tích hợp để nâng cao khả năng khai thác. Các thí nghiệm toàn diện trên các trường hợp mở rộng được thực hiện để kiểm tra sự đóng góp của các thành phần chính và hiệu suất của MMMA. Các giá trị trung bình của chỉ số Hypervolume và Unary Epsilon thu được từ các biến thể của MMMA mà không có phương pháp khởi tạo, tìm kiếm toàn cục gen, tìm kiếm cục bộ và chiến lược tiết kiệm năng lượng kém hơn so với MMMA hoàn chỉnh, điều này chứng tỏ sự đóng góp quan trọng của các thành phần này đối với MMMA. MMMA đạt được các giá trị tốt nhất của các chỉ số trong số tất cả các thuật toán so sánh trong một thời gian chạy hạn chế, điều này chứng tỏ MMMA là một thuật toán hiệu quả và có hiệu suất cao cho việc giải quyết EEDFFSP.

Từ khóa

#lập lịch nhà máy #tiết kiệm năng lượng #thuật toán memetic #tối ưu hóa đa mục tiêu #tốc độ máy biến đổi

Tài liệu tham khảo

Ruiz R, Vázquez-Rodríguez JA (2010) The hybrid flow shop scheduling problem. Eur J Oper Res 205:1–18 Lohmer J, Lasch R (2021) Production planning and scheduling in multi-factory production networks: a systematic literature review. Int J Prod Res 59(7):2028–2054. https://doi.org/10.1080/00207543.2020.1797207 Behnamian J, Ghomi SMTF (2016) A survey of multi-factory scheduling. J Intell Manuf 27:231–249 Fu YP, Hou YS, Wang ZF, Wu XW, Gao KZ, Wang L (2021) Distributed Scheduling Problems in Intelligent Manufacturing Systems. Tsinghua Sci Technol 26:625–645 Shao Z, Pi D, Shao W (2020) Hybrid enhanced discrete fruit fly optimization algorithm for scheduling blocking flow-shop in distributed environment. Expert Syst Appl 145:113–147 Pan Q, Gao L, Wang L, Liang J, Li X (2019) Effective heuristics and metaheuristics to minimize total flowtime for the distributed permutation flowshop problem. Expert Syst Appl 124:309–324 Wang J, Wang L (2019) An iterated greedy algorithm for distributed hybrid flowshop scheduling problem with total tardiness minimization. In: 2019 IEEE 15th international conference on automation science and engineering (CASE), pp 350–355 Fernandez-Viagas V, Perez-Gonzalez P, Framinan JM (2018) The distributed permutation flow shop to minimise the total flowtime. Comput Ind Eng 118:464–477 Pan Q, Gao L, Wang L (2020) An effective cooperative co-evolutionary algorithm for distributed flowshop group scheduling problems. IEEE Trans Cybern 52(7):5999–6012. https://doi.org/10.1109/TCYB.2020.3041494 Chaouch I, Driss OB, Ghedira K (2019) A novel dynamic assignment rule for the distributed job shop scheduling problem using a hybrid ant-based algorithm. Appl Intell 49:1903–1924 Behnamian J, Fatemi Ghomi SMT (2015) Minimizing cost-related objective in synchronous scheduling of parallel factories in the virtual production network. Appl Soft Comput 29:221–232 Wang J-J, Wang L (2022) A cooperative memetic algorithm with feedback for the energy-aware distributed flow-shops with flexible assembly scheduling. Comput Ind Eng 168:108126 Zhang R, Chiong R (2016) 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 Clean Prod 112:3361–3375 Meng L, Zhang C, Shao X, Ren Y, Ren C (2019) Mathematical modelling and optimisation of energy-conscious hybrid flow shop scheduling problem with unrelated parallel machines. Int J Prod Res 57:1119–1145 Neugebauer R, Wabner M, Rentzsch H, Ihlenfeldt S (2011) Structure principles of energy efficient machine tools. CIRP J Manuf Sci Technol 4:136–147 Liu F (2013) Content architecture and future trends of energy efficiency research on machining systems. J Mech Eng 49:87 Chávez-García H, Castillo-Villar KK (2018) Simulation-based model for the optimization of machining parameters in a metal-cutting operation. Simul Model Pract Theory 84:204–221 Li X, Gao L (2016) An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem. Int J Prod Econ 174:93–110 Zhang Z, Tang R, Peng T, Tao L, Jia S (2016) A method for minimizing the energy consumption of machining system: integration of process planning and scheduling. J Clean Prod 137:1647–1662 Gupta JND (1988) Two-stage, hybrid flowshop scheduling problem. J Oper Res Soc 39:359–364 Naderi B, Ruiz R (2010) The distributed permutation flowshop scheduling problem. Comput Oper Res 37:754–768 Moscato P (1989) On evolution, search, optimization, genetic algorithms and martial arts - towards memetic algorithms. In: Caltech concurrent computation program, California Institute of Technology, p 826 Chen X, Ong Y, Lim M, Tan KC (2011) A multi-facet survey on memetic computation. IEEE Trans Evol Comput 15:591–607 Shen X-N, Minku LL, Marturi N, Guo Y-N, Han Y (2018) A Q-learning-based memetic algorithm for multi-objective dynamic software project scheduling. Inf Sci 428:1–29 Du Y, Xing L, Zhang J, Chen Y, He Y (2019) MOEA based memetic algorithms for multi-objective satellite range scheduling problem. Swarm Evol Comput 50:100576 Raja MAZ, Shah AA, Mehmood A, Chaudhary NI, Aslam MS (2018) Bio-inspired computational heuristics for parameter estimation of nonlinear Hammerstein controlled autoregressive system. Neural Comput Appl 29:1455–1474 Mehmood A, Zameer A, Raja MAZ, Bibi R, Chaudhary NI, Aslam MS (2019) Nature-inspired heuristic paradigms for parameter estimation of control autoregressive moving average systems. Neural Comput Appl 31:5819–5842 Wang X, Wang Z, Sheng M, Li Q, Sheng W (2021) An adaptive and opposite K-means operation based memetic algorithm for data clustering. Neurocomputing 437:131–142 Dong J, Hou B, Feng L, Tang H, Tan KC, Ong YS (2022) A cell-based fast memetic algorithm for automated convolutional neural architecture design. IEEE Trans Neural Netw Learn Syst. https://doi.org/10.1109/TNNLS.2022.3155230 Teck S, Dewil R (2022) A bi-level memetic algorithm for the integrated order and vehicle scheduling in a RMFS. Appl Soft Comput 121:108770 Afsar S, Palacios JJ, Puente J, Vela CR, González-Rodríguez I (2022) Multi-objective enhanced memetic algorithm for green job shop scheduling with uncertain times. Swarm Evol Comput 68:101016 Zhang G, Ma X, Wang L, Xing K (2022) Elite archive-assisted adaptive memetic algorithm for a realistic hybrid differentiation flowshop scheduling problem. IEEE Trans Evol Comput 26:100–114 Wang X, Tang L (2017) A machine-learning based memetic algorithm for the multi-objective permutation flowshop scheduling problem. Comput Oper Res 79:60–77 Shao W, Shao Z, Pi D (2021) An ant colony optimization behavior-based MOEA/D for distributed heterogeneous hybrid flow shop scheduling problem under nonidentical time-of-use electricity tariffs. IEEE Trans Autom Sci Eng. https://doi.org/10.1109/TASE.2021.3119353 Ying K-C, Lin S-W (2018) Minimizing makespan for the distributed hybrid flowshop scheduling problem with multiprocessor tasks. Expert Syst Appl 92:132–141 Zheng J, Wang L, Wang J (2020) A cooperative coevolution algorithm for multi-objective fuzzy distributed hybrid flow shop. Knowl-Based Syst 194:105536 Shao W, Shao Z, Pi D (2020) Modeling and multi-neighborhood iterated greedy algorithm for distributed hybrid flow shop scheduling problem. Knowl-Based Syst 194:105527 Hao J, Li J, Du Y, Song M, Duan P, Zhang Y (2019) Solving distributed hybrid flowshop scheduling problems by a hybrid brain storm optimization algorithm. IEEE Access 7:66879–66894 Lei D, Wang T (2019) Solving distributed two-stage hybrid flowshop scheduling using a shuffled frog-leaping algorithm with memeplex grouping. Eng Optim 52:1461–1474 Li Y, Li X, Gao L, Zhang B, Pan Q, Tasgetiren MF, Meng L (2021) A discrete artificial bee colony algorithm for distributed hybrid flowshop scheduling problem with sequence-dependent setup times. Int J Prod Res 59(13):3880–3899. https://doi.org/10.1080/00207543.2020.1753897 Li Y, Li X, Gao L, Meng L (2020) An improved artificial bee colony algorithm for distributed heterogeneous hybrid flowshop scheduling problem with sequence-dependent setup times. Comput Ind Eng 147:106638 Cai J, Lei D, Li M (2021) A shuffled frog-leaping algorithm with memeplex quality for bi-objective distributed scheduling in hybrid flow shop. Int J Prod Res 59(18):5404–5421. https://doi.org/10.1080/00207543.2020.1780333 Shao Z, Shao W, Pi D (2022) LS-HH: a learning-based selection hyper-heuristic for distributed heterogeneous hybrid blocking flow-shop scheduling. IEEE Trans Emerg Top Comput Intell. https://doi.org/10.1109/TETCI.2022.3174915 Tang D, Dai M, Salido MA, Giret A (2016) Energy-efficient dynamic scheduling for a flexible flow shop using an improved particle swarm optimization. Comput Ind 81:82–95 Zhang B, Pan Q, Gao L, Meng L, Li X, Peng K (2019) A three-stage multiobjective approach based on decomposition for an energy-efficient hybrid flow shop scheduling problem. IEEE Trans Syst Man Cybern Syst 50(12):4984–4999. https://doi.org/10.1109/TSMC.2019.2916088 Lei D, Gao L, Zheng Y (2018) A novel teaching-learning-based optimization algorithm for energy-efficient scheduling in hybrid flow shop. IEEE Trans Eng Manage 65:330–340 Li M, Lei D, Cai J (2019) Two-level imperialist competitive algorithm for energy-efficient hybrid flow shop scheduling problem with relative importance of objectives. Swarm Evol Comput 49:34–43 Öztop H, Tasgetiren MF, Kandiller L, Eliiyi DT, Gao L (2020) Ensemble of metaheuristics for energy-efficient hybrid flowshops: Makespan versus total energy consumption. Swarm Evol Comput 54:100660 Chen T, Cheng C, Chou Y (2018) Multi-objective genetic algorithm for energy-efficient hybrid flow shop scheduling with lot streaming. Ann Oper Res 290:813–836. https://doi.org/10.1007/s10479-018-2969-x Gao K, Huang Y, Sadollah A, Wang L (2020) A review of energy-efficient scheduling in intelligent production systems. Complex Intell Syst 6:237–249 Deng J, Wang L, Wu C, Wang J, Zheng X (2016) A competitive memetic algorithm for carbon-efficient scheduling of distributed flow-shop. In: ICIC 2016: international conference on intelligent computing. Springer, Lanzhou, China, pp 476–488 Chen J, Wang L, Peng Z (2019) A collaborative optimization algorithm for energy-efficient multi-objective distributed no-idle flow-shop scheduling. Swarm Evol Comput 50:100557 Wang J, Wang L (2018) A knowledge-based cooperative algorithm for energy-efficient scheduling of distributed flow-shop. IEEE Trans Syst Man Cybern Syst 50:1805–1819 Fu Y, Tian G, Fathollahi-Fard AM, Ahmadi A, Zhang C (2019) Stochastic multi-objective modelling and optimization of an energy-conscious distributed permutation flow shop scheduling problem with the total tardiness constraint. J Clean Prod 226:515–525 Wang J, Wang L (2021) A cooperative memetic algorithm with learning-based agent for energy-aware distributed hybrid flow-shop scheduling. IEEE Trans Evolut Comput 26(3):461–475. https://doi.org/10.1109/TEVC.2021.3106168 Ding J-Y, Song S, Wu C (2016) Carbon-efficient scheduling of flow shops by multi-objective optimization. Eur J Oper Res 248:758–771 Meng S (1991) Handbook of Machining process (in Chinese), Machinery Industry Press, Hao J-K (2012) Memetic algorithms in discrete optimization. In: Neri F, Cotta C, Moscato P (eds) Handbook of memetic algorithms. Springer, Berlin, pp 73–94 Mei Y, Tang K, Yao X (2011) Decomposition-based memetic algorithm for multiobjective capacitated arc routing problem. IEEE Trans Evol Comput 15:151–165 Fernandez-Viagas V, Perez-Gonzalez P, Framinan JM (2019) Efficiency of the solution representations for the hybrid flow shop scheduling problem with makespan objective. Comput Oper Res 109:77–88 Zhang Q, Li H (2007) MOEA/D: a multiobjective evolutionary algorithm based on decomposition. IEEE Trans Evol Comput 11:712–731 Yağmur E, Kesen SE (2020) A memetic algorithm for joint production and distribution scheduling with due dates. Comput Ind Eng 142:106342 Radcliffe NJ, Surry PD (1994) Formal memetic algorithms. Springer, Berlin, pp 1–16 Schiavinotto T, Stützle T (2007) A review of metrics on permutations for search landscape analysis. Comput Oper Res 34:3143–3153 Zitzler E, Thiele L (1999) Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach. IEEE Trans Evol Comput 3:257–271 Zitzler E, Thiele L, Laumanns M, Fonseca CM, Fonseca VGD (2003) Performance assessment of multiobjective optimizers: an analysis and review. IEEE Trans Evol Comput 7:117–132 Ruiz R, Pan Q, Naderi B (2019) Iterated Greedy methods for the distributed permutation flowshop scheduling problem. Omega 83:213–222 Shao W, Pi D, Shao Z (2019) A Pareto-based estimation of distribution algorithm for solving multiobjective distributed no-wait flow-shop scheduling problem with sequence-dependent setup time. IEEE Trans Autom Sci Eng 16:1344–1360