Combining Constraint Programming and Local Search for Job-Shop Scheduling
Authors:
- 1 February 2011
- journal article
- research article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
- Vol. 23 (1) , 1-14
Abstract
Since their introduction, local search algorithms have consistently represented the state of the art in solution techniques for the classical job-shop scheduling problem. This dominance is despite the availability of powerful search and inference techniques for scheduling problems developed by the constraint programming community. In this paper, we introduce a simple hybrid algorithm for job-shop scheduling that leverages both the fast, broad search capabilities of modern tabu search algorithms and the scheduling-specific inference capabilities of constraint programming. The hybrid algorithm significantly improves the performance of a state-of-the-art tabu search algorithm for the job-shop problem and represents the first instance in which a constraint programming algorithm obtains performance competitive with the best local search algorithms. Furthermore, the variability in solution quality obtained by the hybrid is significantly lower than that of pure local search algorithms. Beyond performance demonstration, we perform a series of experiments that provide insights into the roles of the two component algorithms in the overall performance of the hybrid.Keywords
This publication has 23 references indexed in Scilit:
- A very fast TS/SA algorithm for the job shop scheduling problemComputers & Operations Research, 2008
- Deconstructing Nowicki and Smutnicki's -TSAB tabu search algorithm for the job-shop scheduling problemComputers & Operations Research, 2006
- APPLYING MACHINE LEARNING TO LOW-KNOWLEDGE CONTROL OF OPTIMIZATION ALGORITHMSComputational Intelligence, 2005
- Statistical Regimes Across Constrainedness RegionsConstraints, 2005
- Algorithms for propagating resource constraints in AI planning and scheduling: Existing approaches and new resultsArtificial Intelligence, 2003
- Dynamic problem structure analysis as a basis for constraint-directed scheduling heuristicsArtificial Intelligence, 2000
- The job shop scheduling problem: Conventional and new solution techniquesEuropean Journal of Operational Research, 1996
- Implementation of resource constraints in ILOG SCHEDULE: a library for the development of constraint-based scheduling systemsIntelligent Systems Engineering, 1994
- Optimal speedup of Las Vegas algorithmsInformation Processing Letters, 1993
- Benchmarks for basic scheduling problemsEuropean Journal of Operational Research, 1993