Tech Report CS-98-03

Job-Shop Scheduling in Localizer

Laurent Michel and Pascal Van Hentenryck

April 1998

Abstract:

Localizer is a domain-specific language for developing local search procedures. By automating many of the tedious tasks underlying local search algorithms, Localizer was shown to reduce the development time significantly and to preserve most of efficiency of specialized algorithms on applications such as Boolean satisfiability and graph coloring. This paper applies Localizer to job-shop scheduling to provide evidence that it can scale up to more sophisticated applications. It presents two Localizer model: an array-based model and a model based on graph-theoretic concepts. This last model illustrates how advanced data types make the statement even closer to the application, while not degrading performance. Both models find optimal or near optimal solutions to standard scheduling benchmarks quickly (from 20 to 90 seconds) on a modern workstation. The underlying implementation techniques are also described.

(complete text in pdf or gzipped postscript)