Minimization of job waiting time variance on identical parallel machines

We consider the problem of scheduling n independent jobs on m identical parallel machines so as to minimize the waiting time variance of the jobs (Pm WTV). We show that the optimal value of Pm WTV is identical to the optimal value of the problem for minimizing the completion time variance of jobs on identical parallel machines (Pm CTV). We prove that, given the same job set, any feasible schedule of Pm WTV can be transformed into the feasible solution for Pm CTV with the same job set by applying the polynomial algorithms proposed in this paper. Several other important properties of Pm WTV are also proved. Heuristic algorithms are proposed to solve Pm WTV problems. We present the testing results of these heuristic algorithms, which are applied to problems with both small and large job sets.