Hostname: page-component-7b7567c8c-z4zkx Total loading time: 0 Render date: 2026-11-16T11:10:59.662Z Has data issue: false hasContentIssue false

Embedding temporal constraint propagation in machine sequencing for job shop scheduling1

Published online by Cambridge University Press:  27 February 2009

Wesley W. Chu
Affiliation:
Computer Science Department, University of California, Los Angeles, CA 90024, U.S.A.
Patrick H. Ngai
Affiliation:
Computer Science Department, University of California, Los Angeles, CA 90024, U.S.A.

Abstract

In this paper, we show how a temporal constraint propagation technique can be embedded in the machine sequencing approach for solving the job shop scheduling problem. The temporal constraint propagation algorithm propagates the precedence constraints and machine interference constraints to reduce the search space generated by the machine sequencing approach. Further, by making use of the temporal nature of the job shop scheduling, efficient algorithms to propagate precedence constraints and machine interference constraints are developed. Experimental results reveal that embedding constraint propagation in the machine sequencing approach significantly reduces the computation time more than by just using the machine sequencing approach alone. Further, the proposed temporal constraint propagation algorithms provide an order of magnitude improvement on the computation time over the conventional constraint propagation algorithm.

Information

Type
Research Article
Copyright
Copyright © Cambridge University Press 1993

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable