Scheduling deteriorating jobs with chain constraints and a power function of job completion times

Abstract

We study a single-machine problem of scheduling n jobs (tasks) subject to parallel chain precedence constraints with deteriorating jobs, i.e. the processing time of a job is a simple linear function of its execution starting time. We show that the weighted sum of the θth power of job completion times minimization problem can be solved in polynomial time under the proposed model.

Keywords:

• scheduling
• deteriorating jobs
• single machine
• weighted sum of the θth power of job completion times
• parallel chains

Acknowledgments

The authors are grateful for two anonymous referees for their helpful comments on earlier version of the article. This research was supported by the Science Research Foundation of Shenyang Aerospace University (Grant No. 201304Y).