Jackson’s semi-preemptive scheduling on a single machine. (English) Zbl 1231.90193
Summary: We propose an effective improvement of the well-known Jackson’s preemptive schedule lower bound for the single machine scheduling problem with heads and tails. The semi-preemptive scheduling concept roughly consists in reducing the preemption impact by constraining some particular job parts to be processed in reduced time intervals. The impact of semi-preemptive scheduling is twofold: it yields a lower bound which dominates the preemptive one, and enables more effective adjustments of the heads and tails. Our experimental study revealed that suitably embedding our procedure within Carlier’s algorithm makes feasible to solve all of the hard instances which could not be solved by its original variant.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
Keywords:
semi-preemptive scheduling; single machine; release dates; delivery times; makespan; adjustment procedures; lower bound; branch-and-boundReferences:
| [1] | Garey, M. R.; Johnson, D. S., Computers and intractability: a guide to the theory of NP-completeness (1979), W.H. Freeman and Company: W.H. Freeman and Company San Francisco · Zbl 0411.68039 |
| [2] | Jackson JR. Scheduling a production line to minimize maximum tardiness. Management Science Research Project, University of California, Los Angeles; 1955.; Jackson JR. Scheduling a production line to minimize maximum tardiness. Management Science Research Project, University of California, Los Angeles; 1955. |
| [3] | Horn, W. A., Some simple scheduling algorithms, Naval Research Logistics Quarterly, 21 (1974) · Zbl 0276.90024 |
| [4] | Schrage L. Obtaining optimal solutions to resource constrained network scheduling problems. Unpublished manuscript; 1971.; Schrage L. Obtaining optimal solutions to resource constrained network scheduling problems. Unpublished manuscript; 1971. |
| [5] | Frederickson, G. N., Scheduling unit time tasks with integer release times and deadlines, Information Processing Letters, 16, 171-173 (1983) · Zbl 0508.68023 |
| [6] | Garey, M. R.; Johnson, D. S.; Simons, B. B.; Tarjan, R. E., Scheduling unit-time tasks with arbitrary release times and deadlines, SIAM Journal of Computing, 10, 256-269 (1981) · Zbl 0472.68021 |
| [7] | Hoogeveen, J. A., Minimizing maximum promptness and maximum lateness on a single machine, Mathematical Operations Research, 21, 100-114 (1995) · Zbl 0846.90050 |
| [8] | Vakhania, N., Single-machine scheduling with release times and tails, Annals of Operations Research, 129, 1-4, 253-271 (2004) · Zbl 1056.90074 |
| [9] | Pessan, C.; Bouquard, J. L.; Néron, E., An unrelated parallel machines model for an industrial production resetting problem, European Journal of Industrial Engineering, 2, 153-171 (2008) |
| [10] | Dessouky, M. I.; Larson, R. E., Symmetry and optimally properties of the single machine problem, AIIE Transactions, 10, 2, 170-175 (1978) |
| [11] | Larson, R. E.; Dessouky, M. I., Heuristic procedures for the single machine problem to minimize maximum lateness, AIIE Transactions, 10, 176-183 (1978) |
| [12] | Kise, H.; Ibaraki, T.; Mine, H., Performance analysis of six approximation algorithms for the one-machine maximum lateness scheduling problem with ready times, Journal of Operations Research Society of Japan, 22, 205-223 (1979) · Zbl 0427.90049 |
| [13] | Potts, C. N., Analysis of a heuristic for one machine sequencing with release dates and delivery times, Operations Research, 28, 1436-1441 (1980) · Zbl 0447.90041 |
| [14] | Nowicki, E.; Smutnicki, C., An approximation algorithm for single-machine scheduling with release times and delivery times, Discrete Applied Mathematics, 48, 69-79 (1994) · Zbl 0942.68507 |
| [15] | Hall, L.; Shmoys, D., Jackson’s rule for single-machine scheduling: making a good heuristic better, Mathematics of Operations Research, 17, 22-35 (1992) · Zbl 0781.90052 |
| [16] | Mastrolilli, M., Efficient approximation schemes for scheduling problems with release dates and delivery times, Journal of Scheduling, 6, 521-531 (2003) · Zbl 1154.90473 |
| [17] | Dessouky, M. I.; Margenthaler, C. R., The one-machine sequencing problem with early starts and due dates, AIIE Transactions, 4, 214-222 (1972) |
| [18] | Baker, K. R.; Su, Z., Sequencing with due-dates and early start times to minimize maximum tardiness, Naval Research Logistics Quarterly, 21, 171-176 (1974) · Zbl 0277.90044 |
| [19] | McMahon, G.; Florian, M., On scheduling with ready times and due dates to minimize maximum lateness, Operations Research, 23, 3, 475-482 (1975) · Zbl 0301.90024 |
| [20] | Lageweg, B. J.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Minimizing maximum lateness on one machine: computational experience and some applications, Statistica Neerlandica, 30, 25-41 (1976) · Zbl 0336.90029 |
| [21] | Carlier, J., The one-machine sequencing problem, European Journal of Operational Research, 11, 42-47 (1982) · Zbl 0482.90045 |
| [22] | Adams, J.; Balas, E.; Zawack, D., The shifting bottleneck procedure for job shop scheduling, Management Science, 34, 391-401 (1988) · Zbl 0637.90051 |
| [23] | Lancia, G., Scheduling jobs with release dates and tails on two unrelated parallel machines to minimize the makespan, European Journal of Operational Research, 2, 120, 277-288 (2000) · Zbl 0953.90029 |
| [24] | Néron, E.; Tercinet, F.; Sourd, F., Search tree based approaches for parallel machine scheduling, Computers and Operation Research, 35, 4, 1127-1137 (2008) · Zbl 1179.90148 |
| [25] | Sourirajan, K.; Uzsoy, R., Hybrid decomposition heuristics for solving large-scale scheduling problems in semiconductor wafer fabrication, Journal of Scheduling, 10, 41-65 (2007) · Zbl 1154.90491 |
| [26] | Larson, R. E.; Dessouky, M. I.; Devor, R. E., A forward-backward procedure for the single machine problem to minimize maximum lateness, IIE Transactions, 17, 252-260 (1985) |
| [27] | Grabowski, J.; Nowicki, E.; Zdrzalka, S., A block approach for single-machine scheduling with release dates and due dates, European Journal of Operational Research, 26, 2, 278-285 (1986) · Zbl 0603.90073 |
| [28] | Sadykov R, Lazarev A. Experimental comparison of branch-and-bound algorithms for the \(1 | r_j | L_{\max}\); Sadykov R, Lazarev A. Experimental comparison of branch-and-bound algorithms for the \(1 | r_j | L_{\max}\) |
| [29] | Pan, Y.; Shi, L., Branch-and-bound algorithms for solving hard instances of the one-machine sequencing problem, European Journal of Operational Research, 168, 3, 1030-1039 (2006) · Zbl 1077.90030 |
| [30] | Briand C, Ourari S, Bouzouia B, 2010, An efficient ILP formulation for the single machine scheduling problem. RAIRO — Operations Research, 44(1), pp. 61-71.; Briand C, Ourari S, Bouzouia B, 2010, An efficient ILP formulation for the single machine scheduling problem. RAIRO — Operations Research, 44(1), pp. 61-71. · Zbl 1183.90161 |
| [31] | Carlier, J.; Pinson, E., Adjustment of heads and tails for the job-shop problem, European Journal of Operational Research, 78, 146-161 (1994) · Zbl 0812.90063 |
| [32] | Brucker, P.; Jurisch, B.; Sievers, B., A branch and bound algorithm for the job-shop scheduling problem, Discrete Applied Mathematics, 49, 107-127 (1994) · Zbl 0802.90057 |
| [33] | Brucker, P.; Brinkkotter, W., Solving open benchmark problems for job shop problem, Journal of Scheduling, 4, 53-64 (2001) · Zbl 0979.90053 |
| [34] | Della Croce F, T’kindt V. Improving the preemptive bound for the single machine min-max lateness problem subject to release times. In: Proceedings of the eleventh international workshop on project management and scheduling, Istanbul, Turkey, 2008. p. 52-5.; Della Croce F, T’kindt V. Improving the preemptive bound for the single machine min-max lateness problem subject to release times. In: Proceedings of the eleventh international workshop on project management and scheduling, Istanbul, Turkey, 2008. p. 52-5. |
| [35] | Carlier, J.; Pinson, E., An algorithm for solving the job-shop problem, Management Science, 35, 164-176 (1989) · Zbl 0677.90036 |
| [36] | Carlier, J.; Pinson, E., A practical use of Jackson’s preemptive schedule for solving the job-shop problem, Annals of Operations Research, 26, 269-287 (1990) · Zbl 0709.90061 |
| [37] | Haouari, M.; Gharbi, A., An improved max-flow based lower bound for minimizing maximum lateness on identical parallel machines, Operations Research Letters, 31, 49-52 (2003) · Zbl 1013.90066 |
| [38] | Lahrichi, A., Ordonnancements: la notion de “parties obligatoires” et son application aux problèmes cumulatifs, RAIRO-RO, 16, 241-262 (1982) · Zbl 0491.90053 |
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.
