Single machine scheduling with time-dependent linear deterioration and rate-modifying maintenance

We study single machine scheduling problems with linear time‐dependent deterioration effects and maintenance activities. Maintenance periods (MPs) are included into the schedule, so that the machine, that gets worse during the processing, can be restored to a better state. We deal with a job‐independent version of the deterioration effects, that is, all jobs share a common deterioration rate. However, we introduce a novel extension to such models and allow the deterioration rates to change after every MP. We study several versions of this generalized problem and design a range of polynomial‐time solution algorithms that enable the decision‐maker to determine possible sequences of jobs and MPs in the schedule, so that the makespan objective can be minimized. We show that all problems reduce to a linear assignment problem with a product matrix and can be solved by methods very similar to those used for solving problems with positional effects.