  We present a first exact study on higher-dimensional packing problems with
order constraints. Problems of this type occur naturally in applications such
as logistics or computer architecture and can be interpreted as
higher-dimensional generalizations of scheduling problems. Using
graph-theoretic structures to describe feasible solutions, we develop a novel
exact branch-and-bound algorithm. This extends previous work by Fekete and
Schepers; a key tool is a new order-theoretic characterization of feasible
extensions of a partial order to a given complementarity graph that is
tailor-made for use in a branch-and-bound environment. The usefulness of our
approach is validated by computational results.
