A survey of machine scheduling problems with blocking and no-wait in process

A survey of machine scheduling problems with blocking and no-wait in process

0.00 Avg rating0 Votes
Article ID: iaor20002784
Country: United States
Volume: 44
Issue: 3
Start Page Number: 510
End Page Number: 525
Publication Date: May 1996
Journal: Operations Research
Authors:
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.

Reviews

Required fields are marked *. Your email address will not be published.