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

Abstract

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 O(n 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.

Keywords:

• scheduling
• deteriorating jobs
• makespan
• total completion time

Acknowledgements

The authors are grateful to the Editor, and one anonymous referee for his/her constructive comments on the earlier version of our paper.

Additional information

Funding

This research was supported by the National Natural Science Foundation of China [grant number 71301022]; the Natural Science Foundation of Jiangxi, China [grant number 20132BAB201010]; the Science Foundation of Education Committee of Jiangxi, China [grant number GJJ13458]; and the NSC of Taiwan [grant number NSC 102-2221-E-035-070-MY3], [grant number NSC 102-2410-H-035-034].