کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1142408 | 957147 | 2013 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Combinatorial algorithms for minimizing the weighted sum of completion times on a single machine
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We study the problem of minimizing the weighted sum of completion times of jobs with release dates on a single machine with the aim of shedding new light on “the simplest (linear program) relaxation” (Queyranne and Schulz, 1994 [17]). Specifically, we analyze a 3-competitive online algorithm (Megow and Schulz, 2004 [16]), using dual fitting. In the offline setting, we develop a primal–dual algorithm with approximation guarantee 1+2. The latter implies that the cost of the optimal schedule is within a factor of 1+2 of the cost of the optimal LP solution.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Operations Research Letters - Volume 41, Issue 2, March 2013, Pages 121–125
Journal: Operations Research Letters - Volume 41, Issue 2, March 2013, Pages 121–125
نویسندگان
James M. Davis, Rajiv Gandhi, Vijay H. Kothari,