article

The Shifting Bottleneck Procedure for Job Shop Scheduling

Authors:

Joseph Adams,

Egon Balas,

Daniel ZawackAuthors Info & Claims

Management Science, Volume 34, Issue 3

Pages 391 - 401

Published: 01 March 1988 Publication History

Abstract

We describe an approximation method for solving the minimum makespan problem of job shop scheduling. It sequences the machines one by one, successively, taking each time the machine identified as a bottleneck among the machines not yet sequenced. Every time after a new machine is sequenced, all previously established sequences are locally reoptimized. Both the bottleneck identification and the local reoptimization procedures are based on repeatedly solving certain one-machine scheduling problems. Besides this straight version of the Shifting Bottleneck Procedure, we have also implemented a version that applies the procedure to the nodes of a partial search tree. Computational testing shows that our approach yields consistently better results than other procedures discussed in the literature. A high point of our computational testing occurred when the enumerative version of the Shifting Bottleneck Procedure found in a little over five minutes an optimal schedule to a notorious ten machines/ten jobs problem on which many algorithms have been run for hours without finding an optimal solution.

References

[1]

BAKER, K. R., Introduction to Sequencing and Scheduling, Wiley, New York, 1974.

Google Scholar

[2]

BALAS, E., "Machine Sequencing via Disjunctive Graphs: An Implicit Enumeration Algorithm," Oper. Res., 17 (1969), 941-957.

Digital Library

Google Scholar

[3]

CARLIER, J., "The One-Machine Sequencing Problem," European J. Oper. Res., 11 (1982), 42-47.

Crossref

Google Scholar

[4]

CONWAY, R. N., W. L. MAXWELL AND L. W. MILLER, Theory of Scheduling. Addison-Wesley, Reading, MA, 1967.

Google Scholar

[5]

FRENCH, S., Sequencing and Scheduling: An Introduction to the Mathematics of the Job Shop, Wiley, New York, 1982.

Google Scholar

[6]

GAREY, M. R. AND D. S. JOHNSON, Computers and Intractability, W. H. Freeman and Co., San Francisco, 1979.

Google Scholar

[7]

LAWRENCE, S., Supplement to "Resource Constrained Project Scheduling: An Experimental Investigation of Heuristic Scheduling Techniques," GSIA, Carnegie-Mellon University, October 1984.

Google Scholar

[8]

LENSTRA, J. K., Sequencing by Enumerative Methods, Mathematical Centre Tract 69, Mathematisch Centrum, Amsterdam, 1976.

Google Scholar

[9]

LENSTRA, J. K., Personal communication, May 1986.

Google Scholar

[10]

MCMAHON, G. AND M. FLORIAN, "On Scheduling with Ready Times and Due Dates to Minimize Maximum Lateness," Oper. Res., 23 (1975), 475-482.

Digital Library

Google Scholar

[11]

MUTH, J. F., AND G. L. THOMPSON, Industrial Scheduling, Prentice-Hall, Englewood Cliffs, N.J., 1963.

Google Scholar

[12]

RINNOOY KAN, A. H. G., Machine Scheduling Problems: Classification, Complexity and Computations, Nijhoff, The Hague, 1976.

Google Scholar

[13]

ROY, B., AND B. SUSSMAN, "Les probl¿mes d'ordonnancement avec contraintes disjonctives," Note DS No. 9 bis, SEMA, Paris, 1964.

Google Scholar

Cited By

View all

Zhang WSauppe JJacobson S(2021)An Improved Branch-and-Bound Algorithm for the One-Machine Scheduling Problem with Delayed Precedence ConstraintsINFORMS Journal on Computing10.1287/ijoc.2020.098833:3(1091-1102)Online publication date: 1-Jul-2021
https://dl.acm.org/doi/10.1287/ijoc.2020.0988
Weise TLi XChen YWu ZKrawiec K(2021)Solving job shop scheduling problems without using a bias for good solutionsProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3449726.3463124(1459-1466)Online publication date: 7-Jul-2021
https://dl.acm.org/doi/10.1145/3449726.3463124
Zang ZWang WSong YLu LLi WWang YZhao Y(2019)Hybrid Deep Neural Network Scheduler for Job-Shop Problem Based on Convolution Two-Dimensional TransformationComputational Intelligence and Neuroscience10.1155/2019/71728422019Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1155/2019/7172842
Show More Cited By

Index Terms

The Shifting Bottleneck Procedure for Job Shop Scheduling
1. Applied computing
  1. Enterprise computing
  2. Operations research
    1. Industry and manufacturing
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Scheduling algorithms
    2. Online algorithms
      1. Online learning algorithms
        Scheduling algorithms
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning
        Sequential decision making

