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.