Single machine flow-time scheduling with scheduled maintenance

In this paper, we investigate a single machine scheduling problem of minimizing the sum of job flow times subject to scheduled maintenance. We first provide an NP-completeness proof for the problem. This proof is much shorter than the one given in Adiri et al. [1]. The shortest processing time (SPT) sequence is then shown to have a worst case error bound of 2/7. Furthermore, an example is provided to show that the bound is tight. This example also serves as a counter-example to the 1/4 error bound provided in Adiri et al. [1].