Exakte Algorithmen für orthogonale Packungsprobleme

Schepers, Jörg (1997) Exakte Algorithmen für orthogonale Packungsprobleme. PhD thesis.

Abstract

Zahlreiche in Industrie und Wirtschaft auftretende Fragestellungen lassen sich als orthogonale Packungsprobleme formulieren. Dabei wird eine möglichst günstige Anordnung einer Menge zwei- oder dreidimensionaler massiver Quader in einem oder mehreren Behältern gesucht. Neben originär geometrischen Aufgaben wie dem Beladen von Paletten und Containern, dem Erstellen von Platinenlayouts oder dem Zuschnitt von Materialien (Cutting Stock Probleme) zählen hierzu auch Schedulingprobleme mit partitionierbaren Ressourcen. Heuristiken liefern nur dann zufriedenstellende Ergebnisse, wenn alle Maße der zu packenden Teile wesentlich kleiner als die des Containers sind. Bereits ein einziges ungünstig plaziertes sperriges Objekt kann die Qualität einer heuristischen Lösung bis hin zur Unbrauchbarkeit verschlechtern. Daher ist es erforderlich, Instanzen mit wenigen, sperrigen Teilen exakt zu lösen. Die in der Literatur beschriebenen exakten Verfahren beruhen auf ganzzahliger linearer Programmierung. Sie stoßen bereits bei sehr kleinen Instanzen an ihre Grenzen. In der vorliegenden Arbeiten präsentieren wir alternative Ansätze, die auf zwei neuartige Konzepte stützen: Eine Charakterisierung von Packungen mit Hilfe von Intervallgraphen. Die darin enthaltenen Symmetrien erlauben es, bei der Optimierung statt mit einzelnen Packungen mit ganzen Packmusterklassen zu operieren. Dabei ermöglicht die graphentheoretische Formulierung eine sehr kompakte Beschreibung und Speicherung geometrischer Zusammenhänge. Eine allgemeine Konstruktionsmethode für effektive und effizient berechenbare Relaxierungen und Schranken. Wir benutzen die aus der Performanceanalyse von Bin-Packing-Algorithmen bekannten dualzulässigen Funktionen, um Ersatzvolumina zu berechnen, die einen Teil des zwangsweise auftretenden Verschnitts miteinbeziehen. Numerische Resultate für zwei- und dreidimensionale Instanzen zeigen, daß damit erheblich größere Probleme als bisher exakt gelöst werden können.


Actions:
Download: [img] Postscript - Accepted Version
Download (906kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr97-302
Depositing User: Archive Admin
Date Deposited: 02 Apr 2001 00:00
Last Modified: 19 Dec 2011 09:45
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/302