Sophisticated metaheuristics represent the state-of-the-art in job shop scheduling. Inspired by these algorithms, a solution-guided, multi-point constructive search approach has recently been proposed in the constraint programming literature. When applied to job shop scheduling, the algorithm exhibits strong performance, but still lags the state-of-the-art. We examine a simple hybridization of solution-guided constructive search with an existing metaheuristic-based scheduler. Despite the simplicity of the hybridization, we observe very strong results, finding 12 new best solutions for a well-known benchmark set. Of particular note is the fact that the hybrid exhibits very low variance across multiple runs and, because it is complete, is able to prove optimality on a number of problem instances. Joint work with Jean-Paul Watson, Sandia National Laboratories.
Groupe d’études et de recherche en analyse des décisions