An Experimental Comparison of Constraint-Based Algorithms for the Preemptive Job-Shop Scheduling Problem

. In the recent years, constraint programming has been applied to a wide variety of academic and industrial non-preemptive scheduling problems, i.e., problems in which activities cannot be interrupted. In comparison, preemptive scheduling problems have received almost no attention from both the Operations Research and the Artificial Intelligence community (see, for example, (Demeulemeester, 1992) as one of a few exceptions). Motivated by the needs of a specific application, we engaged in a study of the applicability of constraint programming techniques to preemptive scheduling problems. This paper presents the algorithms we developed and the results we obtained on the preemptive variant of the famous "job-shop scheduling problem." Eight heuristic search strategies, combined with two different constraint propagation techniques, are presented and compared using the preemptive variant of job-shop scheduling instances from the literature. The best combination, which relies on "limited dis..