Browsing by Author "Kacem, I."
Now showing 1 - 1 of 1
- Results Per Page
- Sort Options
ArticlePublication Metadata only Approximation algorithms for single machine scheduling with one unavailability period(Springer Nature, 2009-03) Kacem, I.; Haouari, Mohamed; Industrial Engineering; HAOUARI, MohamedIn 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.