A guided local search with iterative ejections of bottleneck operations for the job shop scheduling problem. (February 2018)

• Record Type: Journal Article
• Authors: Nagata, Yuichi; Ono, Isao
• Is Part Of: Computers & operations research. Volume 90(2018)
• Page Start: 60
• Page End: 71
• Publication Date: 2018-02
• Subjects: Local search -- Dynamic programming -- Job shop scheduling -- Metaheuristics; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2017.09.017
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: The local search-based method that works in partial solution space is proposed for solving the job shop scheduling problem. The best-so-far schedule is iteratively improved by solving the constraint satisfaction problem. A dynamic programming-based algorithm efficiently enumerates possible local moves under the constraint on the makespan. A tabu search algorithm is introduced as a re-optimization procedure. A mechanism similar to guided local search and random perturbation procedure improve the performance. Abstract: 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.