IDEAS home Printed from https://ideas.repec.org/a/spr/jsched/v27y2024i1d10.1007_s10951-023-00791-9.html
   My bibliography  Save this article

The price of anarchy for a berth allocation game

Author

Listed:
  • Jiayin Pan

    (Xi’an Jiaotong University)

  • Cong Chen

    (Guangzhou University
    South China University of Technology)

  • Yinfeng Xu

    (Xi’an Jiaotong University
    The State Key Lab for Manufacturing Systems Engineering)

Abstract

In this work, we investigate a berth allocation game involving m identical berths and n vessels. Each vessel selfishly selects a consecutive set of berths for unloading, with the objective of minimizing its own cost represented by the maximum load among the chosen berths. The social cost is defined as the makespan, i.e., the maximum load over all berths. Our game generalizes classical machine scheduling games where jobs (vessels) may require multiple consecutive machines (berths). We analyze the price of anarchy (PoA) of the berth allocation game, which quantifies the impact of selfish behaviors of vessels. Specifically, we first consider a special case where each job can occupy at most two consecutive machines, and derive exact upper and lower bounds for the PoA based on the number of machines m. We show that the PoA asymptotically approaches $$\frac{9}{4}$$ 9 4 . For the general case where each job can occupy an arbitrary number of consecutive machines, we obtain a tight bound for the PoA, which is $$\Theta \left( \frac{\log m}{\log \log m}\right) $$ Θ log m log log m .

