Dominance rules for single machine schedule with sequence dependent setup and due date. (English) Zbl 1284.90028
Summary: Some dominance rules are proposed for the problems of scheduling \(N\) jobs on a single machine with due dates, sequence dependent setup times and no preemption. Two algorithms based on Ragatz’s branch and bound scheme are developed including the dominance rules where the objective is to minimize the maximum tardiness or the total tardiness. Computational experiments demonstrate the effectiveness of the dominance rules.
MSC:
| 90B36 | Stochastic scheduling theory in operations research |
Keywords:
dominance rule; sequence dependent setup; due date; single machine schedule; branch and boundReferences:
| [1] | S. K. Gupta. N jobs M machines job-shop problems with sequence dependent setup times [J]. Int. J. of Production Research, 1982,20(3):643–656. · doi:10.1080/00207548208947793 |
| [2] | L.J. Krajewski, B.E. King, L.P. Ritzman, et al. Kaban, MRP and shaping the manufacturing environment [J]. Management Science, 1987,33(1):39–57. · doi:10.1287/mnsc.33.1.39 |
| [3] | K.R. Baker. Introduction to Sequencing and Scheduling [M]. New York: Wiley, 1974. |
| [4] | A. Allahverdi, J.N.D. Gupta, T. Aldowaisan. A review of scheduling research involving setup considerations [J]. Omega, 1999,27(3):219–239. · doi:10.1016/S0305-0483(98)00042-5 |
| [5] | G. L. Ragatz. A branch-and-bound method for minimum tardiness sequencing on a single processor with sequence dependent setup times [C] // Proc. of 24th Annual Meeting of the Decision Sciences Institute, New Orleans, Louisiana: Decision Sciences Press, 1993:1375–1377. |
| [6] | K. C. Tan, R. Narasinmhan, P. A. Rubin, et al. A comparison of four methods for minimizing total tardiness on a single processor with sequence dependent setup times [J]. Omega, 2000,28(4):313–326. · doi:10.1016/S0305-0483(99)00050-X |
| [7] | P. A. Rubin, G. L. Ragatz. Scheduling in a sequence dependent setup environment with generic search [J]. Computers & Operations Research, 1995,22(1):85–99. · Zbl 0813.90065 · doi:10.1016/0305-0548(93)E0021-K |
| [8] | K. C. Tan, R. Narasimhan. Minimizing tardiness on a single processor with sequence-dependent times: a simulated annealing approach [J]. Omega, 1997,25(6):619–634. · doi:10.1016/S0305-0483(97)00024-8 |
| [9] | Y. H. Lee, K. Bhaskaran, M. Pinedo. A heuristic to minimize the total weighted tardiness with sequence dependent setup [J]. IIE Transaction, 1997,21(9):45–52. · doi:10.1080/07408179708966311 |
| [10] | Y. Park, S. Kim, Y.H. Lee. Scheduling jobs on parallel machines applying neural network and heuristics rules [J]. Computers & Industrial Engineering, 2000,38(1): 189–202. · doi:10.1016/S0360-8352(00)00038-3 |
| [11] | C. Gagne, L. Wilson. Price and Marc Gravel. Scheduling a single machine with sequence dependent setup times using ant colony optimization [R]. Quebec: University of Quebec, 2003. |
| [12] | T. Ibaraki. Enumerative approaches to combinatorial optimization: Part I [J]. Annals of Operations Research, 1987,10(1):1–340. · doi:10.1007/BF02135650 |
| [13] | T. Ibaraki. Enumerative approaches to combinatorial optimization: Part II [J]. Annals of Operations Research, 1987,11(2):341–602. · doi:10.1007/BF02188547 |
| [14] | F. Glover, G. Gutin, A. Yeo, et al. Construction heuristics for asymmetric TSP [J]. European J. of Operation Research, 2001,129(3):555–568. · Zbl 1125.90402 · doi:10.1016/S0377-2217(99)00468-3 |
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.
