Parallel machines scheduling based on the impact of deteriorating maintenance

In this paper we study the problem of revising an initial schedule on parallel identical machines after a subset of jobs has finished processing. This is caused by deteriorating and rate-modifying maintenance. During the planning horizon there should be one maintenance activity scheduled on each machine to improve its processing rate. And delaying the starting time of maintenance should increase the time required to perform it. Considering both the total completion times of all jobs and the impact of maintenance in the form of increase in total machine load, we need to determine the job sequence on each machine and the location of maintenance simultaneously. We provide a polynomial time algorithm to the problem and extend the results to the case of unrelated machines.