Abstract
We study multiprocessor scheduling games with setup times on identical machines. Given a set of scheduling policies (coordination mechanism) on the machines, each out of n players chooses a machine to assign his owned job to, so as to minimize his individual completion time. Each job has a processing length and is of a certain type. Same-type jobs incur a setup overhead to the machine they are assigned to. We study the Price of Anarchy with respect to the makespan of stable assignments, that are pure Nash or strong equilibria for the underlying strategic game. We study in detail the performance of a well established preemptive scheduling mechanism. In an effort to improve over its performance, we introduce a class of mechanisms with certain properties, for which we examine existence of pure Nash and strong equilibria. We identify their performance limitations, and analyze an optimum mechanism out of this class. Finally, we point out several interesting open problems.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aumann, R.J.: Acceptable points in games of perfect information. Pacific Journal of Mathematics 10, 381–417 (1960)
Koutsoupias, E., Papadimitriou, C.H.: Worst-case Equilibria. In: Proc. STACS. LNCS, vol. 1543, pp. 404–413. Springer, Heidelberg (1999)
Christodoulou, G., Koutsoupias, E., Nanavati, A.: Coordination Mechanisms. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 345–357. Springer, Heidelberg (2004)
Koutsoupias, E., Mavronicolas, M., Spirakis, P.G.: Approximate Equilibria and Ball Fusion. Theory of Computing Systems 36(6), 683–693 (2003)
Czumaj, A., Vöcking, B.: Tight bounds for worst-case equilibria. ACM Transactions on Algorithms 3(1) (2007)
Christodoulou, G., Gourvès, L., Pascual, F.: Scheduling Selfish Tasks: About the Performance of Truthful Algorithms. In: Lin, G. (ed.) COCOON 2007. LNCS, vol. 4598, pp. 187–197. Springer, Heidelberg (2007)
Immorlica, N., Li, L., Mirrokni, V.S., Schulz, A.: Coordination Mechanisms for Selfish Scheduling. In: Deng, X., Ye, Y. (eds.) WINE 2005. LNCS, vol. 3828, pp. 55–69. Springer, Heidelberg (2005)
Azar, Y., Jain, K., Mirrokni, V.S.: (almost) optimal coordination mechanisms for unrelated machine scheduling. In: Proc. ACM-SIAM SODA, pp. 323–332 (2008)
Caragiannis, I.: Efficient coordination mechanisms for unrelated machine scheduling. In: Proc. AMC-SIAM SODA, pp. 815–824 (2009)
Durr, C., Nguyen, T.K.: Non-clairvoyant Scheduling Games. In: Proc. SAGT. LNCS. Springer, Heidelberg (to appear, 2009)
Andelman, N., Feldman, M., Mansour, Y.: Strong price of anarchy. In: Proc. ACM-SIAM SODA, pp. 189–198 (2007)
Epstein, L., van Stee, R.: The Price of Anarchy on Uniformly Related Machines Revisited. In: Monien, B., Schroeder, U.-P. (eds.) SAGT 2008. LNCS, vol. 4997, pp. 46–57. Springer, Heidelberg (2008)
Vöcking, B.: Selfish Load Balancing. In: Algorithmic Game Theory, ch. 20, pp. 517–542. Cambridge University Press, Cambridge (2007)
Finn, G., Horowitz, E.: A linear time approximation algorithm for multiprocessor scheduling. BIT 19, 312–320 (1979)
Schuurman, P., Vredeveld, T.: Performance guarantees of local search for multiprocessor scheduling. In: Aardal, K., Gerards, B. (eds.) IPCO 2001. LNCS, vol. 2081, pp. 370–382. Springer, Heidelberg (2001)
Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer, Heidelberg (1999)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-completeness. W.H.Freeman & Co Ltd., New York (1979)
Schuurman, P., Wöginger, G.J.: Preemptive scheduling with job-dependent setup times. In: Proc. ACM-SIAM SODA, pp. 759–767 (1999)
Chen, B.: A better heuristic for preemptive parallel machine scheduling with batch setup times. SIAM Journal on Computing 22, 1303–1318 (1993)
Wöginger, G.J., Yu, Z.: A heuristic for preemptive scheduling with set-up times. Computing 49(2), 151–158 (1992)
Chen, B., Ye, Y., Zhang, J.: Lot-sizing scheduling with batch setup times. Journal of Scheduling 9(3), 299–310 (2006)
Jukna, S.: Extremal Combinatorics with Applications in Computer Science. Springer, Heidelberg (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gourvès, L., Monnot, J., Telelis, O.A. (2009). Selfish Scheduling with Setup Times. In: Leonardi, S. (eds) Internet and Network Economics. WINE 2009. Lecture Notes in Computer Science, vol 5929. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-10841-9_27
Download citation
DOI: https://doi.org/10.1007/978-3-642-10841-9_27
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-10840-2
Online ISBN: 978-3-642-10841-9
eBook Packages: Computer ScienceComputer Science (R0)