Parallel machine scheduling to minimize the sum of quadratic completion times

Research output: Journal article publicationJournal articleAcademic researchpeer-review

20 Citations (Scopus)

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

ASJC Scopus subject areas

  • Industrial and Manufacturing Engineering

Cite this