Constraint propagation based scheduling of job shops

Constraint propagation based scheduling of job shops

0.00 Avg rating0 Votes
Article ID: iaor19971846
Country: United States
Volume: 8
Issue: 2
Start Page Number: 144
End Page Number: 157
Publication Date: Apr 1996
Journal: INFORMS Journal On Computing
Authors: ,
Keywords: artificial intelligence: expert systems
Abstract:

This paper examines the minimum makespan problem for the job shop from a 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.

Reviews

Required fields are marked *. Your email address will not be published.