SCHEDULING JOBS UNDER SIMPLE LINEAR DETERIORATION

We consider simple linear deterioration of processing times, i.e. P(i) - alpha(i)t, where alpha(i) is a job dependent deterioration rate and t >0 is the job's starting time. In this environment, we study most classical n -job, non-preemptive, single machine scheduling models, i.e. most commonly used performance measures are considered: makespan, flow-time, total tardiness, number of tardy jobs, etc We show that all these models remain polynomially solvable.