Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
Approximation algorithms for single machine scheduling with one unavailability period
| |
|
Research paper
Approximation algorithms for single machine scheduling with one unavailability period
Imed Kacem1  and Mohamed Haouari2
| (1) |
Charles Delaunay Institute, University of Technology of Troyes, 12 rue Marie Curie, B.P. 2060, 10010 Troyes, France |
| (2) |
Faculty of Economics and Administrative Sciences, Ozyegin University, Istanbul, Turkey |
Received: 29 May 2007 Revised: 3 April 2008 Published online: 8 May 2008
Abstract In this paper, 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.
Keywords Scheduling - Single machine - Approximation - Unavailability constraint
MSC classification (2000) 90B35
References
| 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)
|
| |
| Dessouky MI, Margenthaler CR (1972) The one-machine sequencing problem with early starts and due dates. AIIE Trans 4(3): 214–222
|
| |
Gens GV, Levner EV (1981) Fast approximation algorithms for job sequencing with deadlines. Discr Appl Math 3: 313–318
|
| |
Hall LA, Shmoys DB (1992) Jackson’s rule for single machine scheduling: making a good heuristic better. Math Oper Res 17:
22–35
|
| |
Ibarra O, Kim CE (1975) Fast approximation algorithms for the knapsack and sum of subset problems. J ACM 22: 463–468
|
| |
| 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
|
| |
| Kellerer H, Strusevich VA (2007) Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its
scheduling applications. Working paper (submitted)
|
| |
Kovalyov MY, Kubiak W (1999) A fully polynomial approximation scheme for weighted earliness- tardiness problem. Oper Res 47:
757–761
|
| |
| 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
|
| |
Lee CY (1996) Machine scheduling with an availability constraints. J Global Optim 9: 363–384
|
| |
| 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
|
| |
| Martello S, Toth P (1990) Knapsack problems algorithms and computer implementations. Wiley, New York
|
| |
Maugière Ph, Billaut JC, Bouquard JL (2005) New single machine and job-shop scheduling problems with availability constraints.
J Schedul 8: 211–231
|
| |
Potts CN (1980) Analysis of a heuristic for one machine sequencing with release dates and delivery times. Oper Res 28: 1436–1441
|
| |
Sahni S (1976) Algorithms for scheduling independent tasks. J ACM 23: 116–127
|
| |
Schmidt G (2000) Scheduling with limited machine availability. Eur J Oper Res 121: 1–15
|
| |
| 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
|
| |
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
|
| |
Woeginger GJ (2005) A comment on scheduling two machines with capacity constraints. Discr Optim 2: 269–272
|
| |
| Yuan JJ, Shi L, Ou JW (2007) Single machine scheduling with forbidden intervals and job delivery times (submitted)
|
| |
|
|
|
|
|
|