© Jakub Wróblewski     (jeśli nie zaznaczono inaczej)

Problem pakowania (bin packing)

Sformułowanie problemu: Danych jest n obiektów, każdy o pewnym rozmiarze wi. Dana jest też dowolnie duża liczba skrzyń, z których każda ma ustaloną pojemność W. Zadanie: umieścić wszystkie n obiektów w skrzyniach w ten sposób, by nie przekroczyć ich pojemności (tzn. by suma wielkości wi obiektów przypisanych jednej skrzyni była nie większa, niż W), przy czym należy w tym celu użyć możliwie małej liczby skrzyń.

Przykład: obiekty 25, 23, 75, 58, 17 umieszczamy w dwóch skrzyniach wielkości 100 w następujący sposób: (75, 23), (58, 25, 17).

Problem ten jest NP-trudny, ale dość dobrze aproksymowalny.

W poniższej tabeli zebrałem przykładowe problemy wraz z najlepszymi wynikami, jakie znalazłem w literaturze. W nawiasie kwadratowym podałem teoretyczne minimum, o ile jest znane, lub oszacowanie wynikające np. z sumy wielkości obiektów i wielkości pojedynczej skrzyni. Tabela "Alg. zachłanny" podaje wynik zastosowania prostej, choć dosyć skutecznej heurystyki: sortujemy obiekty malejąco, po czym w tej kolejności próbujemy je umieszczać w kolejnych skrzyniach. Ostatecznie umieszczamy obiekt w pierwszej skrzyni, w której się zmieści.

Nazwa plikuLiczba obiektówAlg. zachłannyMin. znane rozw. [optimum]Uwagi
u120_08.txt1205150 [50]Źródło danych: strona J.E. Bearsley'a
Rozkład jednostajny 0-100, skrzynia: 150
u120_19.txt1205049 [49]j.w.
u250_07.txt250105104 [103-104]j.w.
u250_12.txt250107106 [105-106]j.w.
u250_13.txt250104103 [102-103]j.w.
HARD0.BPP2005956 [55-56]Źródło danych: Technische Universität Darmstadt (Data set 3)
Rozkład jednostajny 20000-35000, skrzynia: 100000
HARD1.BPP2006057 [56-57]j.w.
HARD2.BPP2006056 [56]j.w.
HARD3.BPP2005955 [55]j.w.
HARD4.BPP2006057 [56-57]j.w.
HARD5.BPP2005956 [55-56]j.w.
HARD6.BPP2006057 [56-57]j.w.
HARD7.BPP2005955 [54-55]j.w.
HARD8.BPP2006057 [56-57]j.w.
HARD9.BPP2006056 [56]j.w.
N4C3W4_T.BPP500220217 [215-217]j.w., Data set 1
Rozkład jednostajny 30-100, skrzynia: 150
N3C3W4_L.BPP2009290 [88-90]j.w.
N4W2B1R5.BPP500111103 [102-103]j.w., Data set 2
Rozkład jednostajny 160-240, skrzynia: 1000
Large.txt400001026110006 [>=9997]Dane autora.
Rozkład nierównomierny na 3000-7000
z silnym maksimum wokół 5000 (odch. std. 750), skrzynia: 20000

Archiwum z powyższymi zbiorami danych. Format danych: pierwsze dwie liczby całkowite oznaczają odpowiednio wielkość skrzyni i liczbę obiektów w pliku, kolejne liczby to wielkości poszczególnych obiektów (również liczby całkowite).


Literatura

  • T.H. Cormen, C.E. Leiserson, R.L. Rivest. Wprowadzenie do algorytmów. WNT, Warszawa 1997. Problem 37-1.
  • P. Crescenzi, V. Kann (red.). A compendium of NP optimization problems.
  • E.G. Coffman Jr, M.R. Garey, D.S. Johnson (1997). Approximation algorithms for bin-packing - a survey. Approximation Algorithms for NP-hard Problems, PWS Publishing Company, Boston, 46-93.

Aktualizacja: 2002

- - - - - - - -