IDEAS home Printed from https://ideas.repec.org/a/pal/jorsoc/v62y2011i7d10.1057_jors.2010.54.html
   My bibliography  Save this article

Berth and quay crane allocation: a moldable task scheduling model

Author

Listed:
  • J Blazewicz

    (Institute of Computing Science, Poznan University of Technology)

  • T C E Cheng

    (The Hong Kong Polytechnic University, Hong Kong SAR)

  • M Machowiak

    (Institute of Computing Science, Poznan University of Technology)

  • C Oguz

    (Koç University)

Abstract

We study the problem of allocating berths to incoming ships and assigning the necessary quay cranes to the ships at a port container terminal. We formulate the problem as the moldable task scheduling problem by considering the tasks as ships and processors as quay cranes assigned to the ships based on the observation that the berthing duration of a ship depends on the number of quay cranes allocated to it. In the model, the processing speed of a task is considered to be a non-linear function of the number of processors allocated to it. We present a suboptimal algorithm that obtains a feasible solution to the discrete version of the problem from the continuous version, that is, where the tasks may require fractional quantities of the resources. We conducted computational experiments to evaluate the performance of the algorithm. The computational results show that the average behaviour of the algorithm is very good.

Suggested Citation

  • J Blazewicz & T C E Cheng & M Machowiak & C Oguz, 2011. "Berth and quay crane allocation: a moldable task scheduling model," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(7), pages 1189-1197, July.
    • Handle: RePEc:pal:jorsoc:v:62:y:2011:i:7:d:10.1057_jors.2010.54
    DOI: 10.1057/jors.2010.54
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1057/jors.2010.54
    File Function: Abstract
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1057/jors.2010.54?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. Imai, Akio & Chen, Hsieh Chia & Nishimura, Etsuko & Papadimitriou, Stratos, 2008. "The simultaneous berth and quay crane allocation problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 44(5), pages 900-920, September.
    2. Imai, Akio & Nishimura, Etsuko & Papadimitriou, Stratos, 2001. "The dynamic berth allocation problem for a container port," Transportation Research Part B: Methodological, Elsevier, vol. 35(4), pages 401-417, May.
    3. Hansen, Pierre & Oguz, Ceyda & Mladenovic, Nenad, 2008. "Variable neighborhood search for minimum cost berth allocation," European Journal of Operational Research, Elsevier, vol. 191(3), pages 636-649, December.
    4. Vis, Iris F. A. & de Koster, Rene, 2003. "Transshipment of containers at a container terminal: An overview," European Journal of Operational Research, Elsevier, vol. 147(1), pages 1-16, May.
    5. Jiyin Liu & Yat‐wah Wan & Lei Wang, 2006. "Quay crane scheduling at container terminals to minimize the maximum relative tardiness of vessel departures," Naval Research Logistics (NRL), John Wiley & Sons, vol. 53(1), pages 60-74, February.
    6. Andrew Lim & Brian Rodrigues & Zhou Xu, 2007. "A m‐parallel crane scheduling problem with a non‐crossing constraint," Naval Research Logistics (NRL), John Wiley & Sons, vol. 54(2), pages 115-127, March.
    7. Jean-François Cordeau & Gilbert Laporte & Pasquale Legato & Luigi Moccia, 2005. "Models and Tabu Search Heuristics for the Berth-Allocation Problem," Transportation Science, INFORMS, vol. 39(4), pages 526-538, November.
    8. Jacek Błażewicz & Maciej Machowiak & Jan Węglarz & Mikhail Kovalyov & Denis Trystram, 2004. "Scheduling Malleable Tasks on Parallel Processors to Minimize the Makespan," Annals of Operations Research, Springer, vol. 129(1), pages 65-80, July.
    9. Hansen, Pierre & Mladenovic, Nenad & Moreno Pérez, Jos´e A., 2008. "Variable neighborhood search," European Journal of Operational Research, Elsevier, vol. 191(3), pages 593-595, December.
    10. Daganzo, Carlos F., 1989. "The crane scheduling problem," Transportation Research Part B: Methodological, Elsevier, vol. 23(3), pages 159-175, June.
    11. Peterkofsky, Roy I. & Daganzo, Carlos F., 1990. "A branch and bound solution method for the crane scheduling problem," Transportation Research Part B: Methodological, Elsevier, vol. 24(3), pages 159-172, June.
    12. Meisel, Frank & Bierwirth, Christian, 2009. "Heuristics for the integration of crane productivity in the berth allocation problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 45(1), pages 196-209, January.
    13. Imai, Akio & Nishimura, Etsuko & Papadimitriou, Stratos, 2003. "Berth allocation with service priority," Transportation Research Part B: Methodological, Elsevier, vol. 37(5), pages 437-457, June.
    14. Luigi Moccia & Jean‐François Cordeau & Manlio Gaudioso & Gilbert Laporte, 2006. "A branch‐and‐cut algorithm for the quay crane scheduling problem in a container terminal," Naval Research Logistics (NRL), John Wiley & Sons, vol. 53(1), pages 45-59, February.
    15. K T Park & K H Kim, 2002. "Berth scheduling for container terminals by using a sub-gradient optimization technique," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 53(9), pages 1054-1062, September.
    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. Correcher, Juan F. & Alvarez-Valdes, Ramon & Tamarit, Jose M., 2019. "New exact methods for the time-invariant berth allocation and quay crane assignment problem," European Journal of Operational Research, Elsevier, vol. 275(1), pages 80-92.
    2. 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.
    3. Xu, Dongsheng & Li, Chung-Lun & Leung, Joseph Y.-T., 2012. "Berth allocation with time-dependent physical limitations on vessels," European Journal of Operational Research, Elsevier, vol. 216(1), pages 47-56.
    4. Yong Wu & Wenkai Li & Matthew E. H. Petering & Mark Goh & Robert de Souza, 2015. "Scheduling Multiple Yard Cranes with Crane Interference and Safety Distance Requirement," Transportation Science, INFORMS, vol. 49(4), pages 990-1005, November.
    5. 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.
    6. Simon Emde & Hamid Abedinnia & Anne Lange & Christoph H. Glock, 2020. "Scheduling personnel for the build-up of unit load devices at an air cargo terminal with limited space," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 42(2), pages 397-426, June.
    7. Wu, Fangfang & Zhang, Xiandong & Chen, Bo, 2023. "An improved approximation algorithm for scheduling monotonic moldable tasks," European Journal of Operational Research, Elsevier, vol. 306(2), pages 567-578.
    8. Jiayin Pan & Yinfeng Xu & Guiqing Zhang, 2018. "Online integrated allocation of berths and quay cranes in container terminals with 1-lookahead," Journal of Combinatorial Optimization, Springer, vol. 36(2), pages 617-636, August.
    9. Giorgi Tadumadze & Simon Emde & Heiko Diefenbach, 2020. "Exact and heuristic algorithms for scheduling jobs with time windows on unrelated parallel machines," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 42(2), pages 461-497, June.
    10. Türkoğulları, Yavuz B. & Taşkın, Z. Caner & Aras, Necati & Altınel, İ. Kuban, 2014. "Optimal berth allocation and time-invariant quay crane assignment in container terminals," European Journal of Operational Research, Elsevier, vol. 235(1), pages 88-101.
    11. Fangfang Wu & Zhongyi Jiang & Run Zhang & Xiandong Zhang, 2023. "Approximation algorithms for scheduling monotonic moldable tasks on multiple platforms," Journal of Scheduling, Springer, vol. 26(4), pages 383-398, August.
    12. Dolgui, Alexandre & Kovalev, Sergey & Kovalyov, Mikhail Y. & Malyutin, Sergey & Soukhal, Ameur, 2018. "Optimal workforce assignment to operations of a paced assembly line," European Journal of Operational Research, Elsevier, vol. 264(1), pages 200-211.

    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. Bierwirth, Christian & Meisel, Frank, 2010. "A survey of berth allocation and quay crane scheduling problems in container terminals," European Journal of Operational Research, Elsevier, vol. 202(3), pages 615-627, May.
    2. Feng Li & Jiuh-Biing Sheu & Zi-You Gao, 2015. "Solving the Continuous Berth Allocation and Specific Quay Crane Assignment Problems with Quay Crane Coverage Range," Transportation Science, INFORMS, vol. 49(4), pages 968-989, November.
    3. Lu Zhen & Ek Peng Chew & Loo Hay Lee, 2011. "An Integrated Model for Berth Template and Yard Template Planning in Transshipment Hubs," Transportation Science, INFORMS, vol. 45(4), pages 483-504, November.
    4. Xu, Dongsheng & Li, Chung-Lun & Leung, Joseph Y.-T., 2012. "Berth allocation with time-dependent physical limitations on vessels," European Journal of Operational Research, Elsevier, vol. 216(1), pages 47-56.
    5. T. R. Lalita & G. S. R. Murthy, 2022. "Compact ILP formulations for a class of solutions to berth allocation and quay crane scheduling problems," OPSEARCH, Springer;Operational Research Society of India, vol. 59(1), pages 413-439, March.
    6. Zhen, Lu, 2015. "Tactical berth allocation under uncertainty," European Journal of Operational Research, Elsevier, vol. 247(3), pages 928-944.
    7. Lalla-Ruiz, Eduardo & Expósito-Izquierdo, Christopher & Melián-Batista, Belén & Moreno-Vega, J. Marcos, 2016. "A Set-Partitioning-based model for the Berth Allocation Problem under Time-Dependent Limitations," European Journal of Operational Research, Elsevier, vol. 250(3), pages 1001-1012.
    8. Changchun Liu & Xi Xiang & Li Zheng, 2020. "A two-stage robust optimization approach for the berth allocation problem under uncertainty," Flexible Services and Manufacturing Journal, Springer, vol. 32(2), pages 425-452, June.
    9. Zhen, Lu & Lee, Loo Hay & Chew, Ek Peng, 2011. "A decision model for berth allocation under uncertainty," European Journal of Operational Research, Elsevier, vol. 212(1), pages 54-68, July.
    10. 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.
    11. Hsien-Pin Hsu & Tai-Lin Chiang & Chia-Nan Wang & Hsin-Pin Fu & Chien-Chang Chou, 2019. "A Hybrid GA with Variable Quay Crane Assignment for Solving Berth Allocation Problem and Quay Crane Assignment Problem Simultaneously," Sustainability, MDPI, vol. 11(7), pages 1-21, April.
    12. Iris, Çağatay & Pacino, Dario & Ropke, Stefan, 2017. "Improved formulations and an Adaptive Large Neighborhood Search heuristic for the integrated berth allocation and quay crane assignment problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 105(C), pages 123-147.
    13. Frank Meisel & Christian Bierwirth, 2013. "A Framework for Integrated Berth Allocation and Crane Operations Planning in Seaport Container Terminals," Transportation Science, INFORMS, vol. 47(2), pages 131-147, May.
    14. Fanrui Xie & Tao Wu & Canrong Zhang, 2019. "A Branch-and-Price Algorithm for the Integrated Berth Allocation and Quay Crane Assignment Problem," Transportation Science, INFORMS, vol. 53(5), pages 1427-1454, September.
    15. Yongpei Guan & Kang-Hung Yang & Zhili Zhou, 2013. "The crane scheduling problem: models and solution approaches," Annals of Operations Research, Springer, vol. 203(1), pages 119-139, March.
    16. Changchun Liu & Xi Xiang & Li Zheng, 2017. "Two decision models for berth allocation problem under uncertainty considering service level," Flexible Services and Manufacturing Journal, Springer, vol. 29(3), pages 312-344, December.
    17. Ursavas, Evrim & Zhu, Stuart X., 2016. "Optimal policies for the berth allocation problem under stochastic nature," European Journal of Operational Research, Elsevier, vol. 255(2), pages 380-387.
    18. Robenek, Tomáš & Umang, Nitish & Bierlaire, Michel & Ropke, Stefan, 2014. "A branch-and-price algorithm to solve the integrated berth allocation and yard assignment problem in bulk ports," European Journal of Operational Research, Elsevier, vol. 235(2), pages 399-411.
    19. Giallombardo, Giovanni & Moccia, Luigi & Salani, Matteo & Vacca, Ilaria, 2010. "Modeling and solving the Tactical Berth Allocation Problem," Transportation Research Part B: Methodological, Elsevier, vol. 44(2), pages 232-245, February.
    20. 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).

    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:pal:jorsoc:v:62:y:2011:i:7:d:10.1057_jors.2010.54. 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.palgrave-journals.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.