Single-machine scheduling with past-sequence-dependent delivery times and a linear deterioration

In many real-life scheduling environments, the jobs deteriorate at a certain rate while waiting to be processed. This paper addresses some single-machine scheduling problems with past-sequence-dependent (p-s-d) delivery times and a linear deterioration. The p-s-d delivery time of a job is propor-tional to the job's waiting time. It is assumed that the deterioration process is reected in the job processing times being an increasing function of their starting times. We consider the following objectives: the makespan, total com-pletion time, total weighted completion time, maximum lateness, and total ab-solute differences in completion times. We seek the optimal schedules for the problems to minimize the makespan and total completion time. Despite that the computational complexities of the problems to minimize the total weighted completion time and maximum lateness remain open, we present heuristics and analyze their worst-case performance ratios, and show that some special cases of the problems are polynomially solvable. We also show that the optimal schedule for the problem to minimize the total absolute differences in comple-tion times is V -shaped with respect to the normal job processing times.