Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/23859
Title: Multi-machine scheduling with variance minimization
Authors: Cai, X
Cheng, TCE 
Keywords: Completion time variance
Dynamic programming
NP-completeness
Scheduling
Issue Date: 1998
Source: Discrete applied mathematics, 1998, v. 84, no. 1-3, p. 55-70 How to cite?
Journal: Discrete Applied Mathematics 
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.
URI: http://hdl.handle.net/10397/23859
ISSN: 0166-218X
DOI: 10.1016/S0166-218X(98)00020-1
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

10
Last Week
0
Last month
0
Citations as of Jul 23, 2017

WEB OF SCIENCETM
Citations

6
Last Week
0
Last month
0
Citations as of Jul 15, 2017

Page view(s)

48
Last Week
1
Last month
Checked on Jul 9, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.