Single-machine scheduling with common due-window assignment for deteriorating jobs

Abstract

In this paper, we consider a single-machine common due-window assignment scheduling problem with deteriorating jobs. Jobs’ processing times are defined by function of their starting times and job-dependent deterioration rates that are related to jobs and are not all equal. The objective is to determine an optimal combination of sequence and common due-window location so as to minimize the weighted sum of earliness, tardiness and due-window location penalties. We propose an O(n² log n) time algorithm to solve the problem and discuss several instances to illustrate it.

Keywords:

• scheduling
• due-window
• deteriorating
• algorithm

Acknowledgements

We are grateful to three anonymous referees for their helpful comments on an earlier version of the paper. This research was supported by the Science Research Project of the Educational Department of Zhejiang Province, China (No.Y201122447) and ZJNSF, China (No.LY12A01019, No.Y1111192).