Skip to main content
SpringerLink
Log in

Configuration and the advantages of the shifting bottleneck procedure for optimizing the job shop total weighted tardiness scheduling problem

  • Published:
Journal of Scheduling Aims and scope Submit manuscript

Abstract

This paper answers two fundamental questions concerning the usage of the shifting bottleneck (SB) procedure to optimize the criterion total weighted tardiness for the classical job shop scheduling problem. The first question is how to configure the SB procedure, as it is a divide-and-conquer method and consists of diverse subsolutions for each procedure phase. The second question is what the advantages of the SB procedure are, in comparison with other state-of-the-art approaches. To answer the first question, we evaluate the performance (i.e. the scheduling quality) and the efficiency (i.e. the computational time) of various SB variants using computational experiments and present guidelines for configuring the SB procedure. To respond to the second question, extensive computational experiments were conducted on various benchmark instances (up to 100 jobs \(\times \) 20 machines). Results show the superior performance/efficiency trade-off of the SB variants with certain configuration to local search methods. This excellent trade-off between performance and efficiency makes the SB procedure particularly promising for solving practical production scheduling problems.

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

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16

Similar content being viewed by others

Notes

  1. Due to a later update of the computational times of SB(VNS, 1) for the test instances, the time limit for MDL are no longer exactly 10 times of the mean time of the SB(VNS, 1). The exact factors are 9.9 for f = 2.4, 9.6 for f = 2.6 and 11.2 for f = 2.7.

