Scheduling jobs under simple linear deterioration

The paper considers simple linear deterioration of processing times, i.e. Pi=αit, where αi is a job dependent deterioration rate and t>0 is the job’s starting time. In this environment, most classical n-job, non-preemptive, single machine scheduling models are studied, i.e. most commonly used performance measures are considered: makespan, flow-time, total tardiness, number of tardy jobs, etc. It is shown that all these models remain polynomially solvable.