SCHEDULING TO MINIMIZE THE COEFFICIENT OF VARIATION

In this paper, we address the problem of uninterruptedly scheduling a set of independent jobs that are ready at time zero with the objective of minimizing the coefficient of variation (CV) of their completion t imes. We first show that, for high processing time values of the longe st job, a variance (V) minimizing schedule also minimizes CV. Using th is equivalence, we next demonstrate the invalidity of an earlier conje cture about the structure of a CV-optimal schedule and proceed to esta blish the NP-hardness of the CV problem. Finally, drawing from our pri or work on the V problem, we provide a pseudo-polynomial dynamic progr amming algorithm for the solution of the CV problem.