Single machine total completion time scheduling problem with workload-dependent maintenance duration

•We consider a scheduling problem with workload-dependent maintenance duration (MD).•The MD function is of the form f(x), where x is the machine workload.•An optimal algorithm is proposed for the case where f′(x)≥1f′(x)≥1.•A PTAS is proposed for the case where f′(x)<1f′(x)<1.

A single-machine scheduling problem with workload-dependent maintenance duration is considered. The objective is to minimize total completion time. For the case where the derivation of the maintenance duration function is greater than or equal to 1, a polynomial time optimal algorithm is proposed. For the case where the derivation of the maintenance duration function is less than 1, a polynomial time approximation scheme is proposed.