کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
427646 | 686534 | 2010 | 6 صفحه PDF | دانلود رایگان |
In this paper, we formalize a natural but new coordination mechanism, named Parallel Processing Policy, and analyze the price of anarchy of the job scheduling game with this mechanism in different scheduling models. Specifically, we first show the existence of pure Nash equilibrium by constructing a potential function. Then we give upper bounds for the price of anarchy in various scheduling models, such as for identical machines, for related machines, for restricted machines and O(m) for unrelated machines. On the negative side, we also give a lower bound of for the unrelated machines model. We believe that this mechanism may be very powerful since it is a combination of two well studied mechanisms, ShortestFirst and Makespan. So it is a very interesting open problem to explore the exact bounds of PoA for this coordination mechanism in different scheduling models.
Journal: Information Processing Letters - Volume 110, Issues 8–9, 1 April 2010, Pages 288-293