Parallel machine scheduling to minimize the sum of quadratic completion times

Research output: Journal article publicationJournal articleAcademic researchpeer-review

22 Citations (Scopus)


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.
Original languageEnglish
Pages (from-to)11-17
Number of pages7
JournalIIE Transactions (Institute of Industrial Engineers)
Issue number1
Publication statusPublished - 1 Jan 2004

ASJC Scopus subject areas

  • Industrial and Manufacturing Engineering


Dive into the research topics of 'Parallel machine scheduling to minimize the sum of quadratic completion times'. Together they form a unique fingerprint.

Cite this