Recommendations

Effective ensembles of heuristics for scheduling flexible job shop problem with new job insertion

Flexible job shop scheduling problem.Ensembles of heuristics.Re-scheduling for new job insertion.Multiple objectives scheduling problem. This study investigates the flexible job shop scheduling problem (FJSP) with new job insertion. FJSP with new job ...
A distributed shifting bottleneck heuristic for complex job shops

In this paper, we consider distributed versions of a modified shifting bottleneck heuristic for complex job shops. The considered job shop environment contains parallel batching machines, machines with sequence-dependent setup times and reentrant ...
Performance Measures and Schedules in Periodic Job Shops

This paper discusses the periodic job shop scheduling problem, a problem where an identical mixture of items, called a minimal part set MPS, is repetitively produced. The performance and behavior of schedules are discussed. Two basic performance ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Management Science Volume 34, Issue 3

March 1988

178 pages

ISSN:0025-1909

Issue’s Table of Contents

Publisher

INFORMS

Linthicum, MD, United States

Publication History

Published: 01 March 1988

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

160
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 02 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Zhang WSauppe JJacobson S(2021)An Improved Branch-and-Bound Algorithm for the One-Machine Scheduling Problem with Delayed Precedence ConstraintsINFORMS Journal on Computing10.1287/ijoc.2020.098833:3(1091-1102)Online publication date: 1-Jul-2021
https://dl.acm.org/doi/10.1287/ijoc.2020.0988
Weise TLi XChen YWu ZKrawiec K(2021)Solving job shop scheduling problems without using a bias for good solutionsProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3449726.3463124(1459-1466)Online publication date: 7-Jul-2021
https://dl.acm.org/doi/10.1145/3449726.3463124
Zang ZWang WSong YLu LLi WWang YZhao Y(2019)Hybrid Deep Neural Network Scheduler for Job-Shop Problem Based on Convolution Two-Dimensional TransformationComputational Intelligence and Neuroscience10.1155/2019/71728422019Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1155/2019/7172842
Zhang JDing GZou YQin SFu J(2019)Review of job shop scheduling research and its new perspectives under Industry 4.0Journal of Intelligent Manufacturing10.1007/s10845-017-1350-230:4(1809-1830)Online publication date: 1-Apr-2019
https://dl.acm.org/doi/10.1007/s10845-017-1350-2
Lara-Cárdenas ESánchez-Díaz XAmaya IOrtiz-Bayliss J(2019)Improving Hyper-heuristic Performance for Job Shop Scheduling Problems Using Neural NetworksAdvances in Soft Computing10.1007/978-3-030-33749-0_13(150-161)Online publication date: 27-Oct-2019
https://dl.acm.org/doi/10.1007/978-3-030-33749-0_13
McDermott JMoraglio A(2019)Program Trace Optimization with Constructive Heuristics for Combinatorial ProblemsEvolutionary Computation in Combinatorial Optimization10.1007/978-3-030-16711-0_13(196-212)Online publication date: 24-Apr-2019
https://dl.acm.org/doi/10.1007/978-3-030-16711-0_13
Nagata YOno I(2018)A guided local search with iterative ejections of bottleneck operations for the job shop scheduling problemComputers and Operations Research10.1016/j.cor.2017.09.01790:C(60-71)Online publication date: 1-Feb-2018
https://dl.acm.org/doi/10.1016/j.cor.2017.09.017
Hoorn J(2018)The Current state of bounds on benchmark instances of the job-shop scheduling problemJournal of Scheduling10.1007/s10951-017-0547-821:1(127-128)Online publication date: 1-Feb-2018
https://dl.acm.org/doi/10.1007/s10951-017-0547-8
Pérez-Rodríguez RHernández-Aguirre A(2018)A hybrid estimation of distribution algorithm for flexible job-shop scheduling problems with process plan flexibilityApplied Intelligence10.1007/s10489-018-1160-z48:10(3707-3734)Online publication date: 1-Oct-2018
https://dl.acm.org/doi/10.1007/s10489-018-1160-z
Karunakaran DMei YChen GZhang MBosman P(2017)Toward evolving dispatching rules for dynamic job shop scheduling under uncertaintyProceedings of the Genetic and Evolutionary Computation Conference10.1145/3071178.3071202(282-289)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1145/3071178.3071202
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

Effective ensembles of heuristics for scheduling flexible job shop problem with new job insertion

A distributed shifting bottleneck heuristic for complex job shops

Performance Measures and Schedules in Periodic Job Shops

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations