IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v295y2021i1p12-21.html
   My bibliography  Save this article

Open shop scheduling games

Author

Listed:
  • Atay, Ata
  • Calleja, Pedro
  • Soteras, Sergio

Abstract

This paper takes a game theoretical approach to open shop scheduling problems to minimize the sum of completion times. We assume that there is an initial schedule to process the jobs (consisting of a number of operations) on the machines and that each job is owned by a different player. Thus, we can associate a cooperative TU-game to any open shop scheduling problem, assigning to each coalition the maximal cost savings it can obtain through admissible rearrangements of jobs’ operations. A number of different approaches to admissible schedules for a coalition are introduced and, in the main result of the paper, a core allocation rule is provided for games arising from unit (execution times and weights) open shop scheduling problems for the most of these approaches. To sharpen the bounds of the set of open shop scheduling problems that result in games that are balanced, we provide two counterexamples: one for general open shop problems and another for further relaxations of the definition of admissible rearrangements for a coalition.

Suggested Citation

  • Atay, Ata & Calleja, Pedro & Soteras, Sergio, 2021. "Open shop scheduling games," European Journal of Operational Research, Elsevier, vol. 295(1), pages 12-21.
    • Handle: RePEc:eee:ejores:v:295:y:2021:i:1:p:12-21
    DOI: 10.1016/j.ejor.2021.02.030
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221721001235
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2021.02.030?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 look for a different version below or search for a different version of it.

    Other versions of this item:

    References listed on IDEAS

    as
    1. Curiel, I. & Potters, J.A.M. & Rajendra Prasad, V. & Tijs, S.H. & Veltman, B., 1994. "Sequencing and cooperation," Other publications TiSEM be67f9e9-7a4a-47f1-9fb9-7, Tilburg University, School of Economics and Management.
    2. Pedro Calleja & Peter Borm & Herbert Hamers & Flip Klijn & Marco Slikker, 2002. "On a New Class of Parallel Sequencing Situations and Related Games," Annals of Operations Research, Springer, vol. 109(1), pages 265-277, January.
    3. M. Musegaas & P. E. M. Borm & M. Quant, 2018. "On the convexity of step out–step in sequencing games," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 26(1), pages 68-109, April.
    4. Marco Slikker, 2006. "Relaxed sequencing games have a nonempty core," Naval Research Logistics (NRL), John Wiley & Sons, vol. 53(4), pages 235-242, June.
    5. Hamers, H.J.M. & Borm, P.E.M. & Tijs, S.H., 1993. "On games corresponding to sequencing situations with ready times," Other publications TiSEM 8e2af556-5430-4f98-9334-c, Tilburg University, School of Economics and Management.
    6. Hamers, Herbert & Klijn, Flip & Suijs, Jeroen, 1999. "On the balancedness of multiple machine sequencing games," European Journal of Operational Research, Elsevier, vol. 119(3), pages 678-691, December.
    7. Borm, Peter & Fiestras-Janeiro, Gloria & Hamers, Herbert & Sanchez, Estela & Voorneveld, Mark, 2002. "On the convexity of games corresponding to sequencing situations with due dates," European Journal of Operational Research, Elsevier, vol. 136(3), pages 616-634, February.
    8. Musegaas, M. & Borm, P.E.M. & Quant, M., 2015. "Step out–Step in sequencing games," European Journal of Operational Research, Elsevier, vol. 246(3), pages 894-906.
    9. Curiel, I. & Potters, J.A.M. & Rajendra Prasad, V. & Tijs, S.H. & Veltman, B., 1993. "Cooperation in one machine scheduling," Other publications TiSEM 9c5ceec5-2080-4b5c-98d5-0, Tilburg University, School of Economics and Management.
    10. van den Nouweland, Anne & Krabbenborg, Marc & Potters, Jos, 1992. "Flow-shops with a dominant machine," European Journal of Operational Research, Elsevier, vol. 62(1), pages 38-46, October.
    11. Imma Curiel & Jos Potters & Rajendra Prasad & Stef Tijs & Bart Veltman, 1994. "Sequencing and Cooperation," Operations Research, INFORMS, vol. 42(3), pages 566-568, June.
    12. Bas van Velzen & Herbert Hamers, 2003. "On the balancedness of relaxed sequencing games," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 57(2), pages 287-297, May.
    13. Herbert Hamers & Flip Klijn & Bas van Velzen, 2002. "On Games corresponding to Sequencing Situations with Precedence Relations," UFAE and IAE Working Papers 553.02, Unitat de Fonaments de l'Anàlisi Econòmica (UAB) and Institut d'Anàlisi Econòmica (CSIC).
    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. Ata Atay & Christian Trudeau, 2022. "Queueing games with an endogenous number of machines," Working Papers 2202, University of Windsor, Department of Economics.

    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. Schouten, Jop & Saavedra-Nieves, Alejandro & Fiestras-Janeiro, G., 2020. "Sequencing Situations and Games with Non-Linear Cost Functions," Other publications TiSEM 3e1db5c9-0f77-4f91-a075-c, Tilburg University, School of Economics and Management.
    2. Schouten, Jop & Saavedra-Nieves, Alejandro & Fiestras-Janeiro, G., 2020. "Sequencing Situations and Games with Non-Linear Cost Functions," Discussion Paper 2020-006, Tilburg University, Center for Economic Research.
    3. van Velzen, S. & Hamers, H.J.M., 2002. "On the Balancedness of Relaxed Sequencing Games," Discussion Paper 2002-49, Tilburg University, Center for Economic Research.
    4. Yang, Guangjing & Sun, Hao & Hou, Dongshuang & Xu, Genjiu, 2019. "Games in sequencing situations with externalities," European Journal of Operational Research, Elsevier, vol. 278(2), pages 699-708.
    5. Gerichhausen, M. & Hamers, H.J.M., 2007. "Partitioning Sequencing Situations and Games," Other publications TiSEM 2bddbf5c-c56d-4b10-ba47-5, Tilburg University, School of Economics and Management.
    6. Gerichhausen, M. & Hamers, H.J.M., 2007. "Partitioning Sequencing Situations and Games," Discussion Paper 2007-40, Tilburg University, Center for Economic Research.
    7. Herbert Hamers & Flip Klijn & Bas Velzen, 2005. "On the Convexity of Precedence Sequencing Games," Annals of Operations Research, Springer, vol. 137(1), pages 161-175, July.
    8. Ata Atay & Christian Trudeau, 2022. "Queueing games with an endogenous number of machines," Papers 2207.07190, arXiv.org, revised Nov 2022.
    9. Gerichhausen, Marloes & Hamers, Herbert, 2009. "Partitioning sequencing situations and games," European Journal of Operational Research, Elsevier, vol. 196(1), pages 207-216, July.
    10. Pedro Calleja & Peter Borm & Herbert Hamers & Flip Klijn & Marco Slikker, 2002. "On a New Class of Parallel Sequencing Situations and Related Games," Annals of Operations Research, Springer, vol. 109(1), pages 265-277, January.
    11. Ciftci, B.B. & Borm, P.E.M. & Hamers, H.J.M. & Slikker, M., 2008. "Batch Sequencing and Cooperation," Other publications TiSEM ed1f8fce-da76-41a6-9a9e-9, Tilburg University, School of Economics and Management.
    12. Imma Curiel, 2010. "Multi-stage sequencing situations," International Journal of Game Theory, Springer;Game Theory Society, vol. 39(1), pages 151-162, March.
    13. Slikker, Marco, 2023. "The stable gain splitting rule for sequencing situations," European Journal of Operational Research, Elsevier, vol. 310(2), pages 902-913.
    14. Min Ji & Sai Liu & Xiaolin Zhang & Keke Cao & T. C. E. Cheng, 2017. "Sequencing Games with Slack Due Windows and Group Technology Considerations," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(2), pages 121-133, February.
    15. Herbert Hamers & Flip Klijn & Bas van Velzen, 2002. "On Games corresponding to Sequencing Situations with Precedence Relations," UFAE and IAE Working Papers 553.02, Unitat de Fonaments de l'Anàlisi Econòmica (UAB) and Institut d'Anàlisi Econòmica (CSIC).
    16. Saavedra-Nieves, Alejandro & Schouten, Jop & Borm, Peter, 2020. "On interactive sequencing situations with exponential cost functions," European Journal of Operational Research, Elsevier, vol. 280(1), pages 78-89.
    17. Chen, Jian & Huang, George Q. & Wang, Jun-Qiang & Yang, Chen, 2019. "A cooperative approach to service booking and scheduling in cloud manufacturing," European Journal of Operational Research, Elsevier, vol. 273(3), pages 861-873.
    18. van Velzen, S., 2003. "Sequencing Games with Controllable Processing Time," Discussion Paper 2003-105, Tilburg University, Center for Economic Research.
    19. van Velzen, S. & Hamers, H.J.M., 2002. "On the Balancedness of Relaxed Sequencing Games," Other publications TiSEM 14e21ac6-26af-438e-943b-9, Tilburg University, School of Economics and Management.
    20. Calleja, P. & Estevez Fernandez, M.A. & Borm, P.E.M. & Hamers, H.J.M., 2004. "Job Scheduling, Cooperation and Control," Other publications TiSEM 05906ac6-b582-4ee7-875e-9, Tilburg University, School of Economics and Management.

    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:eee:ejores:v:295:y:2021:i:1:p:12-21. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.