کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1142627 | 957158 | 2011 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A 3/2-approximation algorithm for kiki-partitioning
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
We consider the multiprocessor scheduling problem with the objective of minimizing the makespan such that the number of items on each machine does not exceed a machine dependent cardinality limit. We present an elementary approximation algorithm with worst-case performance ratio 3/23/2 and running time linear in the number of items.
► We consider multiprocessor scheduling with the objective of minimizing the makespan.
► The number of items on a machine is bounded by a machine dependent cardinality limit.
► A heuristic with worst-case ratio 3/23/2 and linear running time is given.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Operations Research Letters - Volume 39, Issue 5, September 2011, Pages 359–362
Journal: Operations Research Letters - Volume 39, Issue 5, September 2011, Pages 359–362
نویسندگان
Hans Kellerer, Vladimir Kotov,