Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/1145
Title: Parallel machine scheduling to minimize the sum of quadratic completion times
Authors: Cheng, TCE 
Liu, Z
Keywords: Parallel machine scheduling
Quadratic completion time
Probabilistic analysis
Issue Date: Jan-2004
Publisher: Taylor & Francis
Source: IIE transactions, Jan. 2004, v. 36, no. 1, p. 11-17 How to cite?
Journal: IIE transactions 
Abstract: We consider the parallel machine scheduling problem of minimizing the sum of quadratic job completion times. We first prove that the problem is strongly NP-hard. We then demonstrate by probabilistic analysis that the shortest processing time rule solves the problem asymptotically. The relative error of the rule converges in probability to zero under the assumption that the job processing times are independent random variables uniformly distributed in (0, 1). We finally provide some computational results, which show that the rule is effective in solving the problem in practice.
URI: http://hdl.handle.net/10397/1145
ISSN: 0740-817X
DOI: 10.1080/07408170490257844
Rights: Copyright © “IIE”.
This is an electronic version of an article published in T.C.E. Cheng and Z. Liu (2004), IIE Transactions, 36(1), 11–17. IIE Transactions is available online at: http://www.informaworld.com, the open URL of the article: http://www.informaworld.com/openurl?genre=article&issn=0740-817x&volume=36&&issue=1&spage=11.
Appears in Collections:Journal/Magazine Article

Files in This Item:
File Description SizeFormat 
QCT_final_version.pdfPre-published version131.89 kBAdobe PDFView/Open
Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

14
Last Week
0
Last month
0
Citations as of Jun 8, 2016

WEB OF SCIENCETM
Citations

13
Last Week
0
Last month
0
Citations as of Dec 6, 2016

Page view(s)

521
Last Week
10
Last month
Checked on Dec 4, 2016

Download(s)

460
Checked on Dec 4, 2016

Google ScholarTM

Check

Altmetric



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