Jakub Wróblewski > Materiały dodatkowe > Problem pakowania (bin packing)

Problem pakowania (bin packing)

Sformułowanie problemu: Danych jest n obiektów, każdy o pewnym rozmiarze w_i. 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 w_i 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 pliku	Liczba obiektów	Alg. zachłanny	Min. znane rozw. [optimum]	Uwagi
u120_08.txt	120	51	50 [50]	Źródło danych: strona J.E. Bearsley'a Rozkład jednostajny 0-100, skrzynia: 150
u120_19.txt	120	50	49 [49]	j.w.
u250_07.txt	250	105	104 [103-104]	j.w.
u250_12.txt	250	107	106 [105-106]	j.w.
u250_13.txt	250	104	103 [102-103]	j.w.
HARD0.BPP	200	59	56 [55-56]	Źródło danych: Technische Universität Darmstadt (Data set 3) Rozkład jednostajny 20000-35000, skrzynia: 100000
HARD1.BPP	200	60	57 [56-57]	j.w.
HARD2.BPP	200	60	56 [56]	j.w.
HARD3.BPP	200	59	55 [55]	j.w.
HARD4.BPP	200	60	57 [56-57]	j.w.
HARD5.BPP	200	59	56 [55-56]	j.w.
HARD6.BPP	200	60	57 [56-57]	j.w.
HARD7.BPP	200	59	55 [54-55]	j.w.
HARD8.BPP	200	60	57 [56-57]	j.w.
HARD9.BPP	200	60	56 [56]	j.w.
N4C3W4_T.BPP	500	220	217 [215-217]	j.w., Data set 1 Rozkład jednostajny 30-100, skrzynia: 150
N3C3W4_L.BPP	200	92	90 [88-90]	j.w.
N4W2B1R5.BPP	500	111	103 [102-103]	j.w., Data set 2 Rozkład jednostajny 160-240, skrzynia: 1000
Large.txt	40000	10261	10006 [>=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.

Autor strony: Jakub Wróblewski