  Motivated by distribution problems arising in the supply chain of Haleon, we
investigate a discrete optimization problem that we call the "container
delivery scheduling problem". The problem models a supplier dispatching ordered
products with shipping containers from manufacturing sites to distribution
centers, where orders are collected by the buyers at agreed due times. The
supplier may expedite or delay item deliveries to reduce transshipment costs at
the price of increasing inventory costs, as measured by the number of
containers and distribution center storage/backlog costs, respectively. The
goal is to compute a delivery schedule attaining good trade-offs between the
two. This container delivery scheduling problem is a temporal variant of
classic bin packing problems, where the item sizes are not fixed, but depend on
the item due times and delivery times. An approach for solving the problem
should specify a batching policy for container consolidation and a scheduling
policy for deciding when each container should be delivered. Based on the
available item due times, we develop algorithms with sequential and nested
batching policies as well as on-time and delay-tolerant scheduling policies. We
elaborate on the problem's hardness and substantiate the proposed algorithms
with positive and negative approximation bounds, including the derivation of an
algorithm achieving an asymptotically tight 2-approximation ratio.
