کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
478527 1446105 2011 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Parallel-batch scheduling of deteriorating jobs with release dates to minimize the makespan
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
Parallel-batch scheduling of deteriorating jobs with release dates to minimize the makespan
چکیده انگلیسی

We consider the problem of scheduling n deteriorating jobs with release dates on a single batching machine. Each job’s processing time is an increasing simple linear function of its starting time. The machine can process up to b jobs simultaneously as a batch. The objective is to minimize the maximum completion time, i.e., makespan. For the unbounded model, i.e., b = ∞, we obtain an O(n log n) dynamic programming algorithm. For the bounded model, i.e., b < n, we first show that the problem is binary NP-hard even if there are only two distinct release dates. Then we present O(nb) and O((nb/h)h) algorithms for the case where the job processing order is predetermined in advance and for the case where there are h, h ⩾ 2, distinct deteriorating rates, respectively. Furthermore, we provide a fully polynomial-time approximation scheme for the case where the number of distinct release dates is a constant.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 210, Issue 3, 1 May 2011, Pages 482–488
نویسندگان
, , , ,