کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10523991 | 957176 | 2005 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the complexity of scheduling unit-time jobs with OR-precedence constraints
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We present various complexity results for scheduling unit-time jobs subject to OR-precedence constraints. We prove that minimizing the total weighted completion time is strongly NP-hard, even on a single machine. In contrast, we give a polynomial-time algorithm for minimizing the makespan and the total completion time on identical parallel machines.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Operations Research Letters - Volume 33, Issue 6, November 2005, Pages 587-596
Journal: Operations Research Letters - Volume 33, Issue 6, November 2005, Pages 587-596
نویسندگان
Berit Johannes,