کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4959374 | 1445947 | 2017 | 25 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Coordination mechanisms for scheduling games with proportional deterioration
ترجمه فارسی عنوان
مکانیسم هماهنگی برای برنامه ریزی بازی با خرابی متناسب
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
برنامه ریزی، ماشین های موازی، تعادل نش، قیمت هرج و مرج، مشاغل ضعیف،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
چکیده انگلیسی
We study parallel-machine scheduling games with deteriorating jobs. The processing time of a job increases proportionally with its starting time by a positive deterioration rate. Each job acts selfishly aiming to minimize its completion time while choosing a machine on which it will be processed. Machines are equipped with coordination mechanisms to diminish chaos caused by jobs' competition. We consider three coordination mechanisms in this paper, namely Smallest Deterioration Rate first, Largest Deterioration Rate first and MAKESPAN policy. Under these mechanisms, we precisely quantify the inefficiency of their Nash Equilibriums by investigating the Price of Anarchy (PoA) and the Price of Stability (PoS), concerning minimization of social costs including the makespan and the total machine load. By using some new methods, we obtain parametrical bounds on the PoA and PoS, and demonstrate that most of these bounds are tight.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 263, Issue 2, 1 December 2017, Pages 380-389
Journal: European Journal of Operational Research - Volume 263, Issue 2, 1 December 2017, Pages 380-389
نویسندگان
Qianqian Chen, Ling Lin, Zhiyi Tan, Yujie Yan,