A Tabu Search Algorithm for the Unrelated Parallel Machine Scheduling Problem With Machine Availability Constraint and Sequence-Dependent Setup Time

Abstract

Parallel machine scheduling problems have many practical and industrial applications and have recently been the subject of research by many researchers. However, sometimes machines can be unavailable for a period of time for reasons such as machine failure and maintenance operations. The lack of studies in the literature considering such restrictions has been the motivation for this study. In this study, the unrelated parallel machine scheduling problem is discussed with the assumption that the machines will not always be available and they will not be able to perform some tasks. In addition, sequence-dependent setup times between tasks were also taken into account. The objective function is to minimize total tardiness and earliness. A mixed integer mathematical model is presented for the problem and solved with the GUROBI 9.0 solver. Due to the NP-hard nature of the addressed problem, a tabu search (TS) algorithm is proposed. Experimental results show that the proposed TS algorithm has a good performance.