New Search Spaces for Sequencing Problems with Application to Job Shop Scheduling
Robert H. Storer, S. David Wu, Renzo Vaccari
Management Science · 1992 · Volume 38 · Issue 10
Abstract
In this paper search heuristics are developed for generic sequencing problems with emphasis on job shop scheduling. The proposed methods integrate problem specific heuristics common to Operations Research and local search approaches from Artificial Intelligence in order to obtain desirable properties from both. The applicability of local search to a wide range of problems, and the incorporation of problem-specific information are both properties of the proposed algorithms. Two methods are proposed, both of which are based on novel definitions of solution spaces and of neighborhoods in these spaces. Applications of the proposed methodology are developed for job shop scheduling problems, and can be easily applied with any scheduling objective. To demonstrate effectiveness, the method is tested on the job shop scheduling problem with the minimum makespan objective. Encouraging results are obtained.
Keywords
local search, search neighborhoods, scheduling, combinatorial optimization
Enable JavaScript for citation tools and additional paper interactions.