A survey of machine scheduling problems with blocking and no-wait in process
成果类型：
Review
署名作者：
Hall, NG; Sriskandarajah, C
署名单位：
University of Toronto
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.44.3.510
发表日期：
1996
页码：
510-525
关键词：
摘要：
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 an 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 an stochastic no-wait and blocking scheduling problems is also reviewed. Finally, we provide some suggestions for future research directions.