Single-machine scheduling with periodic maintenance to minimize makespan revisited

In this paper, a single‐machine scheduling problem with periodic maintenance and non‐preemptive jobs is considered. The objective is to minimize the makespan. It shows that the classical list scheduling (LS) algorithm, the longest processing time first (LPT) algorithm, and the modified longest processing time first (MLPT) algorithm all have the same worst‐case ratio and the same computational complexity for the considered problem. To compare the performances of three considered algorithms in detail, the worst‐case ratios of algorithms are formed as single‐variable functions of the total number of maintenance activities needed in the optimal schedule. Analysis results show that the bound associated with the LS algorithm is always dominated by the bound associated with the LPT algorithm, and the latter is always dominated by the bound associated with the MLPT algorithm.