کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8052596 | 1519406 | 2015 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Two-agent scheduling with rejection on a single machine
ترجمه فارسی عنوان
برنامه ریزی دو عامل با رد کردن بر روی یک دستگاه واحد
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
برنامه ریزی عامل ماشین تک طرد شدن، الگوریتم زمان تقریبی چندجمله ای، الگوریتم تقریبی،
موضوعات مرتبط
مهندسی و علوم پایه
سایر رشته های مهندسی
مکانیک محاسباتی
چکیده انگلیسی
In this paper, we consider the two-agent scheduling problem with rejection on a single machine. In the problem we have two agents A and B with job families JA and JB, respectively. A job in JA or JB is either accepted and processed on the machine, or rejected with a certain rejection penalty having to be paid. The objective is to minimize the sum of the given objective function fA of the accepted jobs and total rejection penalty of the rejected jobs of the first agent A, given that the second agent B only accepts schedules such that the sum of the given objective function fB of the accepted jobs and total rejection penalty of the rejected jobs of the agent B does not exceed a fixed value Q (Q is a positive integer), where fA and fB are non-decreasing functions on the completion times of their respective jobs. We show that, for all pairs (fA,fB)âCmaxA,CmaxB,LmaxA,LmaxB,âCjA,CmaxB,âCjA,LmaxB,âCjA,âwjBUjB, the problems are NP-hard. When (fA,fB)=CmaxA,LmaxB, we provide a pseudo-polynomial-time algorithm. Moreover, when (fA,fB)=CmaxA,LmaxB and all B-jobs are accepted, we give a 2-approximation algorithm and an fully polynomial-time approximation scheme. Finally, for (fA,fB)ââCjA,LmaxB,âCjA,âwjBUjBK, we present pseudo-polynomial-time algorithms, respectively.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Applied Mathematical Modelling - Volume 39, Issues 3â4, February 2015, Pages 1183-1193
Journal: Applied Mathematical Modelling - Volume 39, Issues 3â4, February 2015, Pages 1183-1193
نویسندگان
Qi Feng, Baoqiang Fan, Shisheng Li, Weiping Shang,