Parallel machine scheduling problems with proportionally deteriorating jobs

Abstract

This article considers two scheduling problems on parallel identical machines with deteriorating jobs, in which the processing time of job is proportional function of its starting times to be processed. Namely, for job j, p _j = b _j t, where b _j > 0 is its deterioration rate, t ≥ t ₀ > 0 is its starting time and t ₀ is a given constant. The criteria of optimality are minimising the makespan and maximising the minimum machine completion time. It has been proved that the first problem is NP-hard; we prove that the second problem is also NP-hard. For both problems heuristic algorithms are constructed and their performance is analysed.

Keywords:

• scheduling
• identical parallel machines
• deteriorating jobs
• algorithm
• NP-hardness

Acknowledgements

The authors are grateful to the two anonymous referees for their constructive comments and suggestions on improving the presentation of this article. The research was supported in part by China Postdoctoral Science Foundation under grant number 20070410243 and the Ministry of Education of China under grant number NCET-05-0746.