کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
481444 | 1446141 | 2009 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Single machine scheduling with release dates and rejection
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Single machine scheduling with release dates and rejection Single machine scheduling with release dates and rejection](/preview/png/481444.png)
چکیده انگلیسی
In this paper, we consider the single machine scheduling problem with release dates and rejection. A job is either rejected, in which case a rejection penalty has to be paid, or accepted and processed on the machine. The objective is to minimize the sum of the makespan of the accepted jobs and the total rejection penalty of the rejected jobs. We show that the problem is NP-hard in the ordinary sense. Then we provide two pseudo-polynomial-time algorithms. Consequently, two special cases can be solved in polynomial-time. Finally, a 2-approximation algorithm and a fully polynomial-time approximation scheme are given for the problem.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 198, Issue 3, 1 November 2009, Pages 975–978
Journal: European Journal of Operational Research - Volume 198, Issue 3, 1 November 2009, Pages 975–978
نویسندگان
Liqi Zhang, Lingfa Lu, Jinjiang Yuan,