کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1142627 | 957158 | 2011 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A 3/2-approximation algorithm for kiki-partitioning
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: A 3/2-approximation algorithm for kiki-partitioning A 3/2-approximation algorithm for kiki-partitioning](/preview/png/1142627.png)
چکیده انگلیسی
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,