The DOI matches its Crossref record.
A Computational Study of the Job-Shop Scheduling Problem
Abstract
The job-shop scheduling problem is a notoriously difficult problem in combinatorial optimization. Although even modest sized instances remain computationally intractable, a number of important algorithmic advances have been made in recent years by J. Adams, E. Balas and D. Zawack; J. Carlier and E. Pinson; B. J. Lageweg, J. K. Lenstra and A. H. G. Rinnooy Kan; and others. Making use of a number of these advances, we have designed and implemented a new heuristic procedure for finding schedules, a cutting-plane method for obtaining lower bounds, and a combinatorial branch and bound algorithm. Our optimization procedure, combining the heuristic method and the combinatorial branch and bound algorithm, solved the well-known 10×10 problem of J. F. Muth and G. L. Thomson in under 7 minutes of computation time on a Sun Sparcstation 1. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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
Cited by
Chaff: engineering an efficient SAT solver
Moskewicz, M. W., Madigan, C. F., Zhao, Y., Zhang, L., & Malik, S. (2001) · Proceedings of the 38th conference on Design automation - DAC '01 · doi:10.1145/378239.379017 · Cited by 2,940
Handbook of Constraint Programming
(2006) · Foundations of Artificial Intelligence · doi:10.1016/s1574-6526(06)x8001-x · Cited by 1,483
Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems
Shaw, P. (1998) · Lecture Notes in Computer Science · doi:10.1007/3-540-49481-2_30 · Cited by 1,366
Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms
Bräysy, O., & Gendreau, M. (2005) · Transportation Science · doi:10.1287/trsc.1030.0056 · Cited by 1,135
Integer and combinatorial optimization
(1999) · Computers & Mathematics with Applications · doi:10.1016/s0898-1221(99)91259-2 · Cited by 1,117
Deterministic job-shop scheduling: Past, present and future
Jain, A. S., & Meeran, S. (1999) · European Journal of Operational Research · doi:10.1016/s0377-2217(98)00113-1 · Cited by 782
New Search Spaces for Sequencing Problems with Application to Job Shop Scheduling
Storer, R. H., Wu, S. D., & Vaccari, R. (1992) · Management Science · doi:10.1287/mnsc.38.10.1495 · Cited by 546
The job shop scheduling problem: Conventional and new solution techniques
Błażewicz, J., Domschke, W., & Pesch, E. (1996) · European Journal of Operational Research · doi:10.1016/0377-2217(95)00362-2 · Cited by 536
Exploring relaxation induced neighborhoods to improve MIP solutions
Danna, E., Rothberg, E., & Pape, C. L. (2005) · Mathematical Programming · doi:10.1007/s10107-004-0518-7 · Cited by 530
A branch and bound algorithm for the job-shop scheduling problem
Brucker, P., Jurisch, B., & Sievers, B. (1994) · Discrete Applied Mathematics · doi:10.1016/0166-218x(94)90204-6 · Cited by 499
Algorithms for Hybrid MILP/CP Models for a Class of Optimization Problems
Jain, V., & Grossmann, I. E. (2001) · INFORMS Journal on Computing · doi:10.1287/ijoc.13.4.258.9733 · Cited by 400
Smart Manufacturing Scheduling With Edge Computing Using Multiclass Deep Q Network
Lin, C.-C., Deng, D.-J., Chih, Y.-L., & Chiu, H.-T. (2019) · IEEE Transactions on Industrial Informatics · doi:10.1109/tii.2019.2908210 · Cited by 342
Park, J., Chun, J., Kim, S. H., Kim, Y., & Park, J. (2021) · International Journal of Production Research · doi:10.1080/00207543.2020.1870013 · Cited by 329
Cheng, R., Gen, M., & Tsujimura, Y. (1999) · Computers & Industrial Engineering · doi:10.1016/s0360-8352(99)00022-4 · Cited by 323
Three Scheduling Algorithms Applied to the Earth Observing Systems Domain
Wolfe, W. J., & Sorensen, S. E. (2000) · Management Science · doi:10.1287/mnsc.46.1.148.15134 · Cited by 313
Cheng, R., Gen, M., & Tsujimura, Y. (1999) · Computers & Industrial Engineering · doi:10.1016/s0360-8352(99)00136-9 · Cited by 303
Sakawa, M., & Kubota, R. (2000) · European Journal of Operational Research · doi:10.1016/s0377-2217(99)00094-6 · Cited by 287
Actor-Critic Deep Reinforcement Learning for Solving Job Shop Scheduling Problems
Liu, C.-L., Chang, C.-C., & Tseng, C.-J. (2020) · IEEE Access · doi:10.1109/access.2020.2987820 · Cited by 281
Genetic programming for production scheduling: a survey with a unified framework
Nguyen, S., Mei, Y., & Zhang, M. (2017) · Complex & Intelligent Systems · doi:10.1007/s40747-017-0036-x · Cited by 279
Ant colony optimization combined with taboo search for the job shop scheduling problem
Huang, K.-L., & Liao, C.-J. (2008) · Computers & Operations Research · doi:10.1016/j.cor.2006.07.003 · Cited by 278
Ajagekar, A., Humble, T., & You, F. (2020) · Computers & Chemical Engineering · doi:10.1016/j.compchemeng.2019.106630 · Cited by 191
“Job-shop scheduling problems belong to the class of most intractable NP-hard combinatorial optimization problems, and pose a significant computational challenge due to its large and complex search space [43].”
Background(2005) · Cited by 38
Improving Quantum Annealing Performance on Embedded Problems
(2020) · Supercomputing Frontiers and Innovations · doi:10.14529/jsfi200403 · Cited by 6
Metadata
- Authors
- Applegate, D., & Cook, W.
- Venue
- ORSA Journal on Computing
- Published
- 1991-05
- Volume
- 3
- Issue
- 2
- Pages
- 149-156
- ISSN
- 0899-1499 (ISSN-L)
- 2326-3245
- OpenAlex
- W2071306171
- Cited by
- 908
- References
- 0
- FWCI
- 32.53
- 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.