A Survey of Machine Scheduling Problems with Blocking and No-Wait in Process

Nicholas G. Hall and Chelliah Sriskandarajah
Additional contact information
Nicholas G. Hall: The Ohio State University
Chelliah Sriskandarajah: University of Toronto

Operations Research, 1996, vol. 44, issue 3, 510-525

Abstract: An important class of machine scheduling problems is characterized by a no-wait or blocking production environment, where there is no intermediate buffer between machines. In a no-wait environment, a job must be processed from start to completion, without any interruption either on or between machines. Blocking occurs when a job, having completed processing on a machine, remains on the machine until a downstream machine becomes available for processing. A no-wait or blocking production environment typically arises from characteristics of the processing technology itself, or from the absence of storage capacity between operations of a job. In this review paper, we describe several well-documented applications of no-wait and blocking scheduling models and illustrate some ways in which the increasing use of modern manufacturing methods gives rise to other applications. We review the computational complexity of a wide variety of no-wait and blocking scheduling problems and describe several problems which remain open as to complexity. We study several deterministic flowshop, jobshop, and openshop problems and describe efficient and enumerative algorithms, as well as heuristics and results about their performance. The literature on stochastic no-wait and blocking scheduling problems is also reviewed. Finally, we provide some suggestions for future research directions.

Keywords: production/scheduling; no-wait production environment; manufacturing; automated systems; review of complexity; algorithms and heuristics (search for similar items in EconPapers)
Date: 1996
References: Add references at CitEc
Citations: View citations in EconPapers (97)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.44.3.510 (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:oropre:v:44:y:1996:i:3:p:510-525

Access Statistics for this article

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