The One-Machine Problem with Delayed Precedence Constraints and its Use in Job Shop Scheduling

Egon Balas, Jan Karel Lenstra and Alkis Vazacopoulos
Additional contact information
Jan Karel Lenstra: Department of Mathematics and Computing Science, Eindhoven University of Technology, PO Box 513, Eindhoven 5600 MB, The Netherlands
Alkis Vazacopoulos: College of Business Administration, Fairleigh Dickinson University, 1000 River Road, Teaneck, New Jersey 07666

Management Science, 1995, vol. 41, issue 1, 94-109

Abstract: We study the one machine scheduling problem with release and delivery times and the minimum makespan objective, in the presence of constraints that for certain pairs of jobs require a delay between the completion of the first job and the start of the second (delayed precedence constraints). This problem arises naturally in the context of the Shifting Bottleneck Procedure for the general job shop scheduling problem, as a relaxation of the latter, tighter than the standard one-machine relaxation. The paper first highlights the difference between the two relaxations through some relevant complexity results. Then it introduces a modified Longest Tail Heuristic whose analysis identifies those situations that permit efficient branching. As a result, an optimization algorithm is developed whose performance is comparable to that of the best algorithms for the standard one-machine problem. Embedding this algorithm into a modified version of the Shifting Bottleneck Procedure that uses the tighter one-machine relaxation discussed here results in a considerable overall improvement in performance on all classes of job shop scheduling problems.

Keywords: job shop scheduling; delayed precedence constraints; Shifting Bottleneck Procedure (search for similar items in EconPapers)
Date: 1995
References: Add references at CitEc
Citations: View citations in EconPapers (20)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.41.1.94 (application/pdf)

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:inm:ormnsc:v:41:y:1995:i:1:p:94-109

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().