Parallel machine scheduling to minimize the sum of quadratic completion times

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.

Acknowledgements

This research was supported in part by The Hong Kong Polytechnic University under grant G-YW59. The second author was also supported by the National Natural Science Foundation of China under grant 10101007.