IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v285y2020i1d10.1007_s10479-019-03235-w.html
   My bibliography  Save this article

Price of anarchy and price of stability in multi-agent project scheduling

Author

Listed:
  • Alessandro Agnetis

    (Università degli Studi di Siena)

  • Cyril Briand

    (LAAS-CNRS, Université de Toulouse, CNRS, UPS)

  • Sandra Ulrich Ngueveu

    (LAAS-CNRS, Université de Toulouse, CNRS, INP)

  • Přemysl Šůcha

    (Czech Technical University in Prague)

Abstract

We consider a project scheduling environment in which the activities are partitioned among a set of agents. The owner of each activity can decide its length, which is linearly related to its cost within a minimum (crash) and a maximum (normal) length. For each day the project makespan is reduced with respect to its normal value, a reward is offered to the agents, and each agent receives a given ratio of the reward. As in classical game theory, we assume that the agents’ parameters are common knowledge. We study the Nash equilibria of the corresponding non-cooperative game as a desired state where no agent is motivated to change his/her decision. Regarding project makespan as an overall measure of efficiency, here we consider the worst and the best Nash equilibria (i.e., for which makespan is maximum and, respectively, minimum among Nash equilibria). We show that the problem of finding the worst Nash equilibrium is NP-hard (finding the best Nash equilibrium is already known to be strongly NP-hard), and propose an ILP formulation for its computation. We then investigate the values of the price of anarchy and the price of stability in a large sample of realistic size problems and get useful insights for the project owner.

