Scheduling a deteriorating maintenance activity on a single machine

Abstract

We study a problem of scheduling a maintenance activity on a single machine. Following several recent papers, the maintenance is assumed to be deteriorating, that is, delaying the maintenance increases the time required to perform it. The following objective functions are considered: makespan, flowtime, maximum lateness, total earliness, tardiness and due-date cost, and number of tardy jobs. We introduce polynomial time solutions for all these problems.

Keywords:

• scheduling
• single-machine
• maintenance activity
• polynomial-time solution

Acknowledgements

This work was supported in part by the Recanati Fund of the School of Business, The Hebrew University, Jerusalem, and in part by the Natural Sciences and Engineering Research Council of Canada (NSERC) grant number OGP0002507.