Parallel machines scheduling with a deteriorating maintenance activity

Abstract

In this paper, we consider parallel identical machines scheduling problems with a deteriorating maintenance activity. In this model, each machine has a deteriorating maintenance activity, that is, delaying the maintenance increases the time required to perform it. We need to make a decision on when to schedule the deteriorating maintenance activities and the sequence of jobs to minimize total completion time. We provide a polynomial time algorithm to solve the total completion time minimization problem.

Keywords:

• scheduling
• parallel identical machines
• maintenance activity
• polynomial algorithm

Acknowledgements

We are grateful to two anonymous referees for their helpful comments on an earlier version of this paper. This research was partially supported by a research grant from the Program of National Natural Science Foundation of China (No. 70902033 and 11001181) and a research grant from the Doctoral Program Foundation of Liaoning Province of China (No. 20081093).