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.
|Number of pages||7|
|Journal||IIE Transactions (Institute of Industrial Engineers)|
|Publication status||Published - 1 Jan 2004|
ASJC Scopus subject areas
- Industrial and Manufacturing Engineering