Abstract
We study a scheduling problem with deteriorating jobs, that is, jobs whose processing times are an increasing function of their start times. We consider the case of a single machine and linear job-independent deterioration. The problem is to determine an optimal combination of the due-date and schedule so as to minimize the sum of due-date, earliness and tardiness penalties. We give an O(n log n) time algorithm to solve this problem.
Acknowledgements
This research was supported in part by The Hong Kong Polytechnic University under Grant Number G-YW81. L Kang was also supported by the National Natural Science Foundation of China under Grant Number 10101010.