An Approximation Scheme for Minimizing Agreeably Weighted Variance on a Single Machine

We consider the problem of minimizing the weighted variance of job completion times on a single machine with job-dependent, agreeable weights. In 1995, Cai derived a fully polynomial time approximation scheme for the special case where the weights of the jobs are polynomially bounded in the number n of jobs. In this article, we completely settle the approximability status of this scheduling problem. We construct a fully polynomial time approximation scheme for the general case, without putting any restrictions on the weights of the jobs.