Approximation algorithms for single machine scheduling with one unavailability period. (English) Zbl 1162.90458
Summary: We investigate the single machine scheduling problem with release dates and tails and a planned unavailability time period. We show that the problem admits a fully polynomial-time approximation scheme when the tails are equal. We derive an approximation algorithm for the general case and we show that the worst-case bound of the sequence yielded by Schrage’s algorithm is equal to 2 and that this bound is tight. Some consequences of this result are also presented.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
References:
| [1] | Carlier J (1982) The one-machine sequencing problem. Eur J Oper Res 11:42–47 (Erratum: Nowicki E, Zdrzalka S (1986) A note on minimizing maximum lateness in a one machine sequencing problem with release dates. Eur J Oper Res 23(2):266–267) |
| [2] | Dessouky MI, Margenthaler CR (1972) The one-machine sequencing problem with early starts and due dates. AIIE Trans 4(3): 214–222 |
| [3] | Gens GV, Levner EV (1981) Fast approximation algorithms for job sequencing with deadlines. Discr Appl Math 3: 313–318 · Zbl 0464.90035 · doi:10.1016/0166-218X(81)90008-1 |
| [4] | Hall LA, Shmoys DB (1992) Jackson’s rule for single machine scheduling: making a good heuristic better. Math Oper Res 17: 22–35 · Zbl 0781.90052 · doi:10.1287/moor.17.1.22 |
| [5] | Ibarra O, Kim CE (1975) Fast approximation algorithms for the knapsack and sum of subset problems. J ACM 22: 463–468 · Zbl 0345.90049 · doi:10.1145/321906.321909 |
| [6] | Kacem I (2007) Approximation algorithms for the makespan minimization with positive tails on a single machine with a fixed non-availability interval. J Comb Optim doi: 10.1007/s10878-007-9102-4 · Zbl 1170.90393 |
| [7] | Kellerer H, Strusevich VA (2007) Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications. Working paper (submitted) |
| [8] | Kovalyov MY, Kubiak W (1999) A fully polynomial approximation scheme for weighted earliness- tardiness problem. Oper Res 47: 757–761 · Zbl 0976.90042 · doi:10.1287/opre.47.5.757 |
| [9] | Lawler EL, Lenstra JK, Rinnooy Kan AHG, Shmoys DB (1993) Sequencing and scheduling: algorithms and complexity, in logistics of production and inventory. In: Graves SC, Rinnooy Kan AHG, Zipkin PH (eds) Handbooks of operation research management science, vol 4. North-Holland, Amsterdam, pp 445–522 |
| [10] | Lee CY (1996) Machine scheduling with an availability constraints. J Global Optim 9: 363–384 · Zbl 0870.90071 · doi:10.1007/BF00121681 |
| [11] | Lee CY (2004) Machine scheduling with an availability constraint. In: Leung JYT (eds) Handbook of scheduling: algorithms, models, and performance analysis, chap 22, Boca Raton |
| [12] | Martello S, Toth P (1990) Knapsack problems algorithms and computer implementations. Wiley, New York · Zbl 0708.68002 |
| [13] | Maugière Ph, Billaut JC, Bouquard JL (2005) New single machine and job-shop scheduling problems with availability constraints. J Schedul 8: 211–231 · Zbl 1123.90033 · doi:10.1007/s10951-005-6812-2 |
| [14] | Potts CN (1980) Analysis of a heuristic for one machine sequencing with release dates and delivery times. Oper Res 28: 1436–1441 · Zbl 0447.90041 · doi:10.1287/opre.28.6.1436 |
| [15] | Sahni S (1976) Algorithms for scheduling independent tasks. J ACM 23: 116–127 · Zbl 0326.68024 · doi:10.1145/321921.321934 |
| [16] | Schmidt G (2000) Scheduling with limited machine availability. Eur J Oper Res 121: 1–15 · Zbl 0959.90023 · doi:10.1016/S0377-2217(98)00367-1 |
| [17] | Souissi A, Kacem I, Chu C (2006) Minimiser le makespan avec prise en compte de contrainte d’indisponibilité sur une seule machine (in French). Valensciences 5: 191–206 |
| [18] | Woeginger GJ (2000) When does a dynamic programming formulation guarantee the existence of a fully polynomial time approximation scheme (FPTAS)?. INFORMS J Comput 12: 57–75 · Zbl 1034.90014 · doi:10.1287/ijoc.12.1.57.11901 |
| [19] | Woeginger GJ (2005) A comment on scheduling two machines with capacity constraints. Discr Optim 2: 269–272 · Zbl 1131.90024 · doi:10.1016/j.disopt.2005.06.005 |
| [20] | Yuan JJ, Shi L, Ou JW (2007) Single machine scheduling with forbidden intervals and job delivery times (submitted) |
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.
