IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v12y2024i14p2223-d1436353.html
   My bibliography  Save this article

Bounding the Price of Anarchy of Weighted Shortest Processing Time Policy on Uniform Parallel Machines

Author

Listed:
  • Felipe T. Muñoz

    (Departamento de Ingeniería Industrial, Facultad de Ingeniería, Universidad del Bío-Bío, Concepción 4030000, Chile)

  • Rodrigo Linfati

    (Departamento de Ingeniería Industrial, Facultad de Ingeniería, Universidad del Bío-Bío, Concepción 4030000, Chile)

Abstract

This article investigates the performance of the Weighted Shortest Processing Time (WSPT) rule as a local sequencing policy in a scheduling game for uniformly related parallel machines, where the social objective is the total weighted completion time. Our research aims to establish improved upper bounds for the price of anarchy in this game. We determine two bounds, incorporating parameters that characterize the instance family, such as the speed of the fastest machine ( s m ) and the number of machines ( m ). One bound establishes a fixed upper bound for the price of anarchy, while the other outperforms the parametric upper bound found in the existing literature. These newly derived bounds provide better insights into the performance of the scheduling game under study, proving that the price of anarchy is upper bounded by min s m 1 + 1 / 2 s m − 1 / 2 m , m , 4 .

Suggested Citation

  • Felipe T. Muñoz & Rodrigo Linfati, 2024. "Bounding the Price of Anarchy of Weighted Shortest Processing Time Policy on Uniform Parallel Machines," Mathematics, MDPI, vol. 12(14), pages 1-12, July.
    • Handle: RePEc:gam:jmathe:v:12:y:2024:i:14:p:2223-:d:1436353
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/12/14/2223/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/12/14/2223/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. 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.
    2. Lee, Kangbok & Leung, Joseph Y.-T. & Pinedo, Michael L., 2012. "Coordination mechanisms for parallel machine scheduling," European Journal of Operational Research, Elsevier, vol. 220(2), pages 305-313.
    3. 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.
    4. Averbakh, Igor, 2010. "Nash equilibria in competitive project scheduling," European Journal of Operational Research, Elsevier, vol. 205(3), pages 552-556, September.
    5. 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.
    6. Cole, Richard & Correa, José R. & Gkatzelis, Vasilis & Mirrokni, Vahab & Olver, Neil, 2015. "Decentralized utilitarian mechanisms for scheduling games," Games and Economic Behavior, Elsevier, vol. 92(C), pages 306-326.
    7. Rzadca, Krzysztof & Trystram, Denis, 2009. "Promoting cooperation in selfish computational grids," European Journal of Operational Research, Elsevier, vol. 199(3), pages 647-657, December.
    8. 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.
    9. Pramod C. Mane & Nagarajan Krishnamurthy & Kapil Ahuja, 2019. "Formation of Stable and Efficient Social Storage Cloud," Games, MDPI, vol. 10(4), pages 1-17, November.
    10. Xinmin Zhou & Wenhao Rao & Yaqiong Liu & Shudong Sun, 2024. "A Decentralized Optimization Algorithm for Multi-Agent Job Shop Scheduling with Private Information," Mathematics, MDPI, vol. 12(7), pages 1-22, March.
    11. W. L. Eastman & S. Even & I. M. Isaacs, 1964. "Bounds for the Optimal Scheduling of n Jobs on m Processors," Management Science, INFORMS, vol. 11(2), pages 268-279, November.
    12. Wayne E. Smith, 1956. "Various optimizers for single‐stage production," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 3(1‐2), pages 59-66, March.
    13. Hao Guo & Weidong Li & Bin Deng, 2023. "A Survey on Fair Allocation of Chores," Mathematics, MDPI, vol. 11(16), pages 1-28, August.
    Full references (including those not matched with items on IDEAS)

    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. 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.
    2. Cong Chen & Paul Giessler & Akaki Mamageishvili & Matúš Mihalák & Paolo Penna, 2024. "Sequential solutions in machine scheduling games," Journal of Scheduling, Springer, vol. 27(4), pages 363-373, August.
    3. 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.
    4. Ravindran Vijayalakshmi, Vipin & Schröder, Marc & Tamir, Tami, 2024. "Minimizing total completion time with machine-dependent priority lists," European Journal of Operational Research, Elsevier, vol. 315(3), pages 844-854.
    5. 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.
    6. Tami Tamir, 2023. "Cost-sharing games in real-time scheduling systems," International Journal of Game Theory, Springer;Game Theory Society, vol. 52(1), pages 273-301, March.
    7. Kramer, Arthur & Dell’Amico, Mauro & Iori, Manuel, 2019. "Enhanced arc-flow formulations to minimize weighted completion time on identical parallel machines," European Journal of Operational Research, Elsevier, vol. 275(1), pages 67-79.
    8. Bachtenkirch, David & Bock, Stefan, 2022. "Finding efficient make-to-order production and batch delivery schedules," European Journal of Operational Research, Elsevier, vol. 297(1), pages 133-152.
    9. 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.
    10. Ilan Reuven Cohen & Izack Cohen & Iyar Zaks, 2024. "A theoretical and empirical study of job scheduling in cloud computing environments: the weighted completion time minimization problem with capacitated parallel machines," Annals of Operations Research, Springer, vol. 338(1), pages 429-452, July.
    11. 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.
    12. Lee, Kangbok & Leung, Joseph Y.-T. & Pinedo, Michael L., 2012. "Coordination mechanisms for parallel machine scheduling," European Journal of Operational Research, Elsevier, vol. 220(2), pages 305-313.
    13. 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.
    14. Hui Liu & Maurice Queyranne & David Simchi‐Levi, 2005. "On the asymptotic optimality of algorithms for the flow shop problem with release dates," Naval Research Logistics (NRL), John Wiley & Sons, vol. 52(3), pages 232-242, April.
    15. Marieke Quant & Marc Meertens & Hans Reijnierse, 2008. "Processing games with shared interest," Annals of Operations Research, Springer, vol. 158(1), pages 219-228, February.
    16. 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.
    17. Ben Hermans & Roel Leus & Jannik Matuschke, 2022. "Exact and Approximation Algorithms for the Expanding Search Problem," INFORMS Journal on Computing, INFORMS, vol. 34(1), pages 281-296, January.
    18. Qiuping Yu & Gad Allon & Achal Bassamboo & Seyed Iravani, 2018. "Managing Customer Expectations and Priorities in Service Systems," Management Science, INFORMS, vol. 64(8), pages 3942-3970, August.
    19. Lili Liu & Guochun Tang & Baoqiang Fan & Xingpeng Wang, 2015. "Two-person cooperative games on scheduling problems in outpatient pharmacy dispensing process," Journal of Combinatorial Optimization, Springer, vol. 30(4), pages 938-948, November.
    20. van Beek, Andries & Malmberg, Benjamin & Borm, Peter & Quant, Marieke & Schouten, Jop, 2021. "Cooperation and Competition in Linear Production and Sequencing Processes," Discussion Paper 2021-011, Tilburg University, Center for Economic Research.

    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:gam:jmathe:v:12:y:2024:i:14:p:2223-:d:1436353. 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: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    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.