Constraint propagation and problem decomposition: A preprocessing procedure for the job shop problem

In recent years, constraint propagation techniques have been shown to be highly effective for solving difficult scheduling problems. In this paper, we present an algorithm which combines constraint propagation with a problem decomposition approach in order to simplify the solution of the job shop sc...

Full description

Saved in:
Bibliographic Details
Published in:Annals of operations research 2002-09, Vol.115 (1), p.125
Main Authors: Dorndorf, Ulrich, Pesch, Erwin, Phan-Huy, Toan
Format: Article
Language:English
Subjects:
Algorithms
Computer programming
Decomposition
Heuristic
Job shops
Operations research
Propagation
Scheduling
Studies
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In recent years, constraint propagation techniques have been shown to be highly effective for solving difficult scheduling problems. In this paper, we present an algorithm which combines constraint propagation with a problem decomposition approach in order to simplify the solution of the job shop scheduling problem. This is mainly guided by the observation that constraint propagation is more effective for 'small' problem instances. Roughly speaking, the algorithm consists of deducing operation sequences that are likely to occur in an optimal solution of the job shop scheduling problem (JSP). The algorithm for which the name edge-guessing procedure has been chosen - since with respect to the job shop scheduling problem (JSP) the deduction of machine sequences is mainly equivalent to orienting edges in a disjunctive graph - can be applied in a preprocessing step, reducing the solution space, thus speeding up the overall solution process. In spite of the heuristic nature of edge-guessing, it still leads to near-optimal solutions.
ISSN:0254-5330
1572-9338
DOI:10.1023/A:1021197120431