Constraint Propagation and Problem Decomposition: A Preprocessing Procedure for the Job Shop Problem

Ulrich Dorndorf (), Erwin Pesch () and Toàn Phan-Huy ()

Annals of Operations Research, 2002, vol. 115, issue 1, 125-145

Abstract: 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. If combined with a heuristic algorithm, we will demonstrate that given the same amount of computation time, the additional application of edge-guessing leads to better solutions. This has been tested on a set of well-known JSP benchmark problem instances. Copyright Kluwer Academic Publishers 2002

Date: 2002
References: Add references at CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://hdl.handle.net/10.1023/A:1021197120431 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:115:y:2002:i:1:p:125-145:10.1023/a:1021197120431

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1023/A:1021197120431

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().