IDEAS home Printed from https://ideas.repec.org/a/eee/transb/v181y2024ics0191261524000171.html
   My bibliography  Save this article

The dry dock scheduling problem

Author

Listed:
  • Jia, Shuai
  • Li, Chung-Lun
  • Meng, Qiang

Abstract

Dry docks are essential facilities for ship maintenance and thus are critical assets of a shipyard. In this paper, we study a dry dock scheduling problem that arises from shipyard operations and management. The problem involves decisions on assigning ships to a set of dry docks and sequencing the ships in each dry dock, subject to complicated but realistic operational constraints such as parallel ship service, sequence-dependent setup times, and compatibility between ships and dry docks, to minimize the total departure tardiness cost of ships. Because accurate ship service times are not available until ships have been mounted on the placing blocks of dry docks and have undergone detailed inspections, the uncertainty of ship service times should be taken into account in dry dock scheduling. The structure of the problem enables us to develop a two-stage robust optimization model to capture ship service time uncertainty. We show that given the first-stage decisions, i.e., ship assignment and sequencing, the optimal second-stage decisions, i.e., the service start times, setup times, service times, and departure tardiness of the ships in the worst-case scenario, can be obtained by a dynamic programming algorithm that runs in pseudo-polynomial time. We incorporate this dynamic programming algorithm into an iterative solution method to generate an optimal solution to the two-stage robust optimization model. Through computational experiments on problem instances generated from the operational data of a shipyard in Singapore, we show that the robust optimization approach ensures the shipyard operator’s resilience against uncertain ship service times and significantly outperforms the current practice for dry dock scheduling.

