کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
429003 | 686994 | 2012 | 5 صفحه PDF | دانلود رایگان |
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 5+25+1≈1.309 and below by 6+26+1≈1.290. Extensions to the parallel m-machine problem are also discussed.
► Generalized shortest processing time (GSPT) is an index priority rule for machine scheduling.
► We discuss the approximation ratio of GSPT when minimizing the sum of quadratic completion times on parallel machines.
► For two machines the approximation ratio of GSPT is bounded above by 1.309 and below by 1.290.
► For m machines the optimality gap of GSPT is more than 3% for large problems with as many as 1000 machines.
Journal: Information Processing Letters - Volume 112, Issue 19, 15 October 2012, Pages 738–742