Back to Search
Start Over
New bounds for single-machine time-dependent scheduling with uniform deterioration.
- Source :
-
Theoretical Computer Science . Jul2024, Vol. 1006, pN.PAG-N.PAG. 1p. - Publication Year :
- 2024
-
Abstract
- We consider the single-machine time-dependent scheduling problem with linearly deteriorating jobs arriving over time. Each job i is associated with a release time r i and a processing time p i (s i) = α i + β i s i , where α i , β i > 0 are parameters and s i is the job's start time. In this setting, the approximability of both single-machine minimum makespan and total completion time problems remains open. We develop new bounds and approximation results for the special case of the problems with uniform deterioration, i.e. β i = β , for each i. The main contribution is a O (1 + 1 / β) -approximation algorithm for the makespan problem and a O (1 + 1 / β 2) approximation algorithm for the total completion time problem. Further, we propose greedy constant-factor approximation algorithms for instances with β = O (1 / n) and β = Ω (n) , where n is the number of jobs. Our analysis is based on an approach for comparing computed and optimal schedules via bounding pseudomatchings. [ABSTRACT FROM AUTHOR]
- Subjects :
- *APPROXIMATION algorithms
*SCHEDULING
*PRODUCTION scheduling
Subjects
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 1006
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 177843789
- Full Text :
- https://doi.org/10.1016/j.tcs.2024.114673