کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1142551 | 957155 | 2010 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Minimizing the sum of weighted completion times in a concurrent open shop
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Minimizing the sum of weighted completion times in a concurrent open shop Minimizing the sum of weighted completion times in a concurrent open shop](/preview/png/1142551.png)
چکیده انگلیسی
We study minimizing the sum of weighted completion times in a concurrent open shop. We give a primal–dual 2-approximation algorithm for this problem. We also show that several natural linear programming relaxations for this problem have an integrality gap of 2. Finally, we show that this problem is inapproximable within a factor strictly less than 6/5 if P≠NPP≠NP, or strictly less than 4/3 if the Unique Games Conjecture also holds.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Operations Research Letters - Volume 38, Issue 5, September 2010, Pages 390–395
Journal: Operations Research Letters - Volume 38, Issue 5, September 2010, Pages 390–395
نویسندگان
Monaldo Mastrolilli, Maurice Queyranne, Andreas S. Schulz, Ola Svensson, Nelson A. Uhan,