Single machine scheduling with decreasing linear deterioration under precedence constraints

This paper deals with single-machine scheduling problems with decreasing linear deterioration, i.e., jobs whose processing times are a decreasing function of their starting times. In addition, the jobs are related by parallel chains and a series–parallel graph precedence constraints, respectively. It is shown that for the problems of minimization of the makespan, polynomial algorithms exist.