Container scheduling: Complexity and algorithms

Byung Cheon Choi, Kangbok Lee, Joseph Y.T. Leung, Michael L. Pinedo, Dirk Briskorn

Research output: Contribution to journalArticlepeer-review

16 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)115-128
Number of pages14
JournalProduction and Operations Management
Issue number1
StatePublished - Jan 2012

All Science Journal Classification (ASJC) codes

  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering
  • Management of Technology and Innovation


  • computational complexity
  • container allocation
  • liner shipping
  • on-time delivery
  • scheduling rules


Dive into the research topics of 'Container scheduling: Complexity and algorithms'. Together they form a unique fingerprint.

Cite this