کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1142641 | 957159 | 2013 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Single machine scheduling with job-dependent convex cost and arbitrary precedence constraints
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
In this work we combine resource augmentation and alpha-point scheduling techniques, which have resulted in very good performance scheduling algorithms, to compute approximate solutions for a general family of scheduling problems: each job has a convex non-decreasing cost function and the goal is to compute a schedule that minimizes the total cost subject to precedence constraints.We show that our algorithm is a O(1)O(1)-speed 11-approximation algorithm and our numerical experiments show that the speed-scaling ratio required is close to 11.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Operations Research Letters - Volume 41, Issue 5, September 2013, Pages 436–441
Journal: Operations Research Letters - Volume 41, Issue 5, September 2013, Pages 436–441
نویسندگان
Rodrigo A. Carrasco, Garud Iyengar, Cliff Stein,