Due-date assignment and single machine scheduling with deteriorating jobs

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.

Keywords:

• single machine scheduling
• due-date
• deteriorating jobs

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.