Container Scheduling: Complexity and Algorithms

• 成果类型: Article
• 署名作者: Choi, Byung-Cheon; Lee, Kangbok; Leung, Joseph Y. -T.; Pinedo, Michael L.; Briskorn, Dirk
• 署名单位: Chungnam National University; Rutgers University System; Rutgers University Newark; Rutgers University New Brunswick; New Jersey Institute of Technology; New York University; University of Cologne
• 刊物名称: PRODUCTION AND OPERATIONS MANAGEMENT
• ISSN/ISSBN: 1059-1478
• DOI: 10.1111/j.1937-5956.2011.01238.x
• 发表日期: 2012
• 页码: 115-128
• 关键词: liner shipping; container allocation; on-time delivery; scheduling rules; computational complexity

摘要

We consider the transport of containers through a fleet of ships. Each ship has a capacity constraint limiting the total number of containers it can carry and each ship visits a given set of ports following a predetermined route. Each container has a release date at its origination port, and a due date at its destination port. A container has a size 1 or size 2; size 1 represents a 1 TEU (20-foot equivalent unit) and size 2 represents 2 TEUs. The delivery time of a container is defined as the time when the ship that carries the container arrives at its destination port. We consider the problem of minimizing the maximum tardiness over all containers. We consider three scenarios with regard to the routes of the ships, namely, the ships having (i) identical, (ii) nested, and (iii) arbitrary routes. For each scenario, we consider different settings for origination ports, release dates, sizes of containers, and number of ports; we determine the computational complexity of various cases. We also provide a simple heuristic for some cases, with its worst case analysis. Finally, we discuss the relationship of our problems with other scheduling problems that are known to be open.