More-Dimensional Packing with Order Constraints
| dc.contributor.author | Fekete, Sándor P. | |
| dc.contributor.author | Köhler, Ekkehard | |
| dc.contributor.author | Teich, Jürgen | |
| dc.date.accessioned | 2021-12-17T10:17:25Z | |
| dc.date.available | 2021-12-17T10:17:25Z | |
| dc.date.issued | 2000 | |
| dc.description.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. | en |
| dc.identifier.issn | 2197-8085 | |
| dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/15951 | |
| dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-14724 | |
| dc.language.iso | en | en |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
| dc.subject.ddc | 510 Mathematik | en |
| dc.subject.other | scheduling | en |
| dc.subject.other | more-dimensional packing | en |
| dc.subject.other | precedence constraints | en |
| dc.subject.other | exact algorithms | en |
| dc.subject.other | interval graphs | en |
| dc.subject.other | partial orders | en |
| dc.title | More-Dimensional Packing with Order Constraints | en |
| dc.type | Research Paper | en |
| dc.type.version | submittedVersion | en |
| tub.accessrights.dnb | free | en |
| tub.affiliation | Fak. 2 Mathematik und Naturwissenschaften::Inst. Mathematik | de |
| tub.affiliation.faculty | Fak. 2 Mathematik und Naturwissenschaften | de |
| tub.affiliation.institute | Inst. Mathematik | de |
| tub.publisher.universityorinstitution | Technische Universität Berlin | en |
| tub.series.issuenumber | 2000, 698 | en |
| tub.series.name | Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin | en |
| tub.subject.msc2000 | 90C27 Combinatorial optimization | en |
| tub.subject.msc2000 | 68R10 Graph theory | en |