×

A shifting bottleneck heuristic for minimizing the total weighted tardiness in a job shop. (English) Zbl 0922.90088

Summary: We present a shifting bottleneck heuristic for minimizing the total weighted tardiness in a job shop. The method decomposes the job shop into a number of single-machine subproblems that are solved one after another. Each machine is scheduled according to the solution of its corresponding subproblem. The order in which the single machine subproblems are solved has a significant impact on the quality of the overall solution and on the time required to obtain this solution. We therefore test a number of different orders for solving the subproblems. Computational results on 66 instances with ten jobs and ten machines show that our heuristic yields solutions that are close to optimal, and it clearly outperforms a well-known dispatching rule enhanced with backtracking mechanisms.

MSC:

90B35 Deterministic scheduling theory in operations research
PDFBibTeX XMLCite

References:

[1] Adams, The shifting bottleneck procedure for job shop scheduling, Manage Sci 34 (3) pp 391– (1988) · Zbl 0637.90051
[2] Applegate, A computational study of the job shop scheduling problem, ORSA J Comput 3 (2) pp 149– (1991) · Zbl 0755.90039 · doi:10.1287/ijoc.3.2.149
[3] Baker, Introduction to sequencing and scheduling (1974)
[4] Balas, Machine sequencing via disjunctive graphs: An implicit enumeration algorithm, Operations Res 17 pp 941– (1969) · Zbl 0183.49404
[5] Balas, The one-machine problem with delayed precedence constraints and its use in the job shop scheduling, Manage Sci 41 (1) pp 94– (1995) · Zbl 0824.90076
[6] Bellman, On a routing problem, Quart Appl Math 16 pp 87– (1958) · Zbl 0081.14403
[7] Carlier, The one-machine sequencing problem, Eur J Operations Res 11 pp 42– (1982) · Zbl 0482.90045
[8] Carlier, An algorithm for solving the job-shop problem, Manage Sci 35 (2) pp 164– (1989) · Zbl 0677.90036
[9] Dauzere-Peres, A modified shifting bottleneck procedure for job-shop scheduling, Int J Prod Res 31 (4) pp 923– (1993) · Zbl 0773.90036
[10] Eilon, Due dates in job shop scheduling, Int J Prod Res 14 pp 223– (1976)
[11] Giffler, Algorithms for solving production scheduling problems, Operations Res 8 pp 487– (1960) · Zbl 0248.90022
[12] Lageweg, Job shop scheduling by implicit enumeration, Manage Sci 24 (4) pp 441– (1977) · Zbl 0373.90034
[13] Lawrence, Resource constrained project scheduling: An experimental investigation of heuristic scheduling techniques (1984)
[14] Lenstra, Complexity of machine scheduling problems, Ann Discrete Math 1 pp 343– (1977) · Zbl 0353.68067
[15] Industrial scheduling (1963)
[16] I. Ovacik R. Uzsoy Decomposition methods for scheduling complex job shops: An application to semiconductor testing facilities 1994
[17] Ovacik, Rolling horizon procedures for single-machine dynamic scheduling problem with sequence-dependent setup times, Int J Prod Res 32 pp 1243– (1994) · Zbl 0901.90132
[18] Ovacik, Decomposition methods for complex factory scheduling problems (1997) · doi:10.1007/978-1-4615-6329-7
[19] Ow, Filtered beam search in scheduling, Int J Prod Res 26 pp 35– (1988)
[20] M. Singer Optimization methods for the total weighted tardiness job shop 1996
[21] Singer, A computational study of branch and bound techniques for minimizing the total weighted tardiness in flow shops and job shops, IIE Sched Logistics 29 pp 109– (1998)
[22] Vepsalainen, Priority rules for job shops with weighted tardiness cost, Manage Sci 33 (8) pp 1035– (1987)
[23] S. Wu E. Byeon R. Storer A graph-theoretic decomposition of job shop scheduling problems to achieve scheduling robustness 1993
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.