Single-machine scheduling with a variable maintenance activity

•We consider a new scheduling model with a maintenance activity on a single machine.•The maintenance activity must start before a given deadline.•The maintenance duration increases with its starting time.•Polynomial time optimal algorithms are proposed for several classic objectives.

We consider the problem of scheduling a maintenance activity and jobs on a single machine, where the maintenance activity must start before a given deadline and the maintenance duration increases with its starting time. We provide polynomial-time algorithms to solve the problems to minimize the makespan, sum of completion times, maximum lateness, and number of tardy jobs.