An ant colony optimization approach for the proportionate multiprocessor open shop
Tóm tắt
Multiprocessor open shop makes a generalization to classical open shop by allowing parallel machines for the same task. Scheduling of this shop environment to minimize the makespan is a strongly NP-Hard problem. Despite its wide application areas in industry, the research in the field is still limited. In this paper, the proportionate case is considered where a task requires a fixed processing time independent of the job identity. A novel highly efficient solution representation is developed for the problem. An ant colony optimization model based on this representation is proposed with makespan minimization objective. It carries out a random exploration of the solution space and allows to search for good solution characteristics in a less time-consuming way. The algorithm performs full exploitation of search knowledge, and it successfully incorporates problem knowledge. To increase solution quality, a local exploration approach analogous to a local search, is further employed on the solution constructed. The proposed algorithm is tested over 100 benchmark instances from the literature. It outperforms the current state-of-the-art algorithm both in terms of solution quality and computational time.
Tài liệu tham khảo
Abdelmaguid TF (2014) A hybrid PSO-TS approach for proportionate multiprocessor open shop scheduling. In: 2014 IEEE international conference on industrial engineering and engineering management. pp 107–111
Abdelmaguid TF (2020a) Scatter search with path relinking for multiprocessor open shop scheduling. Comput Ind Eng 141:106292
Abdelmaguid TF (2020b) Bi-objective dynamic multiprocessor open shop scheduling: an exact algorithm. Algorithms 13(3):74
Abdelmaguid TF, Shalaby MA, Awwad MA (2014) A tabu search approach for proportionate multiprocessor open shop scheduling. Comput Optim Appl 58(1):187–203
Adak Z, Arıoğlu Akan MÖ, Bulkan S (2020) Multiprocessor open shop problem: literature review and future directions. J Comb Optim 40(2):547–569
Azadeh A, Farahani MH, Torabzadeh S, Baghersad M (2014) Scheduling prioritized patients in emergency department laboratories. Comput Methods Programs Biomed 117(2):61–70
Azadeh A, Goldansaz S, Zahedi-Anaraki A (2016) Solving and optimizing a bi-objective open shop scheduling problem by a modified genetic algorithm. Int J Adv Manuf Technol 85:1603–1613
Bai D, Zhang ZH, Zhang Q (2016) Flexible open shop scheduling problem to minimize makespan. Comput Oper Res 67:207–215
Behnamian J, Memar Dezfooli S, Asgari H (2021) A scatter search algorithm with a novel solution representation for flexible open shop scheduling: a multi-objective optimization. J Supercomput. https://doi.org/10.1007/s11227-021-03794-5
Blum C, Dorigo M (2004) The hyper-cube framework for ant colony optimization. IEEE Trans Syst Man Cybern Part B Cybern 34(2):1161–1172
Den Besten M, Stützle T, Dorigo M (2000) Ant colony optimization for the total weighted tardiness problem. In: International conference on parallel problem solving from nature. Springer, Berlin, pp 611–620
Dorigo M, Gambardella LM (1997) Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Trans Evol Comput 1(1):53–66
Dorigo M, Maniezzo V, Colorni A (1996) The ant system: optimization by a colony of cooperating agents. IEEE Trans Syst Man Cybern Part B 26:29–41
Dorigo M, Stützle T (2004) Ant colony optimization. MIT Press, Cambridge
Goldansaz SM, Jolai F, Anaraki AHZ (2013) A hybrid imperialist competitive algorithm for minimizing makespan in a multi-processor open shop. Appl Math Model 37(23):9603–9616
Gonzalez T, Sahni S (1976) Open shop scheduling to minimize finish time. J ACM JACM 23(4):665–679
Graham RL, Lawler EL, Lenstra JK, Kan AR (1979) Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann Discrete Math 5:287–326
Matta ME (2009) A genetic algorithm for the proportionate multiprocessor open shop. Comput Oper Res 36(9):2601–2618
Matta ME, Elmaghraby SE (2010) Polynomial time algorithms for two special classes of the proportionate multiprocessor open shop. Eur J Oper Res 201(3):720–728
Mao W (1995) Multi-operation multi-machine scheduling. In: International conference on high-performance computing and networking. Springer, Berlin, pp 33–38
Merkle D, Middendorf M (2003) Ant colony optimization with global pheromone evaluation for scheduling a single machine. Appl Intell 18(1):105–111
Merkle D, Middendorf M, Schmeck H (2000) Pheromone evaluation in ant colony optimization. In: 2000 26th annual conference of the IEEE industrial electronics society. IECON 2000. 2000 IEEE international conference on industrial electronics, control and instrumentation. 21st century technologies, vol 4. IEEE, pp 2726–2731
Merkle D, Middendorf M, Schmeck H (2002) Ant colony optimization for resource-constrained project scheduling. IEEE Trans Evol Comput 6(4):333–346
Naderi B, Ghomi SF, Aminnayeri M, Zandieh M (2011) Scheduling open shops with parallel machines to minimize total completion time. J Comput Appl Math 235(5):1275–1287
Stützle T, Hoos HH (2000) MAX–MIN ant system. Futur Gener Comput Syst 16(8):889–914
Zhang J, Wang L, Xing L (2019) Large-scale medical examination scheduling technology based on intelligent optimization. J Comb Optim 37(1):385–404