Approximation Algorithm for Quay Crane Scheduling with Noncrossing Constraints in Container Port Terminals

The quay crane scheduling problem studied in this paper is to determine a handling sequence of ship bays for quay cranes assigned to a container ship considering the non-crossing constraints between quay cranes. This paper provides a mixed integer programming model for the considered quay crane scheduling problem that is NP-complete in nature. An approximation algorithm is proposed to obtain near optimal solution. Worst-case analysis for the approximation algorithm is performed and computational experiments are conducted to examine the proposed model and solution algorithm. The computational results show that the proposed approximation algorithm is effective and efficient in solving the considered quay crane scheduling problem.

• Corporate Authors:

  Transportation Research Board

  500 Fifth Street, NW
  Washington, DC  United States  20001
• Authors:
  • Lee, Der-Horng
  • Wang, Huiqiu
  • Shon, Zhengyi
• Conference:
  • Transportation Research Board 87th Annual Meeting
  • Location: Washington DC, United States
  • Date: 2008-1-13 to 2008-1-17
• Date: 2008

Language

• English

Media Info

• Media Type: DVD
• Features: Figures; References; Tables;
• Pagination: 13p
• Monograph Title: TRB 87th Annual Meeting Compendium of Papers DVD

Subject/Index Terms

• TRT Terms: Algorithms; Container terminals; Cranes; Freight traffic; Mathematical models; Mixed integer programming; Scheduling
• Subject Areas: Freight Transportation; Marine Transportation; Terminals and Facilities;

Filing Info

• Accession Number: 01089451
• Record Type: Publication
• Report/Paper Numbers: 08-0367
• Files: BTRIS, TRIS, TRB
• Created Date: Feb 28 2008 9:08AM