The DOI matches its Crossref record; 30 of the 30 references it cites were found in a registry or an index.
A Survey of Machine Scheduling Problems with Blocking and No-Wait in Process
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
(1979) · Cited by 43,841
Equation of State Calculations by Fast Computing Machines
Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H., & Teller, E. (1953) · The Journal of Chemical Physics · doi:10.1063/1.1699114 · Cited by 37,192
Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
Graham, R. L., Lawler, E. L., Lenstra, J. K., & Kan, A. H. G. R. (1979) · Annals of Discrete Mathematics · doi:10.1016/s0167-5060(08)70356-x · Cited by 5,854
Optimal two‐ and three‐stage production schedules with setup times included
Johnson, S. M. (1954) · Naval Research Logistics Quarterly · doi:10.1002/nav.3800010110 · Cited by 3,252
Introduction to Sequencing and Scheduling
Clewett, A. J., & Baker, K. R. (1977) · Operational Research Quarterly (1970-1977) · doi:10.2307/3009192 · Cited by 2,597
Complexity of Machine Scheduling Problems
Lenstra, J. K., Rinnooy Kan, A. H. G., & Brucker, P. (1977) · Annals of Discrete Mathematics · doi:10.1016/s0167-5060(08)70743-x · Cited by 2,197
The Traveling Salesman Problem
(2019) · Fundamentals of Supply Chain Theory · doi:10.1002/9781119584445.ch10 · Cited by 1,614
The Shifting Bottleneck Procedure for Job Shop Scheduling
Adams, J., Balas, E., & Zawack, D. J. (1988) · Management Science · doi:10.1287/mnsc.34.3.391 · Cited by 1,603
NP-complete scheduling problems
Ullman, J. D. (1975) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(75)80008-0 · Cited by 1,452
Scheduling subject to resource constraints: classification and complexity
Blazewicz, J., Lenstra, J. K., & Kan, A. H. G. R. (1983) · Discrete Applied Mathematics · doi:10.1016/0166-218x(83)90012-4 · Cited by 1,436
Computer and job-shop scheduling theory
Coffman, E. G., & Bruno, J. L. (1976) · Medical Entomology and Zoology · Cited by 1,107
Glover, F. (1990) · Interfaces · doi:10.1287/inte.20.4.74 · Cited by 1,092
Japanese Manufacturing Techniques: Nine Hidden Lessons in Simplicity
Mitchell, P. S., & Schonberger, R. J. (1983) · The Academy of Management Review · doi:10.2307/257841 · Cited by 976
Parallel Sequencing and Assembly Line Problems
Hu, T. C. (1961) · Operations Research · doi:10.1287/opre.9.6.841 · Cited by 898
Japanese manufacturing techniques
(1983) · Business Horizons · doi:10.1016/0007-6813(83)90111-8 · Cited by 782
Chapter 9 Sequencing and scheduling: Algorithms and complexity
Lawler, E. L., Lenstra, J. K., Rinnooy Kan, A. H. G., & Shmoys, D. B. (1993) · Handbooks in Operations Research and Management Science · doi:10.1016/s0927-0507(05)80189-6 · Cited by 761
Optimal scheduling for two-processor systems
Coffman, E. G., & Graham, R. L. (1972) · Acta Informatica · doi:10.1007/bf00288685 · Cited by 614
Complexity of Scheduling under Precedence Constraints
Lenstra, J. K., & Kan, A. H. G. R. (1978) · Operations Research · doi:10.1287/opre.26.1.22 · Cited by 557
Machine Scheduling Problems: Classification, complexity and computations
Kan, R. (1976) · Medical Entomology and Zoology · Cited by 478
Statistical cooling : a general approach to combinatorial optimization problems
Aarts, E. E., & Laarhoven, V. P. P. (1985) · Philips Journal of Research · Cited by 366
Recent Developments in Deterministic Sequencing and Scheduling: A Survey
Lawler, E. L., Lenstra, J. K., & Kan, A. H. G. R. (1982) · Springer eBooks · doi:10.1007/978-94-009-7801-0_3 · Cited by 325
Computational Complexity of Discrete Optimization Problems
Lenstra, J. K., & Rinnooy Kan, A. H. G. (1979) · Annals of Discrete Mathematics · doi:10.1016/s0167-5060(08)70821-5 · Cited by 292
Mitchell, P. S. (1983) · Academy of Management Review · doi:10.5465/amr.1983.4284620 · Cited by 284
Two-Processor Scheduling with Start-Times and Deadlines
Garey, M. R., & Johnson, D. S. (1977) · SIAM Journal on Computing · doi:10.1137/0206029 · Cited by 236
Deterministic Processor Scheduling
Gonzalez, M. J. (1977) · ACM Computing Surveys · doi:10.1145/356698.356700 · Cited by 216
Heuristics for flow-shop scheduling
KING, J. R., & SPACHIS, A. S. (1980) · International Journal of Production Research · doi:10.1080/00207548008919673 · Cited by 197
Sequencing by enumerative methods
Lenstra, J. K. (1977) · Data Archiving and Networked Services (DANS) · Cited by 164
Stochastic scheduling problems I — General strategies
Möhring, R. H., Radermacher, F. J., & Weiss, G. (1984) · Zeitschrift für Operations Research · doi:10.1007/bf01919323 · Cited by 159
Complexity of Scheduling Shops with No Wait in Process
Sahni, S. K., & Cho, Y. (1979) · Mathematics of Operations Research · doi:10.1287/moor.4.4.448 · Cited by 132
Worst-Case Analysis of Heuristic Algorithms
Fisher, M. L. (1980) · Management Science · doi:10.1287/mnsc.26.1.1 · Cited by 126
Cited by
A discrete particle swarm optimization algorithm for the no-wait flowshop scheduling problem
Pan, Q.-K., Fatih Tasgetiren, M., & Liang, Y.-C. (2008) · Computers & Operations Research · doi:10.1016/j.cor.2006.12.030 · Cited by 445
Flowshop-scheduling problems with makespan criterion: a review
Reza Hejazi *, S., & Saghafian, S. (2005) · International Journal of Production Research · doi:10.1080/0020754050056417 · Cited by 342
Guinet, A., & Chaabane, S. (2003) · International Journal of Production Economics · doi:10.1016/s0925-5273(03)00087-2 · Cited by 325
A novel hybrid discrete differential evolution algorithm for blocking flow shop scheduling problems
Wang, L., Pan, Q.-K., Suganthan, P. N., Wang, W.-H., & Wang, Y.-M. (2010) · Computers & Operations Research · doi:10.1016/j.cor.2008.12.004 · Cited by 254
Metadata
- Authors
- Hall, N. G., & Sriskandarajah, C.
- Venue
- Operations Research
- Published
- 1996-06
- Volume
- 44
- Issue
- 3
- Pages
- 510-525
- ISSN
- 0030-364X (ISSN-L)
- 1526-5463
- OpenAlex
- W2149884725
- Cited by
- 842
- References
- 30
- FWCI
- 54.50
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.