Suggested Citation

  • Jia, Shuai & Li, Chung-Lun & Meng, Qiang, 2024. "The dry dock scheduling problem," Transportation Research Part B: Methodological, Elsevier, vol. 181(C).
  • Handle: RePEc:eee:transb:v:181:y:2024:i:c:s0191261524000171
    DOI: 10.1016/j.trb.2024.102893
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0191261524000171
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.trb.2024.102893?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. 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.
    2. Rodrigues, Filipe & Agra, Agostinho, 2021. "An exact robust approach for the integrated berth allocation and quay crane scheduling problem under uncertain arrival times," European Journal of Operational Research, Elsevier, vol. 295(2), pages 499-516.
    3. 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.
    4. Chung‐Yee Lee & Shengnan Shu & Zhou Xu, 2021. "Optimal Global Liner Service Procurement by Utilizing Liner Service Schedules," Production and Operations Management, Production and Operations Management Society, vol. 30(3), pages 703-714, March.
    5. 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.
    6. Alper Atamtürk & Muhong Zhang, 2007. "Two-Stage Robust Network Flow and Design Under Demand Uncertainty," Operations Research, INFORMS, vol. 55(4), pages 662-673, August.
    7. Neyshabouri, Saba & Berg, Bjorn P., 2017. "Two-stage robust optimization approach to elective surgery and downstream capacity planning," European Journal of Operational Research, Elsevier, vol. 260(1), pages 21-40.
    8. Amir Hossein Gharehgozli & Debjit Roy & René de Koster, 2016. "Sea container terminals: New technologies and OR models," Maritime Economics & Logistics, Palgrave Macmillan;International Association of Maritime Economists (IAME), vol. 18(2), pages 103-140, June.
    9. Oğuz Solyalı & Jean-François Cordeau & Gilbert Laporte, 2016. "The Impact of Modeling on Robust Inventory Management Under Demand Uncertainty," Management Science, INFORMS, vol. 62(4), pages 1188-1201, April.
    10. Chung-Yee Lee & Reha Uzsoy & Louis A. Martin-Vega, 1992. "Efficient Algorithms for Scheduling Semiconductor Burn-In Operations," Operations Research, INFORMS, vol. 40(4), pages 764-775, August.
    11. Fanwen Meng & Jin Qi & Meilin Zhang & James Ang & Singfat Chu & Melvyn Sim, 2015. "A Robust Optimization Model for Managing Elective Admission in a Public Hospital," Operations Research, INFORMS, vol. 63(6), pages 1452-1467, December.
    12. Fowler, John W. & Mönch, Lars, 2022. "A survey of scheduling with parallel batch (p-batch) processing," European Journal of Operational Research, Elsevier, vol. 298(1), pages 1-24.
    13. Yun Fong Lim & Chen Wang, 2017. "Inventory Management Based on Target-Oriented Robust Optimization," Management Science, INFORMS, vol. 63(12), pages 4409-4427, December.
    14. Mengshi Lu & Zuo‐Jun Max Shen, 2021. "A Review of Robust Operations Management under Model Uncertainty," Production and Operations Management, Production and Operations Management Society, vol. 30(6), pages 1927-1943, June.
    15. Jia, Shuai & Li, Chung-Lun & Xu, Zhou, 2020. "A simulation optimization method for deep-sea vessel berth planning and feeder arrival scheduling at a container port," Transportation Research Part B: Methodological, Elsevier, vol. 142(C), pages 174-196.
    16. Zhen, Lu, 2015. "Tactical berth allocation under uncertainty," European Journal of Operational Research, Elsevier, vol. 247(3), pages 928-944.
    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. 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. Li, Shuqin & Jia, Shuai & Tao, Yi & Lin, Xudong, 2024. "Gate appointment design in a container terminal: A robust optimization approach," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 184(C).
    3. 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).
    4. Xiang, Xi & Liu, Changchun, 2021. "An almost robust optimization model for integrated berth allocation and quay crane assignment problem," Omega, Elsevier, vol. 104(C).
    5. Shaojian Qu & Xinqi Li & Chang Liu & Xufeng Tang & Zhisheng Peng & Ying Ji, 2023. "Two-Stage Robust Programming Modeling for Continuous Berth Allocation with Uncertain Vessel Arrival Time," Sustainability, MDPI, vol. 15(13), pages 1-30, July.
    6. Raeesi, Ramin & Sahebjamnia, Navid & Mansouri, S. Afshin, 2023. "The synergistic effect of operational research and big data analytics in greening container terminal operations: A review and future directions," European Journal of Operational Research, Elsevier, vol. 310(3), pages 943-973.
    7. 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.
    8. Jia, Shuai & Li, Chung-Lun & Xu, Zhou, 2020. "A simulation optimization method for deep-sea vessel berth planning and feeder arrival scheduling at a container port," Transportation Research Part B: Methodological, Elsevier, vol. 142(C), pages 174-196.
    9. Guo, Liming & Zheng, Jianfeng & Du, Haoming & Du, Jian & Zhu, Zhihong, 2022. "The berth assignment and allocation problem considering cooperative liner carriers," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 164(C).
    10. 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.
    11. Kai Wang & Lu Zhen & Shuaian Wang, 2018. "Column Generation for the Integrated Berth Allocation, Quay Crane Assignment, and Yard Assignment Problem," Transportation Science, INFORMS, vol. 52(4), pages 812-834, August.
    12. Agra, Agostinho & Rodrigues, Filipe, 2022. "Distributionally robust optimization for the berth allocation problem under uncertainty," Transportation Research Part B: Methodological, Elsevier, vol. 164(C), pages 1-24.
    13. Guo, Liming & Zheng, Jianfeng & Liang, Jinpeng & Wang, Shuaian, 2023. "Column generation for the multi-port berth allocation problem with port cooperation stability," Transportation Research Part B: Methodological, Elsevier, vol. 171(C), pages 3-28.
    14. 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.
    15. Wawrzyniak, Jakub & Drozdowski, Maciej & Sanlaville, Éric, 2020. "Selecting algorithms for large berth allocation problems," European Journal of Operational Research, Elsevier, vol. 283(3), pages 844-862.
    16. Kastner, Marvin & Kämmerling, Nicolas & Jahn, Carlos & Clausen, Uwe, 2020. "Equipment selection and layout planning - Literature overview and research directions," Chapters from the Proceedings of the Hamburg International Conference of Logistics (HICL), in: Jahn, Carlos & Kersten, Wolfgang & Ringle, Christian M. (ed.), Data Science in Maritime and City Logistics: Data-driven Solutions for Logistics and Sustainability. Proceedings of the Hamburg International Conferen, volume 30, pages 485-519, Hamburg University of Technology (TUHH), Institute of Business Logistics and General Management.
    17. 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.
    18. Rodrigues, Filipe & Agra, Agostinho, 2021. "An exact robust approach for the integrated berth allocation and quay crane scheduling problem under uncertain arrival times," European Journal of Operational Research, Elsevier, vol. 295(2), pages 499-516.
    19. Haolin Ruan & Zhi Chen & Chin Pang Ho, 2023. "Adjustable Distributionally Robust Optimization with Infinitely Constrained Ambiguity Sets," INFORMS Journal on Computing, INFORMS, vol. 35(5), pages 1002-1023, September.
    20. Damla Kizilay & Deniz Türsel Eliiyi, 2021. "A comprehensive review of quay crane scheduling, yard operations and integrations thereof in container terminals," Flexible Services and Manufacturing Journal, Springer, vol. 33(1), pages 1-42, March.

    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:transb:v:181:y:2024:i:c:s0191261524000171. 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/wps/find/journaldescription.cws_home/548/description#description .

    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.