A guided local search with iterative ejections of bottleneck operations for the job shop scheduling problem

This paper presents a local search-based method that works in partial solution space for solving the job shop scheduling problem (JSP). The proposed method iteratively solves a series of constraint satisfaction problems (CSPs), where the current CSP is defined as the original JSP with an additional constraint that the makespan is smaller than that of the schedule obtained by solving the previous CSP. To obtain a solution to the current CSP, a local search-based procedure is performed in a partial solution space where the current solution is represented as a partial schedule. The neighborhood consists of a set of partial schedules whose makespan is less than that of the best-so-far complete schedule obtained by solving the previous CSP. The existence of the additional constraint on the makespan restricts possible local moves to those that satisfy necessary conditions to improve the best-so-far complete schedule. These moves are efficiently enumerated by using a dynamic programming-based algorithm we present in this paper. We also present an effective strategy of selecting next partial solution from the neighborhood, perturbation procedure, and tabu-search procedure, all of which are embedded into the basic framework to enhance the performance.