Multi-objective collaborative job shop scheduling in a dynamic environment: Non-dominated sorting memetic algorithm
Tóm tắt
In this paper, a novel mathematical model is developed for the distributed multi-agent network scheduling problem in a dynamic job shop environment with availability constraints and new job arrivals. In a dynamic collaborative-competitive environment, a number of factories with independent ownership are merged to form a multi-agent production network in which each production agent, despite participation, seeks to optimize its own objective function as a primary priority. To minimize the makespan and the total energy consumption, the ε-constraint approach is used. Since the problem is NP-hard, a memetic algorithm based on a non-dominated sorting genetic algorithm-II and local search are proposed. Finally, the proposed algorithm is compared with a hybrid Pareto-based tabu search algorithm (HPTSA). The obtained results show that in large-size instances, our proposed algorithm outperforms the HPTSA.
Tài liệu tham khảo
Agnetis A, Billaut JC, Gawiejnowicz S, Pacciarelli D, Soukhal A (2014) Multiagent Scheduling: models and algorithms. Springer-Verlag, Berlin
Allaoui H, Artiba A (2006) Scheduling two-stage hybrid flow shop with availability constraints. Comput Oper Res 33(5):1399–1419
Bagheri Rad N, Behnamian J (2022) Recent trends in distributed production network scheduling problem. Artif Intell Rev 55:1945–2295
Barma PS, Dutta J, Mukherjee A et al (2022) A multi-objective ring star vehicle routing problem for perishable items. J Ambient Intell Humaniz Comput 13:2355–2380
Behnamian J, Fatemi Ghomi SMT (2015) Minimizing cost-related objective in synchronous scheduling of parallel factories in virtual production network. Appl Soft Comput 29:221–232
Chan FTS, Chung SH (2007) Distributed scheduling in multiple-factory production with machine maintenance. In: Wang L, Shen W (eds) process planning and scheduling for distributed manufacturing. Springer, London, pp 243–267
Chan FTS, Chung SH, Chan PLY (2005) An adaptive genetic algorithm with dominated genes for distributed scheduling problems. Expert Syst Appl 29(2):364–371
Chaouch I, Driss OB, Ghedira K (2017) A modified ant colony optimization algorithm for the distributed job shop scheduling problem. Proced Comput Sci 112:296–305
Chung SH, Chan FTS, Chan HK (2009) A modified genetic algorithm approach for scheduling of perfect maintenance in distributed production scheduling. Eng Appl Artif Intell 22(7):1005–1014
Fattahi Z, Behnamian J (2022) Location and transportation of intermodal hazmat considering equipment capacity and congestion impact: elastic method and sub-population genetic algorithm. Ann Oper Res 316:303–341
Fei Y, Ziqing L, Yuanjun L (2022) Simulation optimization on joint production and preventive maintenance scheduling for distributed job-shop. J Syst Simul 34(4):688–699
Garey MR, Johnson DS, Sethi R (1976) The complexity of flowshop and job shop scheduling. Math Oper Res 1(2):117–129
Glover F, Woolsey E (1974) Technical note—converting the 0–1 polynomial programming problem to a 0–1 linear program. Oper Res 22(1):180–182
Goli A, Babaee Tirkolaee E, Soltani M (2019) A robust just-in-time flow shop scheduling problem with outsourcing option on subcontractors. Prod Manuf Res 7(1):294–315
Goli A, Babaee Tirkolaee E, Aydın NS (2021) Fuzzy integrated cell formation and production scheduling considering automated guided vehicles and human factors. IEEE Trans Fuzzy Syst 29(12):3686–3695
Jafari V, Rezvani MH (2021) Joint optimization of energy consumption and time delay in IoT-fog-cloud computing environments using NSGA-II metaheuristic algorithm. J Ambient Intell Humaniz Comput. https://doi.org/10.1007/s12652-021-03388-2
Jeong IJ, Yim SB (2009) A job shop distributed scheduling based on Lagrangian relaxation to minimise total completion time. Int J Prod Res 47:6783–6805
Jia HZ, Nee AYC, Fuh JYH, Zhang YF (2002) Web-based multi-functional scheduling system for a distributed manufacturing environment. Concurr Eng 10(1):27–39
Jia HZ, Nee AYC, Fuh JYH, Zhang YF (2003) A modified genetic algorithm for distributed scheduling problems. J Intell Manuf 14(3):351–362
Jia HZ, Fuh JYH, Nee AYC, Zhang YF (2007) Integration of genetic algorithm and Gantt chart for job shop scheduling in distributed manufacturing systems. Comput Ind Eng 53(2):313–320
Jiang ED, Wang L, Peng ZP (2020) Solving energy-efficient distributed job shop scheduling via multi-objective evolutionary algorithm with decomposition. Swarm Evol Comput 58:100745
Ławrynowicz A (2008) Integration of production planning and scheduling using an expert system and a genetic algorithm. J Oper Res Soc 59(4):455–463
Lee CY (1999) Two-machine flowshop scheduling with availability constraints. Eur J Oper Res 114(2):420–429
Li JQ, Duan P, Cao J, Lin XP, Han YY (2018) A hybrid Pareto-based tabu search for the distributed flexible job shop scheduling problem with E/T criteria. IEEE Access 6:58883–58897
Liu X, Bo H, Ma Y, Meng Q (2006) A new approach for planning and scheduling problems in hybrid distributed manufacturing execution system. World Congr Intell Control Autom 2:7357–7361
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
Mavrotas G, Florios K (2013) An improved version of the augmented eps-constraint method (AUGMECON2) for finding the exact Pareto set in multi-objective integer programming problems. Appl Math Comput 219(18):9652–9669
Moon C, Seo Y (2005) Evolutionary algorithm for advanced process planning and scheduling in a multi-plant. Comput Ind Eng 48(2):311–325
Moon C, Lee YH, Jeong CS, Yun Y (2008) Integrated process planning and scheduling in a supply chain. Comput Ind Eng 54(4):1048–1061
Muth JF, Thompson GL, Winters PR (1963) Industrial scheduling. Prentice-Hall, Englewood Cliffs
Naderi B, Azab A (2014) Modeling and heuristics for scheduling of distributed job shops. Expert Syst Appl 41(17):7754–7763
Naderi B, Azab A (2015) An improved model and novel simulated annealing for distributed job shop problems. Int J Adv Manuf Technol 81(1):693–703
Rahmati SHA, Hajipour V, Niaki STA (2013) A soft-computing Pareto-based meta-heuristic algorithm for a multi-objective multi-server facility location problem. Appl Soft Comput 13(4):1728–1740
Şahman MA (2021) A discrete spotted hyena optimizer for solving distributed job shop scheduling problems. Appl Soft Comput 106:107349
Wang S, Yu J (2010) An effective heuristic for flexible job-shop scheduling problem with maintenance activities. Comput Ind Eng 59(3):436–447
Wang Y, Yan L, Zhu H, Yin C (2006) A genetic algorithm for solving dynamic scheduling problems in distributed manufacturing systems. World Congr Intell Control Autom 2:7343–7347
Wang S, Li X, Gao L, Wang L (2021) An improved genetic algorithm for distributed job shop scheduling problem. In: Intelligent Computing Theories and Application, pp 37–47
Williams J (1981) Heuristic techniques for simultaneous scheduling of production and distribution in multi-echelon structures: theory and empirical Comparisons. Manage Sci 27:336–352
Xie J, Gao L, Pan QK, Tasgetiren MF (2019) An effective multi-objective artificial bee colony algorithm for energy efficient distributed job shop scheduling. Proced Manuf 39:1194–1203
Zhang Y-X, Li L, Wang H, Zhao Y-Y, Guo X, Meng C-H (2008) Approach to the distributed job shop scheduling based on multi-agent. In: 2008 IEEE international conference on automation and logistics, 2008, Qingdao, China, pp 2031–2034. https://doi.org/10.1109/ICAL.2008.4636496