IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v63y2015i3p489-500.html
   My bibliography  Save this article

Optimal Coordination Mechanisms for Unrelated Machine Scheduling

Author

Listed:
  • Yossi Azar

    (School of Computer Science, Tel-Aviv University, Tel-Aviv 69978, Israel)

  • Lisa Fleischer

    (Department of Computer Science, Dartmouth, Hanover, New Hampshire 03755)

  • Kamal Jain

    (Ebay Research, Bellevue, Washington 98004)

  • Vahab Mirrokni

    (Google Research, New York, New York 10011)

  • Zoya Svitkina

    (Google, Mountain View, California 94043)

Abstract

We investigate the influence of different algorithmic choices on the approximation ratio in selfish scheduling. Our goal is to design local policies that minimize the inefficiency of resulting equilibria. In particular, we design optimal coordination mechanisms for unrelated machine scheduling, and improve the known approximation ratio from Θ( m ) to Θ(log m ), where m is the number of machines.A local policy for each machine orders the set of jobs assigned to it only based on parameters of those jobs. A strongly local policy only uses the processing time of jobs on the same machine. We prove that the approximation ratio of any set of strongly local ordering policies in equilibria is at least Ω( m ). In particular, it implies that the approximation ratio of a greedy shortest-first algorithm for machine scheduling is at least Ω( m ). This closes the gap between the known lower and upper bounds for this problem and answers an open question raised by Ibarra and Kim (1977) [Ibarra OH, Kim CE (1977) Heuristic algorithms for scheduling independent tasks on nonidentical processors. J. ACM 24(2):280–289.], and Davis and Jaffe (1981) [Davis E, Jaffe JM (1981) Algorithms for scheduling tasks on unrelated processors. J. ACM 28(4):721–736.]. We then design a local ordering policy with the approximation ratio of Θ(log m ) in equilibria, and prove that this policy is optimal among all local ordering policies. This policy orders the jobs in the nondecreasing order of their inefficiency, i.e., the ratio between the processing time on that machine over the minimum processing time. Finally, we show that best responses of players for the inefficiency-based policy may not converge to a pure Nash equilibrium, and present a Θ(log 2 m ) policy for which we can prove fast convergence of best responses to pure Nash equilibria.

