Abstract
We address the classical uniformly related machine scheduling problem with minsum objective. The problem is solvable in polynomial time by the algorithm of Horowitz and Sahni. In that solution, each machine sequences its jobs shortest first. However when jobs may choose the machine on which they are processed, while keeping the same sequencing rule per machine, the resulting Nash equilibria are in general not optimal. The price of anarchy measures this optimality gap. By means of a new characterization of the optimal solution, we show that the price of anarchy in this setting is bounded from above by 2. We also give a lower bound of e/(e − 1) ≈ 1.58. This complements recent results on the price of anarchy for the more general unrelated machine scheduling problem, where the price of anarchy equals 4. Interestingly, as Nash equilibria coincide with shortest processing time first (SPT) schedules, the same bounds hold for SPT schedules. Thereby, our work also fills a gap in the literature.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Aumann, R.J.: Subjectivity and correlation in randomized strategies. J. Math. Econom. 1(1), 67–96 (1974)
Azar, Y., Jain, K., Mirrokni, V.: (Almost) optimal coordination mechanisms for unrelated machine scheduling. In: Proceedings 19th SODA, pp. 323–332. ACM/SIAM (2008)
Christodoulou, G., Koutsoupias, E., Nanavati, A.: Coordination mechanisms. Theoret. Comput. Sci. 410(36), 3327–3336 (2009)
Cole, R., Correa, J.R., Gkatzelis, V., Mirrokni, V., Olver, N.: Inner Product Spaces for MinSum Coordination Mechanisms. In: Proceedings 43rd STOC, pp. 539–548. ACM (2011)
Conway, R.W., Maxwell, W.L., Miller, L.W.: Theory of Scheduling. Addison-Wesley Publishing Co., Reading (1967)
Correa, J., Queyranne, M.: Efficiency of Equilibria in Restricted Uniform Machine Scheduling with MINSUM Social Cost (manuscript) (2010)
Czumaj, A., Vöcking, B.: Tight bounds for worst-case equilibria. ACM Trans. Algorithms 3(1), Art. 4, 17 (2007)
Graham, R., Lawler, E., Lenstra, J., Rinnooy Kan, A.: Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics 5(2), 287–326 (1979)
Heydenreich, B., Müller, R., Uetz, M.: Games and mechanism design in machine scheduling - An introduction. Production and Operations Management 16(4), 437–454 (2007)
Horowitz, E., Sahni, S.: Exact and approximate algorithms for scheduling nonidentical processors. Journal of the ACM 23(2), 317–327 (1976)
Ibarra, O., Kim, C.: Heuristic algorithms for scheduling independent tasks on nonidentical processors. Journal of the ACM 24(2), 280–289 (1977)
Immorlica, N., Li, L., Mirrokni, V.S., Schulz, A.S.: Coordination mechanisms for selfish scheduling. Theoret. Comput. Sci. 410(17), 1589–1598 (2009)
Koutsoupias, E., Papadimitriou, C.: Worst-Case Equilibria. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol. 1563, pp. 404–413. Springer, Heidelberg (1999)
Myerson, R.B.: Utilitarianism, egalitarianism, and the timing effect in social choice problems. Econometrica 49(4), 883–897 (1981)
Myerson, R.B.: Game theory - Analysis of conflict. Harvard University Press, Cambridge (1991)
Papadimitriou, C.: Algorithms, games, and the internet. In: Proceedings 33rd STOC, pp. 749–753. ACM (2001)
Roughgarden, T.: Intrinsic robustness of the price of anarchy. In: Proceedings 41st STOC, pp. 513–522. ACM (2009)
Yu, L., She, K., Gong, H., Yu, C.: Price of anarchy in parallel processing. Inform. Process. Lett. 110(8-9), 288–293 (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hoeksma, R., Uetz, M. (2012). The Price of Anarchy for Minsum Related Machine Scheduling. In: Solis-Oba, R., Persiano, G. (eds) Approximation and Online Algorithms. WAOA 2011. Lecture Notes in Computer Science, vol 7164. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-29116-6_22
Download citation
DOI: https://doi.org/10.1007/978-3-642-29116-6_22
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-29115-9
Online ISBN: 978-3-642-29116-6
eBook Packages: Computer ScienceComputer Science (R0)