  Time-dependent scheduling with linear deterioration involves determining when
to execute jobs whose processing times degrade as their beginning is delayed.
Each job i is associated with a release time r_i and a processing time function
p_i(s_i)=alpha_i + beta_i*s_i, where alpha_i, beta_i>0$ are constants 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. Here, we take a step forward by developing new bounds and approximation
results for the interesting special case of the problems with uniform
deterioration, i.e.\ beta_i=beta, for each i. The key contribution is a
O(1+1/beta)-approximation algorithm for the makespan problem and a
O(1+1/beta^2)-approximation algorithm for the total completion time problem.
Further, we propose greedy constant-factor approximation algorithms for
instances with beta=O(1/n) and beta=Omega(n), where n is the number of jobs.
Our analysis is based on a new approach for comparing computed and optimal
schedules via bounding pseudomatchings.
