Pakowanie dużej liczby pojemników

Pakowanie z dużą liczbą pojemników jest szczególnym przypadkiem problemu pakowania w pojemniki , w którym liczba różnych rozmiarów przedmiotów jest niewielka, podczas gdy liczba przedmiotów o każdym rozmiarze jest duża. Podczas gdy ogólny problem pakowania bin jest NP-trudny , ustawienie dużej krotności można rozwiązać w czasie wielomianowym, zakładając, że liczba różnych rozmiarów jest stałą stałą.

Definicja problemu

Dane wejściowe do problemu są dodatnimi liczbami całkowitymi:

• d - liczba różnych rozmiarów (nazywana też wymiarem problemu );
• B - pojemność pojemnika.
• s ₁ , ..., s _d - rozmiary. Wektor rozmiarów jest oznaczony przez s .
• n ₁ , ..., n _d - krotności; n _i to liczba elementów o rozmiarze s _i . Wektor krotności jest oznaczony przez n .
  • n oznacza całkowitą liczbę elementów, czyli n = n ₁ +...+ n _d .
  • V oznacza największą liczbę całkowitą występującą w opisie problemu, czyli V = max( s ₁ , ..., s _d , n ₁ , ..., n _d , B)

Wyjściem jest pakowanie - przypisanie elementów do pojemników, tak aby całkowity rozmiar elementów w każdym pojemniku wynosił co najwyżej B , przy czym liczba pojemników jest jak najmniejsza.

Przykład : załóżmy, że d = 2, s ₁ = 30, s ₂ = 40, n ₁ = n ₂ = 5, B = 120. Jest więc n = 10 elementów o rozmiarach: 30,30,30,30,30,40,40,40,40,40. Wtedy możliwe opakowanie to: {30,30,30,30}, {40,40,40}, {30,40,40}, które wykorzystuje 3 pojemniki.

Konfiguracje

Konfiguracja to zestaw elementów, które można zmieścić w jednym pojemniku . Może być reprezentowany przez wektor d liczb całkowitych, oznaczający wielokrotności różnych rozmiarów w konfiguracji. Formalnie dla każdej konfiguracji c definiujemy wektor całkowity a _c = a _c,1 , ..., a _{c, d} taki, że a _c ≤ n oraz a _c · s ≤ B.

W powyższym przykładzie jedną z konfiguracji jest c ={30,40,40}, ponieważ 1*30+2*40 ≤ 120. Odpowiadający jej wektor to _c = (1,2). Inne wektory konfiguracji to (4,0), (3,0), (2,0), (2,1), (1,0), (1,1), (1,2), (0,1 ), (0,2), (0,3). Gdybyśmy mieli tylko trzy pozycje o rozmiarze 3, to nie moglibyśmy użyć konfiguracji (4,0).

Problem można przedstawić za pomocą konfiguracyjnego programu liniowego : dla każdej konfiguracji c istnieje zmienna x _c , oznaczająca liczbę przedziałów, w których zastosowano c . Całkowita liczba używanych pojemników jest po prostu sumą x _c we wszystkich konfiguracjach, oznaczoną jako 1 · x . Całkowita liczba użytych przedmiotów z każdego rozmiaru jest sumą wektorów a _c · x _c we wszystkich konfiguracjach c. Następnie problem polega na zminimalizowaniu 1 · x takie, że suma a _c · x _c , po wszystkich konfiguracjach c , wynosi co najmniej n , więc wszystkie elementy są spakowane.

Algorytmy

Podstawowe algorytmy

Załóżmy najpierw, że wszystkie przedmioty są duże, to znaczy, że każde s _i jest co najmniej e·B dla pewnego ułamka e > 0. Wtedy całkowita liczba elementów w każdym pojemniku wynosi co najwyżej 1/ e , więc całkowita liczba konfiguracji wynosi co najwyżej d ^{1/ e} . Każda konfiguracja pojawia się co najwyżej n razy. $Dlatego$ istnieje kombinacje Dla każdej kombinacji musimy sprawdzić d ograniczenia (po jednym dla każdego rozmiaru), więc czas wykonania wynosi ${\ Displaystyle d \ cdot n ^ {d ^ {1/e}}}$ , co jest wielomianem w n , gdy d, e są stały.

Główny problem z tym algorytmem (oprócz tego, że działa tylko wtedy, gdy elementy są duże) polega na tym, że jego czas działania jest wielomianowy w n , ale długość wejścia (w reprezentacji binarnej) jest liniowa w log( V ), czyli rzędu wielkości log( n ).

Wielomian czasu wykonywania w rozmiarze wejściowym

Filippi i Agnetis przedstawili algorytm, który znajduje rozwiązanie z co najwyżej OPT+ d -2 przedziałami w czasie O(poly(log V )). W szczególności dla d = 2 różnych rozmiarów ich algorytm znajduje optymalne rozwiązanie w czasie O(log V ).

