Skip to main content
SpringerLink
Log in

A Computational Study of Shifting Bottleneck Procedures for Shop Scheduling Problems

  • Published:
Journal of Heuristics Aims and scope Submit manuscript

Abstract

We examine the performance of Shifting Bottleneck (SB) heuristics for shop scheduling problems where the performance measure to be minimized is makespan (C max) or maximum lateness (L max). Extensive computational experiments are conducted on benchmark problems from the literature as well as several thousand randomly generated test problems with three different routing structures and up to 1000 operations. Several different versions of SB are examined to determine the effect on solution quality and time of different subproblem solution procedures, reoptimization procedures and bottleneck selection criteria. Results show that the performance of SB is significantly affected by job routings, and that SB with optimal subproblem solutions and full reoptimization at each iteration consistently outperforms dispatching rules, but requires high computation times for large problems. High quality subproblem solutions and reoptimization procedures are essential to obtaining good solutions. We also show that schedules developed by SB to minimize L max perform well with respect to several other performance measures, rendering them more attractive for practical use.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Aarts, E.H.L.,P.J.M. van Laarhoven, J.K. Lenstra, N.L.J. Ulder. (1994). “A Computational Study of Local Search Algorithms for Job Shop Scheduling.” ORSA Journal on Computing 6, 118–125.

    MATH  Google Scholar 

  • Adams, J., E. Balas, and D. Zawack. (1988). “The Shifting Bottleneck Procedure for Job Shop Scheduling.” Management Science 3, 391–401.

    Article  MathSciNet  Google Scholar 

  • Ahuja, R.K., T.L. Magnanti, J.B. Orlin. (1993). Network Flows: Theory, Algorithms and Applications Prentice-Hall.

  • Applegate, D., and W. Cook. (1991). “A Computational Study of Job Shop Scheduling.” ORSA Journal on Computing 3, 149–156.

    MATH  Google Scholar 

  • Balas, E. (1969). “Machine Sequencing via Disjunctive Graphs: An Implicit Enumeration Approach.” Operations Research 17, 941–957.

    Article  MathSciNet  MATH  Google Scholar 

  • Balas, E. (1970). “Project Scheduling with Resource Constraints.” In E.M.L. Beale (ed.) Applications of Mathematical Programming Techniques. London: The English Universities Press Ltd.

    Google Scholar 

  • Balas, E., J.K. Lenstra, and A. Vazacopoulos. (1995). “The One Machine Problem with Delayed Precedence Constraints and Its Use in Job Shop Scheduling.” Management Science 41, 94–109.

    Article  MATH  Google Scholar 

  • Bhaskaran, K., and E. Pinedo. (1991). Dispatching,Chapter 83 of Handbook of Industrial Engineering, G. Salvendy (ed.) New York: J. Wiley.

    Google Scholar 

  • Blackstone, J.H., D.T. Phillips, and G.L. Hogg. (1982). “A State-of-the-Art Survey of Dispatching Rules for Manufacturing Job Shop Operations.” International Journal of Production Research 20, 27–45.

    Article  Google Scholar 

  • Carlier, J. (1982). “The One Machine Sequencing Problem.” European Journal of Operational Research 11, 42–47.

    Article  MathSciNet  MATH  Google Scholar 

  • Carlier, J. and E. Pinson. (1989). “An Algorithm for Solving the Job-Shop Problem.” Management Science 35, 164–176.

    Article  MathSciNet  MATH  Google Scholar 

  • Dauzere-Peres, S. (1995). “AProcedure for the One Machine Sequencing Problem with Dependent Jobs.” European Journal of Operational Research 81, 579–589.

    Article  MATH  Google Scholar 

  • Dauzere-Peres, S. and J.B. Lasserre. (1993). “AModified Shifting Bottleneck Procedure for Job Shop Scheduling.” International Journal of Production Research 31, 923–932.

    Article  MATH  Google Scholar 

  • Demirkol, E., S.V. Mehta, and R. Uzsoy. “Benchmarks for Shop Scheduling Problems.” European Journal of Operational Research(forthcoming).

  • Dorndorf, U., E. Pesch. (1996). “Evolution-Based Learning in a Job Shop Scheduling Environment.” Computers and Operations Research 22, 25–40.

    Article  Google Scholar 

  • Garey, M.R. and D.S. Johnson. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco: W.H. Freeman.

    MATH  Google Scholar 

  • Hoitomt, D.J., P.B. Luh, K.R. Pattipati. (1993). “A Practical Approach to Job Shop-Scheduling Problems.” IEEE Transactions on Robotics and Automation 9, 1–13.

    Article  Google Scholar 

  • Holtsclaw, H.H. and R. Uzsoy. (1996). “Machine Criticality Measures and Subproblem Solution Procedures in Shifting Bottleneck Methods: A Computational Study.” Journal of the Operational Research Society 47, 666–677.

    MATH  Google Scholar 

  • Kempf, K., B. Russell, S. Sidhu, and S. Barrett. (1991). “Artificially Intelligent Schedulers in Manufacturing Practice.” AI Magazine 11, 46–56.

    Google Scholar 

  • Lasserre, J.B. (1992). “An Integrated Model for Job Shop Planning and Scheduling.” Management Science 38, 1201–1211.

    Article  MATH  Google Scholar 

  • Lawler, E.L., J.K. Lenstra, A.H.G. Rinnooy Kan, and D.B. Shmoys. (1993). “Sequencing and Scheduling: Algorithms and Complexity}.” In S.C. Graves, A.H.G. Rinnooy Kan, P. Zipkin (eds.), Handbooks in Operations Research and Management Science Vol. 4 : Logistics of Production and Inventory. North-Holland.

  • Lawrence, S.R., S.E. Sewell. “Heuristic versus Schedules When Processing Times are Uncertain.” Journal of Operations Management(forthcoming).

  • Lenstra, J.K. (1977). Sequencing by Enumerative Methods. Amsterdam: Mathematical Center Tract 69, Mathematisch Centrum.

    MATH  Google Scholar 

  • Lourenco, H. (1995). “Job Shop Scheduling: Computational Study of Local Search and Large-Setup Optimization Methods.” European Journal of Operational Research 83, 347–364.

    Article  MATH  Google Scholar 

  • Luh, P.B., D.J. Hoitomt. (1993). “Scheduling of Manufacturing Systems Using the Lagrangian Relaxation Technique.” IEEE Transactions on Automatic Control 38, 1066–1079.

    Article  MathSciNet  Google Scholar 

  • Matsuo, H., C.J. Suh and R.S. Sullivan. (1988). “A Controlled Search Simulated Annealing Approach for the General Job Shop Scheduling Problem.” Department of Management, Graduate School of Business, University of Texas at Austin.

    Google Scholar 

  • Mehta, S.V., R. Uzsoy. “Predictable Scheduling of a Job Shop Subject to Breakdowns.” IEEE Transactions on Robotics and Automation(forthcoming).

  • Morton, T.E., R.M. Rachamadugu, A. Vepsalainen. (1984). “Accurate Myopic Heuristics for Tardiness Scheduling.” Research Report, Graduate School of Industrial Administration, Carnegie-Mellon University.

    Google Scholar 

  • Nowicki, E., C. Smutnicki. (1996). “A Fast Taboo Search Algorithm for the Job Shop Problem.” Management Science 42, 797–813.

    Article  MATH  Google Scholar 

  • Ovacik, I.M. and R. Uzsoy. (1992). “A Shifting Bottleneck Algorithm for Scheduling Semiconductor Testing Operations.” Journal of Electronics Manufacturing 2, 119–134.

    Article  Google Scholar 

  • Ovacik, I.M. and R. Uzsoy. (1994). “Exploiting Shop Floor Status Information to Schedule Complex Job Shops.” Journal of Manufacturing Systems 13, 73–84.

    Article  Google Scholar 

  • Ovacik, I.M., R. Uzsoy. (1995). “Decomposition Methods for Scheduling Semiconductor Testing Facilities.” Research Report, School of Industrial Engineering, Purdue University.

    Google Scholar 

  • Ovacik, I.M., R. Uzsoy. (1997). Decomposition Methods for Complex Factory Scheduling Problems. Kluwer Academic Publishers

  • Panwalkar, S.S., and W. Iskander. (1997). “A Survey of Scheduling Rules.” Operations Research 25, 45–61.

  • Pinedo, M. (1995). Scheduling: Theory, Algorithms, and Systems. New Jersey: Prentice Hall.

    MATH  Google Scholar 

  • Ramasesh, R. (1990). Dynamic Job Shop Scheduling: A Survey of Simulation Research, OMEGA 18, 43–57.

    Article  Google Scholar 

  • Roy, B. and B. Sussmann. (1964). Les Problems d'Ordonnancement avec Contraintes Disjonctives, Notes DS No. 9 bis, SEMA, Montrouge.

    Google Scholar 

  • Sadeh, N. (1991). Look-Ahead Techniques for Micro-Opportunistic Job Shop Scheduling. Ph.D. thesis, Pittsburgh, PA, School of Computer Science, Carnegie-Mellon University.

    Google Scholar 

  • Schutten, J.M.J. (1995). “Practical Job Shop Scheduling.”Working Paper LPOM-95-12, Laboratory of Production and Operations Management, Department of Mechanical Engineering, University of Twente, The Netherlands

    Google Scholar 

  • Storer, R.H., S.D. Wu, and R. Vaccari. (1992). “New Search Spaces for Sequencing Problems with Applicationto Job Shop Scheduling.” Management Science 38, 1495-1509.

    Article  MATH  Google Scholar 

  • Storer, R.H., S.D. Wu, and R. Vaccari. (1995). “Problem and Heuristic Space Search Strategies for Job Shop Scheduling.” ORSA Journal on Computing 7, 453–467.

    MATH  Google Scholar 

  • Taillard, E. (1993). “Benchmarks for Basic Scheduling Problems.” European Journal of Operational Research 64, 278–285.

    Article  MATH  Google Scholar 

  • Taillard, E.D. (1994). “Parallel Taboo Search Techniques for the Job Shop Scheduling Problem.” ORSA Journal on Computing 6, 108–117.

    MATH  Google Scholar 

  • Uzsoy, R., C.-Y. Lee, and L.A. Martin-Vega. (1992). “A Review of Production Planning and Scheduling Models in the Semiconductor Industry, Part I: System Characteristics, Performance Evaluation and Production Planning.” IIE Transactions on Scheduling and Logistics 24, 47–59.

    Google Scholar 

  • Uzsoy, R., C.Y. Lee, and L.A. Martin-Vega. (1994). “A Survey of Production Planning and Scheduling Models in the Semiconductor Industry, Part II: Shop-Floor Control.” IIE Transactions on Scheduling and Logistics 26, 44–45.

    Google Scholar 

  • Van Laarhoven, P.J.M., E.H.L. Aarts, and J.K. Lenstra. (1992). “Job Shop Scheduling by Simulated Annealing.” Operations Research 40, 113–125.

    Article  MathSciNet  MATH  Google Scholar 

  • Vepsalainen, A.P.L. and T.E. Morton. (1988). “Improving Local Priority Rules Global Lead-Time Estimates: A Simulation Study.” Journal of Manufacturing and Operations Management 1, 102–118.

    Google Scholar 

  • White, K.P. and V.R. Rogers. (1990). “Job-shop Scheduling: Limits of the Binary Disjunctive Formulation.” International Journal of Production Research 28, 2187–2200.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Industrial Engineering, Purdue University, West Lafayette, IN, 47907

    Ebru Demirkol

  2. i2 Technologies, Irving, TX

    Sanjay Mehta

  3. School of Industrial Engineering, Purdue University, West Lafayette, IN, 47907

    Reha Uzsoy

Authors
  1. Ebru Demirkol
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Sanjay Mehta
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Reha Uzsoy
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Demirkol, E., Mehta, S. & Uzsoy, R. A Computational Study of Shifting Bottleneck Procedures for Shop Scheduling Problems. Journal of Heuristics 3, 111–137 (1997). https://doi.org/10.1023/A:1009627429878

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1009627429878

Search

Navigation