IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v34y1988i3p391-401.html
   My bibliography  Save this article

The Shifting Bottleneck Procedure for Job Shop Scheduling

Author

Listed:
  • Joseph Adams

    (Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, Pennsylvania 15213)

  • Egon Balas

    (Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, Pennsylvania 15213)

  • Daniel Zawack

    (American Airlines)

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.

Suggested Citation

  • Joseph Adams & Egon Balas & Daniel Zawack, 1988. "The Shifting Bottleneck Procedure for Job Shop Scheduling," Management Science, INFORMS, vol. 34(3), pages 391-401, March.
    • Handle: RePEc:inm:ormnsc:v:34:y:1988:i:3:p:391-401
    DOI: 10.1287/mnsc.34.3.391
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/mnsc.34.3.391
    Download Restriction: no
    File URL: https://libkey.io/10.1287/mnsc.34.3.391?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ormnsc:v:34:y:1988:i:3:p:391-401. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.