Suggested Citation

  • Alessandro Agnetis & Cyril Briand & Sandra Ulrich Ngueveu & Přemysl Šůcha, 2020. "Price of anarchy and price of stability in multi-agent project scheduling," Annals of Operations Research, Springer, vol. 285(1), pages 97-119, February.
    • Handle: RePEc:spr:annopr:v:285:y:2020:i:1:d:10.1007_s10479-019-03235-w
    DOI: 10.1007/s10479-019-03235-w
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-019-03235-w
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10479-019-03235-w?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. De Reyck, Bert & Herroelen, Willy, 1999. "The multi-mode resource-constrained project scheduling problem with generalized precedence relations," European Journal of Operational Research, Elsevier, vol. 119(2), pages 538-556, December.
    2. Cyril Briand & Sandra Ulrich Ngueveu & Přemysl Šůcha, 2017. "Finding an optimal Nash equilibrium to the multi-agent project scheduling problem," Journal of Scheduling, Springer, vol. 20(5), pages 475-491, October.
    3. Averbakh, Igor, 2010. "Nash equilibria in competitive project scheduling," European Journal of Operational Research, Elsevier, vol. 205(3), pages 552-556, September.
    4. Steve Phillips, Jr. & Mohamed I. Dessouky, 1977. "Solving the Project Time/Cost Tradeoff Problem Using the Minimal Cut Concept," Management Science, INFORMS, vol. 24(4), pages 393-400, December.
    5. Kolisch, Rainer & Sprecher, Arno & Drexl, Andreas, 1992. "Characterization and generation of a general class of resource-constrained project scheduling problems: Easy and hard instances," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 301, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    6. Giuseppe Confessore & Stefano Giordani & Silvia Rismondo, 2007. "A market-based multi-agent system model for decentralized multi-project scheduling," Annals of Operations Research, Springer, vol. 150(1), pages 115-135, March.
    7. W Herroelen & B De Reyck, 1999. "Phase transitions in project scheduling," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 50(2), pages 148-156, February.
    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. Kameda, Hisao, 2021. "Magnitude of inefficiency," European Journal of Operational Research, Elsevier, vol. 292(3), pages 1133-1145.
    2. Šůcha, Přemysl & Agnetis, Alessandro & Šidlovský, Marko & Briand, Cyril, 2021. "Nash equilibrium solutions in multi-agent project scheduling with milestones," European Journal of Operational Research, Elsevier, vol. 294(1), pages 29-41.
    3. Wuliang Peng & Jiali lin & Jingwen Zhang & Liangwei Chen, 2022. "A bi-objective hierarchical program scheduling problem and its solution based on NSGA-III," Annals of Operations Research, Springer, vol. 308(1), pages 389-414, January.

    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. Šůcha, Přemysl & Agnetis, Alessandro & Šidlovský, Marko & Briand, Cyril, 2021. "Nash equilibrium solutions in multi-agent project scheduling with milestones," European Journal of Operational Research, Elsevier, vol. 294(1), pages 29-41.
    2. Dayal Madhukar & Verma, Sanjay, 2015. "Multi-processor Exact Procedures for Regular Measures of the Multi-mode RCPSP," IIMA Working Papers WP2015-03-25, Indian Institute of Management Ahmedabad, Research and Publication Department.
    3. Cyril Briand & Sandra Ulrich Ngueveu & Přemysl Šůcha, 2017. "Finding an optimal Nash equilibrium to the multi-agent project scheduling problem," Journal of Scheduling, Springer, vol. 20(5), pages 475-491, October.
    4. Hartmann, Sönke & Briskorn, Dirk, 2010. "A survey of variants and extensions of the resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 207(1), pages 1-14, November.
    5. Hartmann, Sönke & Briskorn, Dirk, 2008. "A survey of variants and extensions of the resource-constrained project scheduling problem," Working Paper Series 02/2008, Hamburg School of Business Administration (HSBA).
    6. M. Vanhoucke & J. Coelho & L. V. Tavares & D. Debels, 2004. "On The Morphological Structure Of A Network," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 04/272, Ghent University, Faculty of Economics and Business Administration.
    7. Adhau, Sunil & Mittal, M.L. & Mittal, Abhinav, 2013. "A multi-agent system for decentralized multi-project scheduling with resource transfers," International Journal of Production Economics, Elsevier, vol. 146(2), pages 646-661.
    8. Vo[ss], Stefan & Witt, Andreas, 2007. "Hybrid flow shop scheduling as a multi-mode multi-project scheduling problem with batching requirements: A real-world application," International Journal of Production Economics, Elsevier, vol. 105(2), pages 445-458, February.
    9. Bredael, Dries & Vanhoucke, Mario, 2023. "Multi-project scheduling: A benchmark analysis of metaheuristic algorithms on various optimisation criteria and due dates," European Journal of Operational Research, Elsevier, vol. 308(1), pages 54-75.
    10. Chen, Shih-Pin & Tsai, Ming-Jiun, 2011. "Time-cost trade-off analysis of project networks in fuzzy environments," European Journal of Operational Research, Elsevier, vol. 212(2), pages 386-397, July.
    11. A B Hafızoğlu & M Azizoğlu, 2010. "Linear programming based approaches for the discrete time/cost trade-off problem in project networks," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(4), pages 676-685, April.
    12. Hermel, Dror & Hasheminia, Hamed & Adler, Nicole & Fry, Michael J., 2016. "A solution framework for the multi-mode resource-constrained cross-dock scheduling problem," Omega, Elsevier, vol. 59(PB), pages 157-170.
    13. J. C. Gonçalves-Dosantos & I. García-Jurado & J. Costa, 2020. "Sharing delay costs in stochastic scheduling problems with delays," 4OR, Springer, vol. 18(4), pages 457-476, December.
    14. V. Van Peteghem & M. Vanhoucke, 2009. "Using Resource Scarceness Characteristics to Solve the Multi-Mode Resource-Constrained Project Scheduling Problem," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 09/595, Ghent University, Faculty of Economics and Business Administration.
    15. D. Debels & M. Vanhoucke, 2006. "The impact of various activity assumptions on the lead-time and resource utilization of resource-constrained projects," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 06/385, Ghent University, Faculty of Economics and Business Administration.
    16. Tamara Borreguero Sanchidrián & Tom Portoleau & Christian Artigues & Alvaro García Sánchez & Miguel Ortega Mier & Pierre Lopez, 2024. "Large neighborhood search for an aeronautical assembly line time-constrained scheduling problem with multiple modes and a resource leveling objective," Annals of Operations Research, Springer, vol. 338(1), pages 13-40, July.
    17. Vanhoucke, Mario & Coelho, Jose & Debels, Dieter & Maenhout, Broos & Tavares, Luis V., 2008. "An evaluation of the adequacy of project network generators with systematically sampled networks," European Journal of Operational Research, Elsevier, vol. 187(2), pages 511-524, June.
    18. Rahman Torba & Stéphane Dauzère-Pérès & Claude Yugma & Cédric Gallais & Juliette Pouzet, 2024. "Solving a real-life multi-skill resource-constrained multi-project scheduling problem," Annals of Operations Research, Springer, vol. 338(1), pages 69-114, July.
    19. Patoghi, Amirhosein & Mousavi, Seyed Meysam, 2021. "A new approach for material ordering and multi-mode resource constraint project scheduling problem in a multi-site context under interval-valued fuzzy uncertainty," Technological Forecasting and Social Change, Elsevier, vol. 173(C).
    20. Sprecher, Arno, 2000. "SALBLIB: Challenging instances for assembly line balancing," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 526, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.

    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:spr:annopr:v:285:y:2020:i:1:d:10.1007_s10479-019-03235-w. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.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.