Suggested Citation

  • Yossi Azar & Lisa Fleischer & Kamal Jain & Vahab Mirrokni & Zoya Svitkina, 2015. "Optimal Coordination Mechanisms for Unrelated Machine Scheduling," Operations Research, INFORMS, vol. 63(3), pages 489-500, June.
  • Handle: RePEc:inm:oropre:v:63:y:2015:i:3:p:489-500
    DOI: 10.1287/opre.2015.1363
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.2015.1363
    Download Restriction: no

    File URL: https://libkey.io/10.1287/opre.2015.1363?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Rohde, K.I.M., 2005. "A reason for sophisticated investors not to seize arbitrage opportunities in markets without frictions," Research Memorandum 054, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    2. José R. Correa & Maurice Queyranne, 2012. "Efficiency of equilibria in restricted uniform machine scheduling with total weighted completion time as social cost," Naval Research Logistics (NRL), John Wiley & Sons, vol. 59(5), pages 384-395, August.
    3. Schuurman, P. & Vredeveld, T., 2005. "Performance guarantees of local search for multiprocessor scheduling," Research Memorandum 055, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Rosner, Shaul & Tamir, Tami, 2023. "Scheduling games with rank-based utilities," Games and Economic Behavior, Elsevier, vol. 140(C), pages 229-252.
    2. Chen, Qianqian & Lin, Ling & Tan, Zhiyi & Yan, Yujie, 2017. "Coordination mechanisms for scheduling games with proportional deterioration," European Journal of Operational Research, Elsevier, vol. 263(2), pages 380-389.
    3. Cong Chen & Yinfeng Xu, 0. "Coordination mechanisms for scheduling selfish jobs with favorite machines," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-33.
    4. Cong Chen & Yinfeng Xu, 2020. "Coordination mechanisms for scheduling selfish jobs with favorite machines," Journal of Combinatorial Optimization, Springer, vol. 40(2), pages 333-365, August.
    5. Briskorn, Dirk & Waldherr, Stefan, 2022. "Anarchy in the UJ: Coordination mechanisms for minimizing the number of late jobs," European Journal of Operational Research, Elsevier, vol. 301(3), pages 815-827.
    6. Vasilis Gkatzelis & Konstantinos Kollias & Tim Roughgarden, 2016. "Optimal Cost-Sharing in General Resource Selection Games," Operations Research, INFORMS, vol. 64(6), pages 1230-1238, December.
    7. Pascual, Fanny & Rzadca, Krzysztof, 2018. "Colocating tasks in data centers using a side-effects performance model," European Journal of Operational Research, Elsevier, vol. 268(2), pages 450-462.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Cole, Richard & Correa, Jose & Gkatzelis, Vasillis & Mirrokni, Vahab & Olver, Neil, 2015. "Decentralized utilitarian mechanisms for scheduling games," LSE Research Online Documents on Economics 103081, London School of Economics and Political Science, LSE Library.
    2. Guoqiang Fan & Qingqin Nong, 2018. "A Coordination Mechanism for a Scheduling Game with Uniform-Batching Machines," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 35(05), pages 1-15, October.
    3. Petra Schuurman & Tjark Vredeveld, 2007. "Performance Guarantees of Local Search for Multiprocessor Scheduling," INFORMS Journal on Computing, INFORMS, vol. 19(1), pages 52-63, February.
    4. C N Potts & V A Strusevich, 2009. "Fifty years of scheduling: a survey of milestones," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(1), pages 41-68, May.
    5. Francisco Castillo-Zunino & Pinar Keskinocak, 2021. "Bi-criteria multiple knapsack problem with grouped items," Journal of Heuristics, Springer, vol. 27(5), pages 747-789, October.
    6. Braat, Jac & Hamers, Herbert & Klijn, Flip & Slikker, Marco, 2019. "A selfish allocation heuristic in scheduling: Equilibrium and inefficiency bound analysis," European Journal of Operational Research, Elsevier, vol. 273(2), pages 634-645.
    7. Cong Chen & Yinfeng Xu, 0. "Coordination mechanisms for scheduling selfish jobs with favorite machines," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-33.
    8. Varun Gupta & Benjamin Moseley & Marc Uetz & Qiaomin Xie, 2020. "Greed Works—Online Algorithms for Unrelated Machine Stochastic Scheduling," Mathematics of Operations Research, INFORMS, vol. 45(2), pages 497-516, May.
    9. Heydenreich, B. & Müller, R.J. & Uetz, M.J., 2006. "Games and mechanism design in machine scheduling - an introduction," Research Memorandum 022, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    10. Brueggemann, T. & Hurink, J.L. & Vredeveld, T. & Woeginger, G.J., 2006. "Very large-scale neighborhoods with performance guarantees for minimizing makespan on parallel machines," Research Memorandum 052, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    11. Cong Chen & Yinfeng Xu, 2020. "Coordination mechanisms for scheduling selfish jobs with favorite machines," Journal of Combinatorial Optimization, Springer, vol. 40(2), pages 333-365, August.
    12. Herbert Hamers & Flip Klijn & Marco Slikker, 2019. "Implementation of optimal schedules in outsourcing with identical suppliers," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 89(2), pages 173-187, April.
    13. Q. Q. Nong & G. Q. Fan & Q. Z. Fang, 2017. "A coordination mechanism for a scheduling game with parallel-batching machines," Journal of Combinatorial Optimization, Springer, vol. 33(2), pages 567-579, February.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:63:y:2015:i:3:p:489-500. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.