Das d-dimensionale Vektorpackproblem (d-VPP), welches aus Planungsaufgaben resultieren kann, ist eine Verallgemeinerung des eindimensionalen Zuschnittproblems (1CSP) und deshalb NP-schwer. Die stetige Relaxation, die mittels Spaltengenerierung gelöst werden kann, ergebe den optimalen Zielfunktionswert zC, während der optimale Zielfunktionswert der ganzzahligen Aufgabe zD ist. In der Dissertation werden obere Schranken für das Gap Δ = zD-zC hergeleitet und systematisch Instanzen des 1CSPs mit großem Δ (bis zu 6/5) konstruiert. Die im Teilbarkeitsfall des 1CSPs bekannte Abschätzung Δ < 2 wird zu Δ < 7/5 verschärft. Im d-VPP mit d > 1 gilt die MIRUP-Hypothese Δ < 2 nicht. Dies und die Unbeschränktheit des Wertes einer Variante bei d gegen unendlich werden an speziellen Beispielen gezeigt. Außerdem wird eine Heuristik vorgeschlagen und erprobt.
| Identifer | oai:union.ndltd.org:DRESDEN/oai:qucosa:de:qucosa:22443 |
| Date | 18 December 2003 |
| Creators | Rietz, Jürgen |
| Contributors | Terno, Johannes, Scheithauer, Guntram, Dempe, Stephan, Althöfer, Ingo, Fischer, Andreas, TU Bergakademie Freiberg |
| Source Sets | Hochschulschriftenserver (HSSS) der SLUB Dresden |
| Language | German |
| Detected Language | German |
| Type | doc-type:doctoralThesis, info:eu-repo/semantics/doctoralThesis, doc-type:Text |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0022 seconds