Single machine flow-time scheduling with scheduled maintenance (Q811593)

We investigate a single machine scheduling problem of minimizing the sum of job flow times subject to scheduled maintenance. We first provide NP- completeness proof for the problem. This proof is much shorter than the one given in the literature. 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.