Suggested Citation

  • Jiayin Pan & Cong Chen & Yinfeng Xu, 2024. "The price of anarchy for a berth allocation game," Journal of Scheduling, Springer, vol. 27(1), pages 51-60, February.
  • Handle: RePEc:spr:jsched:v:27:y:2024:i:1:d:10.1007_s10951-023-00791-9
    DOI: 10.1007/s10951-023-00791-9
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10951-023-00791-9
    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/s10951-023-00791-9?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. Rodrigues, Filipe & Agra, Agostinho, 2022. "Berth allocation and quay crane assignment/scheduling problem under uncertainty: A survey," European Journal of Operational Research, Elsevier, vol. 303(2), pages 501-524.
    2. Ioannis Caragiannis & Angelo Fanelli, 2019. "An Almost Ideal Coordination Mechanism for Unrelated Machine Scheduling," Post-Print hal-02089340, HAL.
    3. Errol L. Lloyd, 1981. "Concurrent Task Systems," Operations Research, INFORMS, vol. 29(1), pages 189-201, February.
    4. Jingui Huang & Jianer Chen & Songqiao Chen & Jianxin Wang, 2007. "A simple linear time approximation algorithm for multi-processor job scheduling on four processors," Journal of Combinatorial Optimization, Springer, vol. 13(1), pages 33-45, January.
    5. Andelman, Nir & Feldman, Michal & Mansour, Yishay, 2009. "Strong price of anarchy," Games and Economic Behavior, Elsevier, vol. 65(2), pages 289-317, March.
    6. 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.
    7. Jianer Chen & Chung‐Yee Lee, 1999. "General multiprocessor task scheduling," Naval Research Logistics (NRL), John Wiley & Sons, vol. 46(1), pages 57-74, February.
    8. Bierwirth, Christian & Meisel, Frank, 2015. "A follow-up survey of berth allocation and quay crane scheduling problems in container terminals," European Journal of Operational Research, Elsevier, vol. 244(3), pages 675-689.
    9. Bukchin, Yossi & Raviv, Tal & Zaides, Ilya, 2020. "The consecutive multiprocessor job scheduling problem," European Journal of Operational Research, Elsevier, vol. 284(2), pages 427-438.
    10. Imai, Akio & Sun, Xin & Nishimura, Etsuko & Papadimitriou, Stratos, 2005. "Berth allocation in a container port: using a continuous location space approach," Transportation Research Part B: Methodological, Elsevier, vol. 39(3), pages 199-221, March.
    11. Thanasis Lianeas & Evdokia Nikolova & Nicolas E. Stier-Moses, 2019. "Risk-Averse Selfish Routing," Mathematics of Operations Research, INFORMS, vol. 44(1), pages 38-57, February.
    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. Bukchin, Yossi & Raviv, Tal & Zaides, Ilya, 2020. "The consecutive multiprocessor job scheduling problem," European Journal of Operational Research, Elsevier, vol. 284(2), pages 427-438.
    2. Zhen, Lu & Zhuge, Dan & Wang, Shuaian & Wang, Kai, 2022. "Integrated berth and yard space allocation under uncertainty," Transportation Research Part B: Methodological, Elsevier, vol. 162(C), pages 1-27.
    3. Wang, Chong & Liu, Kaiyuan & Zhang, Canrong & Miao, Lixin, 2024. "Distributionally robust chance-constrained optimization for the integrated berth allocation and quay crane assignment problem," Transportation Research Part B: Methodological, Elsevier, vol. 182(C).
    4. El Mehdi, Er Raqabi & Ilyas, Himmich & Nizar, El Hachemi & Issmaïl, El Hallaoui & François, Soumis, 2023. "Incremental LNS framework for integrated production, inventory, and vessel scheduling: Application to a global supply chain," Omega, Elsevier, vol. 116(C).
    5. Xufeng Tang & Chang Liu & Xinqi Li & Ying Ji, 2023. "Distributionally Robust Programming of Berth-Allocation-with-Crane-Allocation Problem with Uncertain Quay-Crane-Handling Efficiency," Sustainability, MDPI, vol. 15(18), pages 1-27, September.
    6. Sung Won Cho & Hyun Ji Park & Chulung Lee, 2021. "An integrated method for berth allocation and quay crane assignment to allow for reassignment of vessels to other terminals," Maritime Economics & Logistics, Palgrave Macmillan;International Association of Maritime Economists (IAME), vol. 23(1), pages 123-153, March.
    7. Wu, Lingxiao & Wang, Shuaian, 2018. "Exact and heuristic methods to solve the parallel machine scheduling problem with multi-processor tasks," International Journal of Production Economics, Elsevier, vol. 201(C), pages 26-40.
    8. Meixian Jiang & Jiajia Feng & Jian Zhou & Lin Zhou & Fangzheng Ma & Guanghua Wu & Yuqiu Zhang, 2023. "Multi-Terminal Berth and Quay Crane Joint Scheduling in Container Ports Considering Carbon Cost," Sustainability, MDPI, vol. 15(6), pages 1-20, March.
    9. Cong Chen & Yinfeng Xu, 0. "Coordination mechanisms for scheduling selfish jobs with favorite machines," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-33.
    10. Agra, Agostinho & Oliveira, Maryse, 2018. "MIP approaches for the integrated berth allocation and quay crane assignment and scheduling problem," European Journal of Operational Research, Elsevier, vol. 264(1), pages 138-148.
    11. Liu, Changchun, 2020. "Iterative heuristic for simultaneous allocations of berths, quay cranes, and yards under practical situations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 133(C).
    12. Abou Kasm, Omar & Diabat, Ali & Chow, Joseph Y.J., 2023. "Simultaneous operation of next-generation and traditional quay cranes at container terminals," European Journal of Operational Research, Elsevier, vol. 308(3), pages 1110-1125.
    13. Yi Ding & Shuai Jia & Tianyi Gu & Chung-Lun Li, 2016. "SGICT Builds an Optimization-Based System for Daily Berth Planning," Interfaces, INFORMS, vol. 46(4), pages 281-296, August.
    14. Xiang, Xi & Liu, Changchun & Miao, Lixin, 2017. "A bi-objective robust model for berth allocation scheduling under uncertainty," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 106(C), pages 294-319.
    15. 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.
    16. Liu, Baoli & Li, Zhi-Chun & Wang, Yadong, 2022. "A two-stage stochastic programming model for seaport berth and channel planning with uncertainties in ship arrival and handling times," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 167(C).
    17. Haoqi Xie & Daniela Ambrosino, 2025. "Operations Research, Machine Learning, and Integrated Techniques for Decision Problems in the Seaside Area of Container Terminals," SN Operations Research Forum, Springer, vol. 6(2), pages 1-51, June.
    18. Shu-Chuan Chang & Ming-Hua Lin & Jung-Fa Tsai, 2024. "An Optimization Approach to Berth Allocation Problems," Mathematics, MDPI, vol. 12(5), pages 1-16, March.
    19. Zhen, Lu & Liang, Zhe & Zhuge, Dan & Lee, Loo Hay & Chew, Ek Peng, 2017. "Daily berth planning in a tidal port with channel flow control," Transportation Research Part B: Methodological, Elsevier, vol. 106(C), pages 193-217.
    20. Liu, Baoli & Li, Zhi-Chun & Sheng, Dian & Wang, Yadong, 2021. "Integrated planning of berth allocation and vessel sequencing in a seaport with one-way navigation channel," Transportation Research Part B: Methodological, Elsevier, vol. 143(C), pages 23-47.

    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:jsched:v:27:y:2024:i:1:d:10.1007_s10951-023-00791-9. 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.