A variable neighborhood search for job shop scheduling with set-up times to minimize makespan

Production Scheduling problems are typically named bases on the processing routes of their jobs on different processors and also the number of processors in each stage. In this paper, we consider the problem of scheduling a job shop (JSS) where set-up times are sequence-dependent (SDST) to minimize the maximum completion times of operations or makespan. Our problem is generally formulated as J/STsd/CmaxJ/STsd/Cmax. To tackle such an NP-hard problem, a recent effective metaheuristic algorithm known as variable neighborhood search (VNS) is employed. VNS algorithms have shown excellent capability to solve scheduling problems to optimal or near-optimal schedule. Our proposed VNS is readily intelligible yet is a robust solution technique for the problem of SDST JSS. VNS is categorized as a local search-based algorithm armed with systematic neighborhood search structures. Our proposed VNS obviates the notorious myopic behavior of local search-based metaheuristic algorithms by the means of several systematic insertion neighborhood search structures. An experimental design based on Taillard’s benchmark is conducted to evaluate the efficiency and effectiveness of our proposed algorithm against some effective algorithms in the literature. The obtained results strongly support the high performance of our proposed algorithm with respect to other well-known heuristic and metaheuristic algorithms.