← Search

Production and Operations Management 2011

Container Scheduling: Complexity and Algorithms

Byung‐Cheon Choi1; Kangbok Lee2; Joseph Y.‐T. Leung3; Michael Pinedo4,5; Dirk Briskorn6,7

1 Chungnam National University · 2 Rutgers, The State University of New Jersey · 3 New Jersey Institute of Technology · 4 Management Sciences (United States) · 5 New York University · 6 Cologne Institute for Economic Research · 7 University of Cologne

Abstract

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.

DOI
10.1111/j.1937-5956.2011.01238.x
Sources
openalex

Cite