Optimizing Open Shop Scheduling: Minimizing Makespan through Whale Optimization Algorithm and Transportation Time Consideration

Document Type : Research Paper

Authors

1 MSc graduate, Department of Industrial Engineering, Tabriz Branch, Islamic Azad University, Tabriz, Iran

2 Department of Industrial Engineering, Bonab Branch, Islamic Azad University, Bonab, Iran

3 Department of Mechanical Engineering, Faculty of Engineering, University of Zabol, Zabol 98613-35856, Iran

10.22070/jqepo.2024.16744.1244

Abstract

This paper addresses the open shop scheduling problem, considering parallel machines within each stage and integrating job transportation times between stages, independent of job specifics. In this scheduling problem, all jobs traverse each stage, and once a job commences on a machine, it must complete without machine breakdowns. To meet this challenge, a mixed-integer linear programming (MILP) model is introduced to minimize the makespan, which represents the maximum job completion time. Given the NP-hard nature of the open-shop scheduling problem, this study employs the whale metaheuristic algorithm to solve instances across various dimensions, spanning small, medium, and large scales. The algorithm parameters are systematically optimized using the Taguchi Method. Results from comparing the whale algorithm with the linear model implemented in GAMS highlight its exceptional efficiency in handling randomly generated small and medium-sized instances. Moreover, in a comparative analysis with other algorithms such as PSO and DE, the whale algorithm not only competes effectively but, in some instances, outperforms its counterparts. This observation underscores the algorithm's prowess in maintaining efficiency and high performance, particularly when addressing large-scale open-shop scheduling challenges. It excels in achieving a delicate balance between exploration and exploitation, thereby avoiding local optimal solutions.

Keywords

References

Abdelmaguid, T. F. (2020). Bi-objective dynamic multiprocessor open shop scheduling: an exact algorithm. Algorithms, 13(3), 74.
Abdelmaguid, T. F. (2020). Scatter search with path relinking for multiprocessor open shop scheduling. Computers & Industrial Engineering, 141, 106292.
Abdelmaguid, T. F. (2021). Bi-objective dynamic multiprocessor open shop scheduling for maintenance and healthcare diagnostics. Expert Systems With Applications, 186, 115777.
Adak, Z. (2021). Solution Representation in Proportionate Multiprocessor Open Shop. Journal of Intelligent Systems: Theory and Applications, 4(2), 86–93.
Adak, Z., Arıoğlu, M. Ö., & Bulkan, S. (2022). An ant colony optimization approach for the proportionate multiprocessor open shop. Journal of Combinatorial Optimization, 43, 785–817.
Ahmadizar, F., & Shahmaleki, P. (2014). Group shop scheduling with sequence-dependent setup and transportation times. APPLIED MATHEMATICAL MODELLING, 38(21–22), 5080–5091.
Barzegar, B., Motameni, H., KHOSROZADEH, G. A., & Divsalar, A. (2012). A Hybrid Genetic Algorithm for the Open Shop Scheduling with Makespan and Total Completion Time.
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. The Journal of Supercomputing, 77, 13115-13138.
Bezoui, M., Olteanu, A. L., & Sevaux, M. (2023). Integrating preferences within multiobjective flexible job shop scheduling. European Journal of Operational Research, 305(3), 1079–1086.
Esmaeili, M., Ahmadizar, F., & Sadeghi, H. (2021). Minimizing the sum of earliness and tardiness in single-machine scheduling. Journal of Quality Engineering and Production Optimization, 6(2), 59-78.
Gawali, M. B., & Shinde, S. K. (2018). Task scheduling and resource allocation in cloud computing using a heuristic approach. Journal of Cloud Computing, 7, 1-16.
Gonzalez, T., & Sahni, S. (1976). Open shop scheduling to minimize finish time. Journal of the ACM (JACM), 23(4), 665–679.
Gu, H. M., Hu, R., Qian, B., Jin, H. P., & Wang, L. (2019). Whale optimization algorithm with local search for open shop scheduling problem to minimize makespan. In Intelligent Computing Theories and Application: 15th International Conference, ICIC 2019, Nanchang, China, August 3–6, 2019, Proceedings, Part II 15 (pp. 678-687). Springer International Publishing.
 
