Single-machine scheduling with time-dependent and position-dependent deteriorating jobs

In many real-life scheduling situations, the jobs deteriorate at a certain rate while waiting to be processed. This study introduces a new deterioration model where the actual processing time of a job depends not only on the starting time of the job but also on its scheduled position. The objective is to find the optimal schedule such that the makespan or total completion time is minimised. This study first shows that both problems are solvable in On log n time. This study further shows that in both cases there exists an optimal schedule that is the shortest processing time, longest processing time, or V-shaped with respect to the job normal processing times, depending on the relationships between problem parameters.