School of Computer Science, Carnegie Mellon University
Variable and Calue Ordering Heuristics for the Job Shop Scheduling Constraint Satisfaction Problem
Norman M. Sadeh, Mark S. Fox*
This is an updated version of technical report CMU-RI-TR-91-23 scheduled to appear in the Artificial Intelligence Journal.
A new probabilistic framework is introduced that better captures these key aspects of the job shop scheduling search space. Empirical results show that variable and value ordering heuristics derived within this probabilistic framework often yield significant improvements in search efficiency and significant reductions in the search time required to obtain a satisfactory solution.
The research reported in this article was the first one, along with the work of Keng and Yun [Keng 89], to use the CSP problem solving paradigm to solve job shop scheduling problems. The suite of benchmark problems it introduced has been used since then by a number of other researchers to evaluate alternative techniques for the job shop scheduling CSP. The article briefly reviews some of these more recent efforts and shows that our variable and value ordering heuristics remain quite competitive.
*Department of Industrial Engineering,University of Toronto, 4 Taddle Creek Road, Toronto, Ontario M5S 1A4, Canada