A SURVEY OF MACHINE SCHEDULING PROBLEMS WITH BLOCKING AND NO-WAIT IN-PROCESS

An important class of machine scheduling problems is characterized by a no-wait or blocking production environment, where there is no interm ediate buffer between machines. in a no-wait environment, a job must b e processed from start to completion, without any interruption either on or between machines. Blocking occurs when a job, having completed p rocessing on a machine, remains an the machine until a downstream mach ine becomes available for processing. A no-wait or blocking production environment typically arises from characteristics of the processing t echnology itself, or from the absence of storage capacity between oper ations of a job. In this review paper, we describe several well-docume nted applications of no-wait and blocking scheduling models and illust rate some ways in which the increasing use of modern manufacturing met hods gives rise to other applications. We review the computational com plexity of a wide variety of no-wait and blocking scheduling problems and describe several problems which remain open as to complexity. We s tudy several deterministic flowshop, jobshop, and openshop problems an d 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 pr ovide some suggestions for future research directions.