Approximation algorithms for single machine scheduling with one unavailability period
Type :
Article
Publication Status :
published
Access :
restrictedAccess
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.
Source :
4OR: A Quarterly Journal of Operations Research
Date :
2009-03
Volume :
7
Issue :
1
Publisher :
Springer Nature
Collections
Share this page