TY - JOUR

T1 - New bounds for single-machine time-dependent scheduling with uniform deterioration

AU - Gkikas, Aggelos

AU - Letsios, Dimitrios

AU - Radzik, Tomasz

AU - Steinhofel, Kathleen

N1 - Publisher Copyright:
© 2024 The Authors

PY - 2024/7/27

Y1 - 2024/7/27

N2 - 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 ri and a processing time pi(si)=αi+βisi, where αi,βi>0 are parameters and si 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.

AB - 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 ri and a processing time pi(si)=αi+βisi, where αi,βi>0 are parameters and si 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.

UR - http://www.scopus.com/inward/record.url?scp=85194833318&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2024.114673

DO - 10.1016/j.tcs.2024.114673

M3 - Article

SN - 0304-3975

VL - 1006

JO - Theoretical Computer Science

JF - Theoretical Computer Science

M1 - 114673

ER -