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

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+β_is_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/β²) 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.