References

  • Adams, J., Balas, E., & Zawack, D. (1988). The shifting bottleneck procedure for job shop scheduling. Management Science, 34(3), 391–401.

    Article  Google Scholar 

  • Applegate, D., & Cook, W. (1991). A computational study of the job-shop scheduling problem. ORSA Journal on Computing, 3(2), 149–156.

    Article  Google Scholar 

  • Bellman, R. (1958). On a routing problem. Quarterly of Applied Mathematics, 16, 87–90.

    Google Scholar 

  • Bülbül, K. (2011). A hybrid shifting bottleneck-tabu search heuristic for the job shop total weighted tardiness problem. Computers & Operations Research, 38, 967–983.

    Article  Google Scholar 

  • Bülbül, K., & Kaminsky, P. (2013). A linear programming-based method for job shop scheduling. Journal of Scheduling, 16, 161–183.

    Article  Google Scholar 

  • Chen, J. Y., Pfund, M. E., Fowler, J. W., Montgomery, D. C., & Callarman, T. E. (2010). Robust scaling parameters for composite dispatching rules. IIE Transactions, 42(11), 842–853.

    Article  Google Scholar 

  • Dauzere-Peres, S. (1995). A procedure for the one-machine sequencing problem with dependent jobs. European Journal of Operational Research, 81(3), 579–589.

    Article  Google Scholar 

  • Dauzere-Peres, S., & Lasserre, J.-B. (1993). A modified shifting bottleneck procedure for job-shop scheduling. International Journal of Production Research, 31(4), 923–932.

    Article  Google Scholar 

  • Demirkol, E., Mehta, S., & Uzsoy, R. (1997). A computational study of shifting bottleneck procedures for shop scheduling problems. Journal of Heuristics, 3, 111–137.

    Article  Google Scholar 

  • Geiger, M. J. (2010). On heuristic search for the single machine total weighted tardiness problem—Some theoretical insights and their empirical verification. European Journal of Operational Research, 207(3), 1235–1243.

    Article  Google Scholar 

  • Gordon, V., Strusevich, V., & Dolgui, A. (2012). Scheduling with due date assignment under special conditions on job processing. Journal of Scheduling, 15, 447–456.

    Article  Google Scholar 

  • Graham, R., Lawler, E., Lenstra, J., & Kan, A. (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 5, 287–326.

    Article  Google Scholar 

  • Hansen, P., & Mladenović, N. (2002). Developments of variable neighbourhood search. In C. C. Ribeiro & P. Hansen (Eds.), Essays and surveys in metaheuristics (pp. 415–439). Boston: Kluwer Academic Publishers.

    Chapter  Google Scholar 

  • Holthaus, O., & Rajendran, C. (2000). Efficient jobshop dispatching rules: Further developments. Production Planning & Control, 11(2), 171–178.

    Article  Google Scholar 

  • Holtsclaw, H. H., & Uzsoy, R. (1996). Machine criticality measures and subproblem solution procedures in shifting bottleneck methods: A computational study. The Journal of the Operational Research Society, 47(5), 666–677.

    Article  Google Scholar 

  • Kreipl, S. (2000). A large step random walk for minimizing total weighted tardiness in a job shop. Journal of Scheduling, 3, 125–138.

    Article  Google Scholar 

  • Lee, Y. H., & Pinedo, M. (1997). Scheduling jobs on parallel machines with sequence-dependent setup times. European Journal of Operational Research, 100(3), 464–474.

    Article  Google Scholar 

  • Mati, Y., Dauzere-Peres, S., & Lahlou, C. (2011). A general approach for optimizing regular criteria in the job-shop scheduling problem. European Journal of Operational Research, 212(1), 33–42.

    Article  Google Scholar 

  • Mason, S. J., Fowler, J. W., & Carlyle, W. M. (2002). A modified shifting bottleneck heuristic for minimizing total weighted tardiness in complex job shops. Journal of Scheduling, 5(3), 247–262.

    Article  Google Scholar 

  • Mason, S. J., Fowler, J. W., Carlyle, W. M., & Montgomery, D. C. (2005). Heuristics for minimizing total weighted tardiness in complex job shops. International Journal of Production Research, 43(10), 1943–1963.

    Article  Google Scholar 

  • Mladenović, N., & Hansen, P. (1997). Variable neighborhood search. Computers & Operations Research, 24, 1097–1100.

    Article  Google Scholar 

  • Mönch, L., Schabacker, R., Pabst, D., & Fowler, J. W. (2007). Genetic algorithm-based subproblem solution procedures for a modified shifting bottleneck heuristic for complex job shops. European Journal of Operational Research, 177(3), 2100–2118.

    Article  Google Scholar 

  • Mönch, L., & Zimmermann, J. (2007). Simulation-based assessment of machine criticality measures for a shifting bottleneck scheduling approach in complex manufacturing systems. Computers in Industry, 58(7), 644–655.

    Article  Google Scholar 

  • Muth, J., & Thompson, G. (1963). Industrial scheduling. Englewood Cliffs, NJ: Prentice-Hall.

    Google Scholar 

  • Ovacikt, I. M., & Uzsoy, R. (1992). A shifting bottleneck algorithm for scheduling semiconductor testing operations. Journal of Electronics Manufacturing, 2(3), 119–134.

    Article  Google Scholar 

  • Ovacikt, I. M., & Uzsoy, R. (1997). Decomposition methods for complex factory scheduling problems. New York: Springer.

    Book  Google Scholar 

  • Pfund, M. E., Balasubramanian, H., Fowler, J. W., Mason, S. J., & Rose, O. (2008a). A multi-criteria approach for scheduling semiconductor wafer fabrication facilities. Journal of Scheduling, 11(1), 29–47.

    Article  Google Scholar 

  • Pfund, M. E., Fowler, J. W., Gadkari, A., & Chen, Y. (2008b). Scheduling jobs on parallel machines with setup times and ready times. Computers & Industrial Engineering, 54(4), 764–782.

    Article  Google Scholar 

  • Pinedo, M. (2008). Scheduling: Theory, algorithms and systems (2nd ed.). Upper Saddle River, NJ: Prentice Hall.

    Google Scholar 

  • Pinedo, M., & Singer, M. (1999). A shifting bottleneck heuristic for minimizing the total weighted tardiness in a job shop. Naval Research Logistics (NRL), 46(1), 1–17.

    Article  Google Scholar 

  • Singer, M. (2001). Decomposition methods for large job shops. Computers & Operations Research, 28(3), 193–207.

    Article  Google Scholar 

  • Singer, M., & Pinedo, M. (1998). A computational study of branch and bound techniques for minimizing the total weighted tardiness in job shops. IIE Transactions, 30, 109–118.

    Google Scholar 

  • Scholz-Reiter, B., Hildebrandt, T., & Tan, Y. (2013a). Effective and efficient scheduling of dynamic job shops—Combining the shifting bottleneck procedure with variable neighbourhood search. CIRP Annals—Manufacturing Technology, 62(1), 423–426.

    Article  Google Scholar 

  • Scholz-Reiter, B., Tan, Y., & Hildebrandt, T. (2013b). A computational study of shifting bottleneck procedures for job shop total weighted tardiness scheduling problems. In Proceedings of the 6th Multidisciplinary International Conference on Scheduling: Theory and Applications (pp. 437–456).

  • Taillard, E. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 1993(64), 278–285.

    Article  Google Scholar 

  • Van Hentenryck, P., & Michel, L. (2004). Scheduling abstractions for local search. Lecture Notes in Computer Science, 3011, 319–334.

    Article  Google Scholar 

  • Vepsalainen, A. P. J., & Morton, T. E. (1987). Priority rules for job shops with weighted tardiness costs. Management Science, 33(8), 1035–1047.

    Article  Google Scholar 

  • Zhou, H., Cheung, W., & Leung, L. (2009). Minimizing weighted tardiness of job-shop scheduling using a hybrid genetic algorithm. European Journal of Operational Research, 194(1), 637–649.

    Article  Google Scholar 

Download references

Acknowledgments

This research was supported by the International Graduate School for Dynamics in Logistics (IGS) at the University of Bremen

Author information

Authors and Affiliations

  1. University of Bremen, Bremen, Germany

    Yi Tan, Torsten Hildebrandt & Bernd Scholz-Reiter

Authors
  1. Yi Tan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Torsten Hildebrandt
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Bernd Scholz-Reiter
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yi Tan.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Tan, Y., Hildebrandt, T. & Scholz-Reiter, B. Configuration and the advantages of the shifting bottleneck procedure for optimizing the job shop total weighted tardiness scheduling problem. J Sched 19, 429–452 (2016). https://doi.org/10.1007/s10951-015-0441-1

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10951-015-0441-1

Keywords

Search

Navigation