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
EISSN: 1545-8830
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
PIRA download icon_1.1View/Download Contents

SCOPUSTM   
Citations

18
Last Week
0
Last month
0
Citations as of Aug 13, 2018

WEB OF SCIENCETM
Citations

17
Last Week
0
Last month
0
Citations as of Aug 14, 2018

Page view(s)

680
Last Week
2
Last month
Citations as of Aug 14, 2018

Download(s)

494
Citations as of Aug 14, 2018

Google ScholarTM

Check

Altmetric


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