Minimizing makespan in semiresumable case of single-machine scheduling with an availability constraint

Single machine scheduling with an unavailability interval to minimize makespan is considered in this paper under the assumption that the disrupted job has to partially restart after the machine becomes available again. It is easily shown that this problem is NP-hard, and it is shown that the Longest Processing Time (LPT) algorithm has a relative worst-case error bound of α/2, where α is re-processing rate. Furthermore, an example is provided to show that this bound is tight. Then a LPT-based heuristic is proposed. Computational results show that this heuristic is quite effective in finding an optimal or near-optimal schedule. Effects of different parameters on this heuristic are also analyzed in this paper.