On the minimization of completion time variance with a bicriteria extension

The authors discuss a single-machine scheduling problem where the objective is to minimize the variance of job completion times. To date, the problem has not been solved in polynomial time. The authors present a dynamic programming algorithm that is pseudopolynomial in complexity. They also propose a fully polynomial approximation scheme and derive a lower bound that is useful in its implementation. Furthermore, show that the dynamic programming solution is easy to extend to a bicriteria version of the problem in which it is desired to simultaneously minimize the mean completion time.