Parallel machines scheduling with a deteriorating maintenance activity

AbstractIn 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: schedulingparallel identical machinesmaintenance activitypolynomial algorithm AcknowledgementsWe 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).