Kubiak, W. (2022). Book of Open Shop Scheduling. Springer International Publishing.
Kurdi, M. (2022). Ant colony optimization with a new exploratory heuristic information approach for open shop scheduling problem. Knowledge-Based Systems, 242, 108323.
Mafarja, M. M., & Mirjalili, S. (2018). Whale Optimization Approaches for Wrapper Feature Selection. Applied Soft Computing Journal, 62, 441–453.
Mejía, G., & Yuraszeck, F. (2020). A self-tuning variable neighborhood search algorithm and an effective decoding scheme for open shop scheduling problems with travel / setup times. European Journal of Operational Research, 285(2), 484–496.
Mirjalili, S., & Lewis, A. (2016). The Whale Optimization Algorithm. Advances in Engineering Software, 95, 51–67.
Naderia, B., & Roshanaei, V. (2014). No-idle time Scheduling of Open shops: Modeling and Meta-heuristic Solution Methods. International Journal of Supply and Operations Management, 1(1), 54–68.
Pinedo Michael, L. (2008). Scheduling Theory, Algorithms, and Systems. New York University. ISBN: 978-0-387-78934-7, e-ISBN: 978-0-387-78935.
Rahmani Hosseinabadi, A. A., Vahidi, J., Saemi, B., Sangaiah, A. K., & Elhoseny, M. (2019). Extended genetic algorithm for solving open-shop scheduling problem. Soft computing, 23, 5099-5116.
 
Rastgar, I., Rezaeian, J., Mahdavi, I., & Fattahi, P. (2021). Opportunistic maintenance management for a hybrid flow shop scheduling problem. Journal of Quality Engineering and Production Optimization, 6(2), 17-30.
Rezvan, M. T., Gholami, H., & Zakerian, R. (2021). A new algorithm for solving the parallel machine scheduling problem to maximize benefit and the number of jobs processed. Journal of Quality Engineering and Production Optimization, 6(2), 115-142.
Schworm, P., Wu, X., Glatt, M., & Aurich, J. C. (2023). Solving flexible job shop scheduling problems in manufacturing with Quantum Annealing. Production Engineering, 17(1), 105–115.
Shareh, M. B., Bargh, S. H., Hosseinabadi, A. A. R., & Slowik, A. (2021). An improved bat optimization algorithm to solve the tasks scheduling problem in open shop. Neural Computing and Applications, 33, 1559–1573.
Sharifzadegan, M., Tahmoores Sohrabi, & Chaghoshi, A. J. (2021). Hybrid optimization of production scheduling and maintenance using mathematical programming and NSGA-II meta-heuristic method. Journal of Quality Engineering and Production Optimization, 6(2), 79-96.
Torres-Tapia, W., Montoya-Torres, J. R., Ruiz-Meza, J., & Belmokhtar-Berraf, S. (2022). A Matheuristic based on Ant Colony System for the Combined Flexible Jobshop Scheduling and Vehicle Routing Problem. IFAC-PapersOnLine, 55(10) 1613-1618 .
Ying, K. C., & Lin, S. W. (2023). Minimizing makespan in two-stage assembly additive manufacturing: A reinforcement learning iterated greedy algorithm. Applied Soft Computing, 138, 110190.
Zhang, G., Sun, J., Liu, X., Wang, G., & Yang, Y. (2019). Solving flexible job shop scheduling problems with transportation time based on improved genetic algorithm. Mathematical Biosciences and Engineering, 16(3), 1334–1347.
Journal of Quality Engineering and Production Optimization
Volume 8, Issue 1
May 2023
Pages 133-150

Files

Share

How to cite

Statistics