Goemans i Rothvoss przedstawili algorytm dla dowolnego ustalonego d , który znajduje optymalne rozwiązanie, gdy wszystkie liczby są podane w systemie binarnym. Ich algorytm rozwiązuje następujący problem: biorąc pod uwagę dwa d -wymiarowe polytopy P i Q , znajdź minimalną liczbę punktów całkowitych w P , których suma leży w Q . Ich algorytm działa w czasie ${\ Displaystyle (\ log V) ^ {2 ^ {O (d)}}}$ . Ich algorytm można dostosować do innych problemów, takich jak szeregowanie identycznych maszyn i szeregowanie niepowiązanych maszyn z różnymi ograniczeniami.

Zaokrąglanie instancji ogólnej do instancji o dużej liczebności

Kilka algorytmów aproksymacji dla ogólnego problemu pakowania w pojemniki wykorzystuje następujący schemat:

• Podziel pozycje na „małe” (mniejsze niż eB , dla pewnego ułamka e w (0,1)) i „duże” (przynajmniej eB ).
• Najpierw zajmij się dużymi przedmiotami:
  • Zaokrąglij rozmiary przedmiotów w taki sposób, aby liczba różnych rozmiarów była co najwyżej stałą d.
  • Rozwiąż wynikowy problem dużej krotności.
• Chciwie rozdzielaj małe przedmioty, np. za pomocą pakowania w pojemniki z następnym dopasowaniem . Jeśli nie zostaną utworzone żadne nowe pojemniki, skończymy. Jeśli tworzone są nowe pojemniki, oznacza to, że wszystkie pojemniki (może z wyjątkiem ostatniego) są zapełnione do co najmniej (1- e ) B . Dlatego liczba pojemników wynosi co najwyżej OPT/(1- e )+1 ≤ (1+2e ) OPT+1.

Algorytmy różnią się sposobem, w jaki okrążają instancję.

Zaokrąglenie liniowe

Lueker i de-la-Vega i wymyślili ideę adaptacyjnego zaokrąglania danych wejściowych . Uporządkuj przedmioty według ich wielkości i pogrupuj je w 1/ e ² grupy o liczności ne ² . W każdej grupie zaokrąglij rozmiary w górę do maksymalnego rozmiaru w grupie. Teraz są tylko d = 1/ e ² różne rozmiary. Rozwiązanie z zaokrągloną instancją jest wykonalne również dla oryginalnej instancji, ale liczba pojemników może być większa niż to konieczne. Aby określić ilościowo stratę, rozważ instancję zaokrągloną w dół do maksymalnego rozmiaru w pliku poprzednia grupa (pierwsza grupa jest zaokrąglana w dół do 0). Zaokrąglona w dół instancja D jest prawie równa zaokrąglonej w górę instancji U , z wyjątkiem tego, że w D jest kilka ne ² zer, podczas gdy w U jest kilka ne ² dużych pozycji; ale ich rozmiar to co najwyżej B . Dlatego U wymaga co najwyżej 2 ^pojemników więcej niż D . Ponieważ D wymaga mniejszej liczby pojemników niż optymalna, otrzymujemy, że Bins( U ) ≤ OPT + ne ² , to znaczy, że mamy błąd addytywny, który można dowolnie zmniejszyć, wybierając e .

Jeśli wszystkie elementy są duże (o rozmiarze co najmniej eB ), to każdy pojemnik w OPT zawiera co najwyżej 1/ e elementów (o rozmiarze co najmniej eB ), więc OPT musi mieć co najmniej en . Dlatego Bins( U ) ≤ (1+ e )OPT. Po obsłudze małych przedmiotów otrzymujemy co najwyżej ${\ Displaystyle (1 + 2e) \ operatorname {OPT} +1}$ .

Zaokrąglenie geometryczne

Karmarkar i Karp przedstawiają bardziej wydajną metodę zaokrąglania, którą nazywają zaokrąglaniem geometrycznym (w przeciwieństwie do zaokrąglania liniowego de-la-Vegi i Luekera). Opierając $.$ , przedstawiają algorytm z wielomianem w $wykonywania$ i Ich algorytm znajduje rozwiązanie o rozmiarze co najwyżej ${\ Displaystyle \ operatorname {OPCJA} + {\ mathcal {O}} (\ log ^ {2} (\ operatorname {OPCJA}})$ }

Ulepszenia

Ta technika została później ulepszona przez kilku autorów:

• Rothvoss przedstawił algorytm, który generuje rozwiązanie o rozmiarze co najwyżej ${\ Displaystyle \ operatorname {OPT} + O (\ log ( \mathrm {OPCJA} )\cdot \log \log(\mathrm {OPCJA} ))}$ .

• Hoberg i Rothvoss ulepszyli ten algorytm, aby wygenerować rozwiązanie o rozmiarze co najwyżej ${\ Displaystyle \ operatorname {OPCJA} + O (\ log (\ operatorname {OPCJA}))}$ . Algorytm jest losowy, a jego czas działania jest wielomianem w całkowitej liczbie elementów.

Zobacz też

• Problem wycinania zapasów — podobny do pakowania wielu pojemników, ale celem jest zminimalizowanie całkowitej ilości zmarnowanego miejsca w każdym pojemniku, a nie liczby pojemników. Co więcej, w niektórych wariantach liczba elementów z każdego rozmiaru nie jest stała, ale może się zmieniać między określonymi dolnymi i górnymi granicami.