کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
436149 | 689974 | 2015 | 18 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Performance guarantees for a scheduling problem with common stepwise job payoffs
ترجمه فارسی عنوان
تضمین عملکرد برای یک مشکل برنامه ریزی با پرداخت های شغلی مرحله ای است
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
تضمین تقریب مطلق، تضمین تقریب نسبی، برنامه ریزی، پرداخت های گام به گام، تاریخ های عرضه
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We consider a single machine scheduling problem with unequal release dates and a common stepwise payoff function for the jobs. The goal is to maximize the sum of the jobs payoffs, which are defined with regard to some common delivery dates. The problem is strongly NP-hard. In this paper, we propose a polynomial time approximation algorithm with both absolute and relative performance guarantees. The time complexity of the approximation algorithm is O(KNlogN)O(KNlogN), N being the number of jobs and K the number of delivery dates.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 562, 11 January 2015, Pages 377–394
Journal: Theoretical Computer Science - Volume 562, 11 January 2015, Pages 377–394
نویسندگان
Yasmina Seddik, Christophe Gonzales, Safia Kedad-Sidhoum,