A note on due-date assignment and single-machine scheduling with deteriorating jobs and learning effects

Abstract

The concepts of deteriorating jobs and learning effects have been individually studied in many scheduling problems. This note considers a single-machine scheduling problem with deteriorating jobs and learning effects. All of the jobs have a common (but unknown) due date. The objective is to minimize the sum of the weighted earliness, tardiness and due-date penalties. An O(n³) algorithm is proposed to optimally solve the problem with deteriorating jobs and job-dependent learning effect. Besides, an O(n log n) algorithm is provided to solve the problem with deteriorating jobs and job-independent learning effect.

Keywords:

• scheduling
• single-machine
• deteriorating jobs
• learning effects

Acknowledgements

We are grateful to the editor and the referees for their helpful comments and suggestions on an early version of this paper. This research is supported in part by the National Science Council of Taiwan, Republic of China, under grant number NSC-97-2221-E-150-056-MY2.