Multi-machine scheduling with variance minimization

Xiaoqiang Cai, Edwin Tai Chiu Cheng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

12 Citations (Scopus)

Abstract

This paper addresses the problem of scheduling n jobs on m identical parallel machines so as to minimize the completion time variance. Properties of optimal solutions are derived first. Then, complexity results are obtained, which show that the problem is NP-complete in the strong sense when m is arbitrary, and NP-complete in the ordinary sense when m is fixed. Two algorithms are proposed. The first algorithm can generate an optimal solution in time O(n2mPm(P - Pm)m-1/[mm(m - 1)!]2), where P is the sum of all the processing times and Pm is the sum of the first m largest processing times. The second algorithm can find a near-optimal solution in time O(nPm(P - Pm)m-1/mm(m - 1)!). It is further shown that the relative error of the near-optimal solution is guaranteed to approach zero at a rate O(n-2) as n increases.
Original languageEnglish
Pages (from-to)55-70
Number of pages16
JournalDiscrete Applied Mathematics
Volume84
Issue number1-3
DOIs
Publication statusPublished - 15 May 1998

Keywords

  • Completion time variance
  • Dynamic programming
  • NP-completeness
  • Scheduling

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Cite this