کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
428554 686815 2013 4 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Coordination mechanism for selfish scheduling under a grade of service provision
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Coordination mechanism for selfish scheduling under a grade of service provision
چکیده انگلیسی

In this paper, we study the problem of selfish scheduling game under a grade of service provision, where all machines and all jobs are labeled with the different grade of service (GoS) levels such that a job J can be assigned to execute on machine M only when the GoS level of machine M is not higher than the GoS level of job J  . We consider two coordination mechanisms for this selfish scheduling game: the makespan policy and the LG-LPT policy. For the first mechanism, we show that the price of anarchy is exactly 32 for two machines and Θ(logmloglogm) for m  (⩾3)(⩾3) machines, respectively. For the second mechanism, we point out that the price of anarchy is 54 for two machines and 2−1m−1 for m  (⩾3)(⩾3) machines, respectively, and we finally analyze the convergence to a Nash equilibrium of the induced game.


► We study two coordination mechanisms for the selfish scheduling game under a GoS provision: makespan policy and LG-LPT policy.
► For first mechanism, the POA is 32 for two machines and Θ(logmloglogm) for m  (>3)(>3) machines, respectively.
► For second mechanism, the POA is 54 for two machines and 2−1m−1 for m  (>3)(>3) machines, respectively.
► We finally analyze the convergence of the second mechanism to a Nash equilibrium of the induced game.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 113, Issue 8, 30 April 2013, Pages 251–254
نویسندگان
, ,