Minimization of job waiting time variance on identical parallel machines

Xiaoyun Xu, Nong Ye

Research output: Contribution to journalArticlepeer-review

17 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)917-927
Number of pages11
JournalIEEE Transactions on Systems, Man and Cybernetics Part C: Applications and Reviews
Issue number5
StatePublished - Sep 2007


  • Identical parallel machine
  • Job scheduling
  • Waiting time variance (WTV)

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Software
  • Information Systems
  • Human-Computer Interaction
  • Computer Science Applications
  • Electrical and Electronic Engineering


Dive into the research topics of 'Minimization of job waiting time variance on identical parallel machines'. Together they form a unique fingerprint.

Cite this