A Decomposition Method for the Group-Based Quay Crane Scheduling Problem

Defeng Sun (), Lixin Tang (), Roberto Baldacci () and Zihan Chen ()
Additional contact information
Defeng Sun: National Frontiers Science Center for Industrial Intelligence and Systems Optimization, Northeastern University, Shenyang 110819, China; Key Laboratory of Data Analytics and Optimization for Smart Industry (Northeastern University), Ministry of Education, Shenyang 110819, China
Lixin Tang: National Frontiers Science Center for Industrial Intelligence and Systems Optimization, Northeastern University, Shenyang 110819, China
Roberto Baldacci: Division of Engineering Management and Decision Sciences, College of Science and Engineering, Hamad Bin Khalifa University, Qatar Foundation, Doha 34110, Qatar
Zihan Chen: Huawei Cloud Computing Technologies Co., Ltd., Beijing 100085, China

INFORMS Journal on Computing, 2024, vol. 36, issue 2, 543-570

Abstract: This study addresses the quay crane scheduling problem (QCSP), which involves scheduling a fixed number of quay cranes to load and unload containers from ships in a maritime container terminal. The objective is to minimize the completion time while adhering to precedence, safety margin, and noncrossing constraints. Efficient scheduling of quay cranes plays a crucial role in reducing the time vessels spend at terminals. To solve the QCSP, we explore different schedule directions for the quay cranes. Specifically, we consider three directions: unidirectional, where the quay cranes maintain a consistent movement direction from upper to lower bays or vice versa after initial repositioning; bidirectional, allowing the cranes to change direction once during operations; and multidirectional, permitting freely changing movement direction during operations. For the bidirectional QCSP, we propose a new compact mathematical formulation. To obtain valid lower bounds on the optimal completion time, we derive various relaxations of this new formulation based on the different schedule directions. Our solution framework employs logic-based Benders decomposition, decomposing the problem into an assignment master problem and operation-sequence slave subproblems. Extensive computational experiments using benchmark instances from existing literature and newly generated instances validate the efficiency and effectiveness of the lower bounds and the exact solution approach.

Keywords: container terminal operations; multi-directional quay crane scheduling; logic-based Benders decomposition; branch-and-cut (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2022.0298 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:36:y:2024:i:2:p:543-570

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().