摘要

We consider the problem of minimizing the sum of quadratic completion times on two parallel machines and we discuss the approximation ratio of the generalized shortest processing time (GSPT) priority rule according to which the jobs are sorted in non-decreasing processing time order and the next job on the list is assigned to the earliest available machine. We show that the approximation ratio of the GSPT rule is bounded above by root 5+2/root 5+1 approximate to 1.309 and below by root 6+2/root 6+1 approximate to 1.290. Extensions to the parallel m-machine problem are also discussed.

  • 出版日期2012-10-15