Minimization of Job Waiting Time Variance on Identical Parallel Machines

We consider the problem of scheduling independent jobs on 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//WTV). We prove that, given the same job set, any feasible schedule of (Pm//WTV) can be transformed into the feasible solution for (Pm//WTV) 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.