Zahlreiche in Industrie und Wirtschaft auftretende Fragestellungen lassen sich
als mehrdimensionale Packungsprobleme formulieren. Neben
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.
Die meisten dieser Fragestellungen fallen in die Kategorie der
orthogonalen Packungsprobleme. Dabei versucht man, eine Menge d-dimensionaler
massiver Quader in einem oder mehreren quaderförmigen Behältern
achsenparallel
,,möglichst günstig`` zu plazieren. So will man beim
orthogonalen Bin-Packing-Problem möglichst wenige Behälter verwenden, beim
orthogonalen Knapsackproblem den Gesamtwert der Güter in einem
Behälter maximieren oder
beim Strip-Packing-Problem die Höhe der Packung minimieren.
Diese Probleme sind als Verallgemeinerungen des eindimensionalen
Bin-Packing-Problems
NP-schwer im strengen Sinne. Dennoch vermittelt die
komplexitätstheoretische
Einordnung allein noch keinen Eindruck von ihrem immensen
Schwierigkeitsgrad.
Während man gegenwärtig für das
im weiteren Sinne
NP-schwere
eindimensionale Knapsackproblem Instanzen mit bis zu
250.000 Objekten exakt lösen kann, umfaßte die größte
bisher exakt gelöste Instanz des zweidimensionalen orthogonalen
Knapsackproblems
ganze 22 Objekte.
Zur Lösung praktischer Probleme werden daher heuristische Methoden eingesetzt.
In der Regel produzieren diese Verfahren zufriedenstellende Lösungen.
Entscheidend ist dabei allerdings, daß die zu packenden
Gegenstände wesentlich kleiner als die Behälter sind.
Beim Packen weniger sperriger Teile kann bereits ein einziges
ungünstig plaziertes
Objekt die Qualität der Gesamtlösung drastisch verschlechtern.
Daher ist es erforderlich, Instanzen mit wenigen sperrigen
Teilen exakt zu lösen.
