Constraint Propagation Based Scheduling of Job Shops

This paper examines the minimum makespan problem for the job shop from an artificial intelligence point of view. A new solution procedure is presented which combines general learning strategies with special purpose heuristics, i.e., a constraint propagation based procedure is used and by decomposing the whole problem into single machine problems, problem specific knowledge is introduced. Fundamental for this approach is the equivalency between the constraint and the disjunctive graph. Presented comprehensive computational tests show high quality partial solutions, substantially accelerated exact methods, and a gain of deeper insight into the nature of the underlying problem instances. For example, the propagation and decomposition techniques reveal the particular structure underlying the well-known Fisher and Thompson 10 × 10 problem and thus provide an explanation for why this problem was intractable for such a long time.