کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
429003 686994 2012 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A note on minimizing the sum of quadratic completion times on two identical parallel machines
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
A note on minimizing the sum of quadratic completion times on two identical parallel machines
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 112, Issue 19, 15 October 2012, Pages 738–742
نویسندگان
, ,