Behälterproblem

Das Behälterproblem oder auch Bin Packing ist ein kombinatorisches Optimierungsproblem, das auf folgender Fragestellung basiert:

  • Gegeben: Eine Anzahl
    k \in \mathbb{N}
    von „Behältern“ (englisch bin) der Größe
    b \in \mathbb{N}
    und eine Anzahl
    n \in \mathbb{N}
    „Objekte“ mit den Gewichten (Größen)
     a_1,a_2,..,a_n\ \leq\ b
    .
  • Frage: Können die n „Objekte“ so auf die k „Behälter“ verteilt (packing) werden, dass keiner der „Behälter“ überläuft?
Formal:
 \exists\ f : \{1,..,n\} \to \{1,..,k\}\ \mbox{, so dass }\forall\ j := 1,..,k \quad \sum_{f(i)=j} a_i \leq b \mbox{  gilt ?}

Das oben beschriebene Entscheidungsproblem ist NP-vollständig; das zugehörige Optimierungsproblem – das Finden einer Zuordnung, bei der die Anzahl an Behältern minimiert wird – ist NP-schwer.

Die hier gegebene Formulierung des Bin-Packing-Problems ist nur die Motivation beziehungsweise Basis für eine Vielzahl weiterer Packing-Problems, die unter anderem in der Verpackungsindustrie eine große Rolle spielen.

Eine etwas allgemeiner formale Definition beschreibt das Bin-Packing-Problem als die Bestimmung einer Partition und Zuordnung einer Menge von Objekten, so dass eine bestimmte Bedingung erfüllt bzw. eine Zielfunktion minimiert oder maximiert wird.

Algorithmen

Da Bin-Packing ein NP-schweres Problem ist, ist es unmöglich große Instanzen exakt zu lösen. Johnsons Approximationsalgorithmus First Fit Decreasing löst das Problem in polynomieller Zeit mit einer scharfen asymptotischen Gütegarantie von 11 \over 9 (nicht asymptotisch beträgt die Gütegarantie 3 \over 2).

Sortiere die Objekte nach absteigendem Gewicht
Füge die Objekte der Reihe nach ein,
 sodass jedes in den ersten Behälter gegeben wird, in dem noch genug Platz ist.
 Falls in keinem der bereits geöffneten Behälter genügend Platz ist, öffne einen neuen.

Die Laufzeit beträgt O(n * log(n)) (sowohl für das Sortieren, als auch für das Einfügen). Die selben Resultate gelten auch für Best Fit Decreasing. Dabei wird ein Objekt nicht in den ersten Behälter eingefügt, in den es passt, sondern in den Behälter, in den es gerade noch passt (die Restkapazität wird also minimiert).

Wenn für jedes Objekt sofort entschieden werden muss, in welchen Behälter es kommt, spricht man von der Online-Variante des Bin-Packing-Problems. Dabei ist es also nicht möglich, die Objekte im Vorhinein nach Gewicht zu sortieren. Die Algorithmen First Fit und Best Fit arbeiten analog zu den oben genannten, jedoch ohne vorheriges Sortieren. Beide Algorithmen haben eine scharfe asymptotische Gütegarantie von 1.7 und eine Laufzeit von O(n * log(n)).

Der naive Algorithmus Next Fit packt die Objekte der Reihe nach in den letzten geöffneten Behälter, falls sie hineinpassen. Ansonsten wird der Behälter geschlossen, ein neuer geöffnet und das aktuelle Objekt in den leeren Behälter gegeben. Die asymptotische Gütegarantie beträgt 2, die Laufzeit O(n). Der Vorteil dieses naiven Algorithmus ist, dass immer nur ein Behälter gleichzeitig geöffnet ist (was in der praktischen Anwendung eine Bedingung sein kann).

Literatur

  • Bernhard Korte, Jens Vygen: Kombinatorische Optimierung. Springer, Berlin Heidelberg 2008, ISBN 978-3-540-76918-7, S. 485ff

Weblinks


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Cutting Stock Problem — Das eindimensionale Zuschnittproblem (engl. one dimensional cutting stock problem) ist ein schweres ganzzahliges lineares Optimierungsproblem mit dem Ziel, eindimensionale Teile in vorgegebenen Bedarfszahlen aus möglichst wenig Stücken Material… …   Deutsch Wikipedia

  • Zuschnittproblem — Das eindimensionale Zuschnittproblem (engl. one dimensional cutting stock problem) ist ein schweres ganzzahliges lineares Optimierungsproblem mit dem Ziel, eindimensionale Teile in vorgegebenen Bedarfszahlen aus möglichst wenig Stücken Material… …   Deutsch Wikipedia

  • Zuschnittsproblem — Das eindimensionale Zuschnittproblem (engl. one dimensional cutting stock problem) ist ein schweres ganzzahliges lineares Optimierungsproblem mit dem Ziel, eindimensionale Teile in vorgegebenen Bedarfszahlen aus möglichst wenig Stücken Material… …   Deutsch Wikipedia

  • BIN PACKING — Das Behälterproblem oder auch Bin Packing ist ein kombinatorisches Optimierungsproblem, das auf folgender Fragestellung basiert: Gegeben: Eine Anzahl von „Behältern“ (englisch bin) der Größe und eine Anzahl „Objekte“ mit den Größen …   Deutsch Wikipedia

  • Bin-Packing — Das Behälterproblem oder auch Bin Packing ist ein kombinatorisches Optimierungsproblem, das auf folgender Fragestellung basiert: Gegeben: Eine Anzahl von „Behältern“ (englisch bin) der Größe und eine Anzahl „Objekte“ mit den Größen …   Deutsch Wikipedia

  • Bin-Packing-Problem — Das Behälterproblem oder auch Bin Packing ist ein kombinatorisches Optimierungsproblem, das auf folgender Fragestellung basiert: Gegeben: Eine Anzahl von „Behältern“ (englisch bin) der Größe und eine Anzahl „Objekte“ mit den Größen …   Deutsch Wikipedia

  • Bin-packing — Das Behälterproblem oder auch Bin Packing ist ein kombinatorisches Optimierungsproblem, das auf folgender Fragestellung basiert: Gegeben: Eine Anzahl von „Behältern“ (englisch bin) der Größe und eine Anzahl „Objekte“ mit den Größen …   Deutsch Wikipedia

  • Bin Packing Problem — Das Behälterproblem oder auch Bin Packing ist ein kombinatorisches Optimierungsproblem, das auf folgender Fragestellung basiert: Gegeben: Eine Anzahl von „Behältern“ (englisch bin) der Größe und eine Anzahl „Objekte“ mit den Größen …   Deutsch Wikipedia

  • Eimerproblem — Das Behälterproblem oder auch Bin Packing ist ein kombinatorisches Optimierungsproblem, das auf folgender Fragestellung basiert: Gegeben: Eine Anzahl von „Behältern“ (englisch bin) der Größe und eine Anzahl „Objekte“ mit den Größen …   Deutsch Wikipedia

  • Eindimensionales Zuschnittproblem — Das eindimensionale Zuschnittproblem (engl. one dimensional cutting stock problem) ist ein schweres ganzzahliges lineares Optimierungsproblem mit dem Ziel, eindimensionale Teile in vorgegebenen Bedarfszahlen aus möglichst wenig Stücken Material… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”