Inhalt des Dokuments
Preprint 698-2000
Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)- Title
- More-Dimensional Packing with Order Constraints
- Authors
- Sándor P. Fekete, Ekkehard Köhler, and Jürgen Teich
- Classification
-
MSC: primary: 90C27 Combinatorial optimization secondary: 68R10 Graph theory - Keywords
-
scheduling, more-dimensional packing, precedence constraints, exact algorithms, interval graphs, partial orders.
- Abstract
-
We present a first systematic study on more-dimensional packing problems with order constraints. Problems of this type occur naturally in applications such as logistics or computer architecture. They can be interpreted as more-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.
- Source
Zusatzinformationen / Extras
Direktzugang
Schnellnavigation zur Seite über Nummerneingabe