×

Shifting bottleneck scheduling for total weighted tardiness minimization – a computational evaluation of subproblem and re-optimization heuristics. (English) Zbl 1349.90320

Summary: Machine-based decomposition of total weighted tardiness job shops is known to be considerably more complicated than in the makespan case, mainly due to the structure of the underlying graph model and thus the arising one-machine subproblems. In fact, the effectiveness of a shifting bottleneck approach crucially depends on the employed subproblem solver. Although a sophisticated exact algorithm exists, problem instances involving more than 30 jobs are still challenging. In this paper, new heuristic approaches to subproblems of this kind are devised which rely on advanced problem-specific concepts like local optimality and dominance principles. The proposed subproblem solvers are combined with an iterated local search method for re-optimizing already scheduled machines. Computational experiments show that the final enhanced shifting bottleneck algorithms are not only applicable to job shops involving up to 100 jobs and 20 machines, but also able to improve existing results for benchmark instances.

MSC:

90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming

Software:

OR-Library
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] French, S., Sequencing and schedulingan introduction to the mathematics of the job shop (1982), Chichester: Chichester Ellis Horwood
[2] Graham, R. L.; Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Optimization and approximation in deterministic sequencing and schedulinga survey, Ann Oper Res, 5, 187-326 (1979) · Zbl 0411.90044
[3] Lenstra, J. K.; Rinnooy Kan, A. H.G.; Brucker, P., Complexity of machine scheduling problems, Ann Discrete Math, 1, 343-362 (1977) · Zbl 0301.90025
[4] Singer, M.; Pinedo, M., A computational study of branch and bound techniques for minimizing the total weighted tardiness in job shops, IIE Trans, 30, 2, 109-118 (1997)
[5] Pinedo, M.; Singer, M., A shifting bottleneck heuristic for minimizing the total weighted tardiness in a job shop, Naval Res Logist, 46, 1-17 (1999) · Zbl 0922.90088
[6] Singer, M., Decomposition methods for large job shops, Comput Oper Res, 28, 193-207 (2001) · Zbl 0964.90020
[7] Mason, S. J.; Fowler, J. W.; Carlyle, W. M., A modified shifting bottleneck heuristic for minimizing total weighted tardiness in complex job shops, J Sched, 5, 247-262 (2002) · Zbl 1009.90045
[8] Mönch, L.; Drießel, R., A distributed shifting bottleneck heuristic for complex job shops, Comput Ind Eng, 49, 363-380 (2005)
[9] Mönch, L.; Schabacker, R.; Pabst, D.; Fowler, J. W., Genetic algorithm-based subproblem solution procedures for a modified shifting bottleneck heuristic for complex job shops, Eur J Oper Res, 177, 3, 2100-2118 (2007) · Zbl 1109.90044
[10] Mönch, L.; Zimmermann, J., A computational study of a shifting bottleneck heuristic for multi-product complex job shops, Prod Plan Control, 22, 1, 25-40 (2011)
[11] Scholz-Reiter, B.; Hildebrandt, T.; Tan, Y., Effective and efficient scheduling of dynamic job shops combining the shifting bottleneck procedure with variable neighbourhood search, CIRP Ann—Manuf Technol, 62, 423-426 (2013)
[13] Bülbül, K., A hybrid shifting bottleneck tabu search heuristic for the job shop total weighted tardiness problem, Comput Oper Res, 38, 6, 967-983 (2011) · Zbl 1205.90116
[14] Braune, R.; Zäpfel, G.; Affenzeller, M., An exact approach for single machine subproblems in shifting bottleneck procedures for job shops with total weighted tardiness objective, Eur J Oper Res, 218, 1, 76-85 (2012) · Zbl 1244.90089
[16] Kreipl, S., A large step random walk for minimizing total weighted tardiness in a job shop, J Sched, 3, 125-138 (2000) · Zbl 0969.90045
[18] de Bontridder, K., Minimizing total weighted tardiness in a generalized job shop, J Sched, 8, 6, 479-496 (2005) · Zbl 1123.90022
[19] Essafi, I.; Mati, Y.; Dauzère-Pérès, S., A genetic local search algorithm for minimizing total weighted tardiness in the job-shop scheduling problem, Comput Oper Res, 35, 2599-2616 (2008) · Zbl 1177.90155
[20] Mati, Y.; Dauzère-Pérès, S.; Lahlou, C., A general approach for optimizing regular criteria in the job-shop scheduling problem, Eur J Oper Res, 212, 33-42 (2011) · Zbl 1237.90093
[21] Zhou, H.; Cheung, W.; Leung, L. C., Minimizing weighted tardiness of job-shop scheduling using a hybrid genetic algorithm, Eur J Oper Res, 194, 637-649 (2009) · Zbl 1163.90004
[23] Zhang, R.; Wu, C., A simulated annealing algorithm based on block properties for the job shop scheduling problem with total weighted tardiness objective, Comput Oper Res, 38, 854-867 (2011) · Zbl 1202.90150
[24] 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, 5, 495-518 (2013) · Zbl 1297.90034
[25] Jouglet, A.; Savourey, D.; Carlier, J.; Baptiste, P., Dominance-based heuristics for one-machine total cost scheduling problems, Eur J Oper Res, 184, 3, 879-899 (2008) · Zbl 1141.90019
[26] Jouglet, A.; Carlier, J., Dominance rules in combinatorial optimization problems, Eur J Oper Res, 212, 3, 433-444 (2011) · Zbl 1237.90199
[28] Adams, J.; Balas, E.; Zawack, D., The shifting bottleneck procedure for job shop scheduling, Manag Sci, 34, 3, 391-401 (1988) · Zbl 0637.90051
[29] Akturk, M. S.; Ozdemir, D., A new dominance rule to minimize total weighted tardiness with unequal release dates, Eur J Oper Res, 135, 394-412 (2001) · Zbl 1051.90013
[30] Panwalkar, S. S.; Iskander, W., A survey of scheduling rules, Oper Res, 25, 1, 45-61 (1977) · Zbl 0369.90054
[31] Haupt, R., A survey of priority-rule based scheduling, OR Spekt, 11, 3-16 (1989) · Zbl 0658.90047
[32] Vepsalainen, A. P.J.; Morton, T. E., Priority rules for job shops with weighted tardiness costs, Manag Sci, 33, 8, 1035-1047 (1987)
[33] Morton, T. E.; Ramnath, P., Guided forward search in tardiness scheduling of large one machine problems, (Brown, D. E.; Scherer, W. T., Intelligent scheduling systems (1995), Kluwer Academic Publishers: Kluwer Academic Publishers Hingham, MA)
[35] Jouglet, A.; Baptiste, P.; Carlier, J., Branch-and-bound algorithms for total weighted tardiness, (Leung, J. T., Handbook of scheduling (2004), CRC Press: CRC Press Boca Raton, FL, USA), chap. 13
[36] Balas, E.; Vazacopoulos, A., Guided local search and the shifting bottleneck for job shop scheduling, Manag Sci, 44, 2, 262-275 (1998) · Zbl 0989.90057
[37] Beasley, J., Or-libraryDistributing test problems by electronic mail, J Oper Res Soc, 41, 11, 1069-1072 (1990)
[39] Taillard, E., Benchmarks for basic scheduling problems, Eur J Oper Res, 64, 278-285 (1993) · Zbl 0769.90052
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.