direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Preprints 2000

More-Dimensional Packing with Order Constraints
Zitatschlüssel Report-698-2000
Autor Sándor P. Fekete and Ekkehard Köhler and Jürgen Teich
Jahr 2000
Nummer 698
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung We consider the optimal placementent 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.
Typ der Publikation Preprint
Link zur Publikation Download Bibtex Eintrag