Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Enhancing local search algorithms for job shops with min-sum objectives by approximate move evaluation

  • Published:
Journal of Scheduling Aims and scope Submit manuscript

Abstract

Exact move evaluation in local search-based job shop scheduling is known to be time consuming, especially for medium and large size instances. Therefore, approximation functions providing quick estimates for the cost induced by a move are often used in order to accelerate the search process. This paper describes the generalization of an existing cost estimation function for insertion moves towards min-sum objectives, such as total weighted tardiness, total weighted completion time and total weighted number of late jobs. Besides the transfer of the concept itself, shortcomings of the original approach are identified and eliminated and an enhanced approximation scheme is presented. The final estimation function is able to provide a considerably increased accuracy for the considered min-sum objectives compared to the existing approach. The advantage of the new function emerges most clearly when it is embedded into a tabu search algorithm, as verified based on benchmark instances from literature involving up to 100 jobs and 20 machines.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

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

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  • Armentano, V. A., & Scrich, C. R. (2000). Tabu search for minimizing total tardiness in a job shop. International Journal of Production Economics, 63(2), 131–140.

    Article  Google Scholar 

  • Balas, E. (1979). Disjunctive programming. Annals of Discrete Mathematics, 5, 3–51.

    Article  Google Scholar 

  • Balas, E., & Vazacopoulos, A. (1998). Guided local search and the shifting bottleneck for job shop scheduling. Management Science, 44(2), 262–275.

    Article  Google Scholar 

  • Beasley, J. (1990). Or-library: Distributing test problems by electronic mail. Journal of the Operational Research Society, 41(11), 1069–1072.

    Google Scholar 

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

    Google Scholar 

  • Braune, R., Zäpfel, G., & Affenzeller, M. (2009). A computational study of lower bounding schemes for total weighted tardiness job shops. In: Proceedings of the 2nd International Symposium on Logistics and Industrial Informatics (LINDI 2009), IEEE Publications, pp 102–107.

  • Bülbül, K. (2010). A hybrid shifting bottleneck tabu search heuristic for the job shop total weighted tardiness problem. Technical report. Istanbul: Sabanci University.

  • 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 

  • De Bontridder, K. (2005). Minimizing total weighted tardiness in a generalized job shop. Journal of Scheduling, 8(6), 479–496.

    Article  Google Scholar 

  • Dell’Amico, M., & Trubian, M. (1993). Applying tabu search to the job-shop scheduling problem. Annals of Operations Research, 41, 231–252.

    Article  Google Scholar 

  • Essafi, I., Mati, Y., & Dauzère-Pérès, S. (2008). A genetic local search algorithm for minimizing total weighted tardiness in the job-shop scheduling problem. Computers & Operations Research, 35, 2599–2616.

    Article  Google Scholar 

  • French, S. (1982). Sequencing and scheduling: An introduction to the mathematics of the job shop. Chichester: Ellis Horwood.

    Google Scholar 

  • Józefowska, J., Jurisch, B., & Kubiak, W. (1994). Scheduling shops to minimize the weighted number of late jobs. Operations Research Letters, 16(5), 277–283.

    Article  Google Scholar 

  • Kovács, A., & Beck, J. C. (2011). A global constraint for total weighted completion time for unary resources. Constraints, 16, 100–123.

    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 

  • Lawrence, S. R. (1984). Resource-constrained project scheduling: An experimental investigation of heuristic scheduling techniques. Pittsburgh, PA: Graduate School of Industrial Administration, Carnegie-Mellon University.

    Google Scholar 

  • Lin, S. C., Goodman, E. D., Punch, W. F. (1997). A genetic algorithm approach to dynamic job shop scheduling problem. In T. Bäck (Ed.), Proceedings of the 7th International Conference on Genetic Algorithms (ICGA), Morgan Kaufmann, pp. 481–488.

  • Mati, Y., Dauzère-Pérès, S., & Lahlou, C. (2011). A general approach for optimizing regular criteria in the job-shop scheduling problem. European Journal of Operational Research, 212, 33–42.

    Article  Google Scholar 

  • Mattfeld, D. C., & Bierwirth, C. (2004). An efficient genetic algorithm for job shop scheduling with tardiness objectives. European Journal of Operational Research, 155(3), 616–630.

    Article  Google Scholar 

  • Morton, T. E., & Pentico, D. W. (1993). Heuristic scheduling systems with applications to production systems and project management. New York: Wiley.

    Google Scholar 

  • Nowicki, E., & Smutnicki, C. (2005). An advanced tabu search algorithm for the job shop problem. Journal of Scheduling, 8, 145–159.

    Article  Google Scholar 

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

    Article  Google Scholar 

  • Roy, B., & Sussmann, B. (1964). Les problèmes d’ordonnancement avec contraintes disjonctives. Note D.S. no. 9 bis. Paris: SEMA.

  • Singer, M. (1996). Optimization methods for the total weighted tardiness job shop. PhD thesis, Columbia University.

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

    Google Scholar 

  • Storer, R. H., Wu, S. D., & Vaccari, R. (1992). New search spaces for sequencing problems with application to job shop scheduling. Management Science, 38, 1495–1509.

    Article  Google Scholar 

  • Suh, C. J. (1988). Controlled search simulated annealing for job shop scheduling. PhD thesis, University of Texas, Austin.

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

    Article  Google Scholar 

  • Taillard, E. (1994). Parallel taboo search techniques for the job shop scheduling problem. ORSA Journal on Computing, 6, 108–117.

    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 

  • Wang, T. Y., & Wu, K. B. (1999). An efficient configuration generation mechanism to solve job shop scheduling problems by the simulated annealing algorithm. International Journal of Systems Science, 30(5), 527–532.

    Article  Google Scholar 

  • Wang, T. Y., & Wu, K. B. (2000). A revised simulated annealing algorithm for obtaining the minimum total tardiness in job shop scheduling problems. International Journal of Systems Science, 31(4), 537–542.

    Article  Google Scholar 

  • Zhang, C., Li, P., Guan, Z., & Rao, Y. (2007). A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem. Computers & Operations Research, 34, 3229–3242.

    Article  Google Scholar 

  • Zhang, C. Y., Li, P., Rao, Y., & Guan, Z. (2008). A very fast TS/SA algorithm for the job shop scheduling problem. Computers & Operations Research, 35, 282–294.

    Article  Google Scholar 

  • Zhang, R., & Wu, C. (2011). A simulated annealing algorithm based on block properties for the job shop scheduling problem with total weighted tardiness objective. Computers & Operations Research, 38, 854–867.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute of Production and Logistics Management, Johannes Kepler University, Altenbergerstrasse 69, 4040 , Linz, Austria

    Roland Braune & Günther Zäpfel

  2. Department of Software Engineering, Upper Austria University of Applied Sciences, 4232 , Hagenberg, Austria

    Michael Affenzeller

Authors
  1. Roland Braune
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Günther Zäpfel
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Michael Affenzeller
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Roland Braune.

Electronic supplementary material

Below is the link to the electronic supplementary material.

ESM 1 (PDF 47 kb)

Rights and permissions

Reprints and permissions

About this article

Cite this article

Braune, R., Zäpfel, G. & Affenzeller, M. Enhancing local search algorithms for job shops with min-sum objectives by approximate move evaluation. J Sched 16, 495–518 (2013). https://doi.org/10.1007/s10951-012-0305-x

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10951-012-0305-x

Keywords

Search

Navigation