Abstract
We study the convergence time of local search for a standard machine scheduling problem in which jobs are assigned to identical or related machines. Local search corresponds to the best response dynamics that arises when jobs selfishly try to minimize their costs. We assume that each machine runs a coordination mechanism that determines the order of execution of jobs assigned to it. We obtain various new polynomial and pseudo-polynomial bounds for the well-studied coordination mechanisms Makespan and Shortest-Job-First, using worst-case and smoothed analysis. We also introduce a natural coordination mechanism FIFO, which takes into account the order in which jobs arrive at a machine, and study both its impact on the convergence time and its price of anarchy.
This research was supported by ERC Starting Grant 306465 (BeyondWorstCase).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Beier, R., Vöcking, B.: Random knapsack in expected polynomial time. J. Comput. Syst. Sci. 69(3), 306–329 (2004)
Brucker, P., Hurink, J., Werner, F.: Models and algorithms for planning and scheduling problems improving local search heuristics for some scheduling problems. Part II. Discrete Appl. Math. 72(1), 47–69 (1997). doi:http://dx.doi.org/10.1016/S0166-218X(96)00036-4
Brunsch, T., Röglin, H., Rutten, C., Vredeveld, T.: Smoothed performance guarantees for local search. Math. Program. 146(1–2, Ser. A), 185–218 (2014). doi:10.1007/s10107-013-0683-7
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). doi:10.1007/978-3-540-27836-8_31
Czumaj, A., Vöcking, B.: Tight bounds for worst-case equilibria. Trans. Algorithms ACM 3(1) (2007)
Etscheid, M.: Performance guarantees for scheduling algorithms under perturbed machine speeds. In: Cai, L., Cheng, S.-W., Lam, T.-W. (eds.) ISAAC 2013. LNCS, vol. 8283, pp. 207–217. Springer, Heidelberg (2013). doi:10.1007/978-3-642-45030-3_20
Even-Dar, E., Kesselman, A., Mansour, Y.: Convergence time to Nash equilibria. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 502–513. Springer, Heidelberg (2003). doi:10.1007/3-540-45061-0_41
Feldmann, R., Gairing, M., Lücking, T., Monien, B., Rode, M.: Nashification and the coordination ratio for a selfish routing game. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 514–526. Springer, Heidelberg (2003). doi:10.1007/3-540-45061-0_42
Finn, G., Horowitz, E.: A linear time approximation algorithm for multiprocessor scheduling. BIT 19, 312–320 (1979)
Garey, M.R., Johnson, D.S.: Complexity results for multiprocessor scheduling under resource constraints. SIAM J. Comput. 4, 397–411 (1975)
Goldberg, P.W.: Bounds for the convergence rate of randomized local search in a multiplayer load-balancing game. In: Proceedings of the PODC 2004, pp. 131–140 (2004). doi:10.1145/1011767.1011787
Hurkens, C.A.J., Vredeveld, T.: Local search for multiprocessor scheduling: how many moves does it take to a local optimum? Oper. Res. Lett. 31(2), 137–141 (2003)
Immorlica, N., Li, L., Mirrokni, V.S., Schulz, A.S.: Coordination mechanisms for selfish scheduling. Theor. Comput. Sci. 410(17), 1589–1598 (2009). doi:10.1016/j.tcs.2008.12.032
Manthey, B., Röglin, H.: Smoothed analysis: analysis of algorithms beyond worst case. IT - Information Technology 53(6), 280–286 (2011)
Rosenthal, R.W.: A class of games possessing pure-strategy Nash equilibria. Internat. J. Game Theor. 2, 65–67 (1973)
Schuurman, P., Vredeveld, T.: Performance guarantees of local search for multiprocessor scheduling. Informs J. Comput. 19(1), 52–63 (2007)
Spielman, D., Teng, S.-H.: Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time. J. ACM 51(3), 385–463 (2004)
Spielman, D., Teng, S.-H.: Smoothed analysis: an attempt to explain the behavior of algorithms in practice. Commun. ACM 52(10), 76–84 (2009)
Acknowledgments
We thank Clemens Rösner for helpful discussions about the lower bounds for the SJF model and the proof of Theorem 2.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer-Verlag GmbH Germany
About this paper
Cite this paper
Brunsch, T., Etscheid, M., Röglin, H. (2016). Bounds for the Convergence Time of Local Search in Scheduling Problems. In: Cai, Y., Vetta, A. (eds) Web and Internet Economics. WINE 2016. Lecture Notes in Computer Science(), vol 10123. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-54110-4_24
Download citation
DOI: https://doi.org/10.1007/978-3-662-54110-4_24
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-54109-8
Online ISBN: 978-3-662-54110-4
eBook Packages: Computer ScienceComputer Science (R0)