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

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.