Algorytm Multifit

Algorytm multifit jest algorytmem wielokierunkowego partycjonowania liczb , pierwotnie opracowanym dla problemu planowania identycznych maszyn . Został opracowany przez Coffmana, Gareya i Johnsona. jako podprogram wykorzystuje algorytm dla innego znanego problemu – problemu pakowania w pojemniki .

Algorytm

Dane wejściowe do algorytmu to zbiór S liczb i parametr n . Wymaganym wynikiem jest podział S na n podzbiorów, tak aby największa suma podzbioru (zwana także makespan ) była jak najmniejsza.

Algorytm używa jako podprogramu algorytmu zwanego FFD ( first-fit-decreasing binpacking ). Algorytm FFD przyjmuje jako dane wejściowe ten sam zestaw S liczb i pojemność binarną c . Heurystycznie pakuje liczby do pojemników, tak aby suma liczb w każdym pojemniku wynosiła co najwyżej C , mając na celu wykorzystanie jak najmniejszej liczby pojemników. Multifit uruchamia FFD wiele razy, za każdym razem z inną pojemnością C , aż znajdzie takie C , że FFD o pojemności C spakuje S do co najwyżej n kosze. Aby go znaleźć, używa wyszukiwania binarnego w następujący sposób.

Niech L := max (suma( S ) / n , max( S ) ). Uwaga: przy pojemności pojemnika mniejszej niż L każde opakowanie musi wykorzystywać więcej niż n pojemników.
Niech U := max ( 2 sum( S ) / n , max( S ) ). Zauważ, że przy pojemności pojemników co najmniej U FFD wykorzystuje co najwyżej n pojemników. Dowód : załóżmy przez sprzeczność, że niektóre dane wejściowe nie _pasują do żadnego z pierwszych n pojemników. Oczywiście jest to możliwe tylko wtedy, gdy i ≥ n +1. Jeśli s _i > C/2, to skoro dane wejściowe są uporządkowane malejąco, ta sama nierówność zachodzi dla wszystkich pierwszych n +1 wejścia w S . Oznacza to, że sum(S) > (n+1) C /2 > n U /2, sprzeczność z definicją U . W przeciwnym razie s _i ≤ C/2. Zatem suma każdego z pierwszych n pojemników jest większa niż C/2. To znowu implikuje sum(S) > n C /2 > n U /2, sprzeczność.
Iteruj k razy (gdzie k jest parametrem precyzji):
- Niech C := ( L + U )/2. Uruchom FFD na S z pojemnością C .
  - Jeśli FFD potrzebuje co najwyżej n pojemników, zmniejsz U , pozwalając U := C .
  - Jeśli FFD potrzebuje więcej niż n pojemników, zwiększ L, pozwalając L := C.
Na koniec uruchom FFD z pojemnością U . Gwarantowane jest użycie co najwyżej n pojemników. Zwróć wynikowy harmonogram.

Wydajność

Multifit to algorytm aproksymacji o stałym współczynniku . Zawsze znajduje partycję, w której makespan jest co najwyżej stałym współczynnikiem większym niż optymalny makespan. Aby znaleźć tę stałą, musimy najpierw przeanalizować FFD. Podczas gdy standardowa analiza FFD uwzględnia przybliżoną liczbę pojemników, gdy pojemność jest stała, tutaj musimy przeanalizować przybliżoną liczbę pojemników , gdy liczba pojemników jest stała. Formalnie dla każdego rozmiaru wejściowego S i liczby całkowitej n niech ${\ displaystyle OPT (S, n)}$ będzie najmniejszą pojemnością taką, że S można zapakować w n pojemników o tej pojemności. Zauważ, że $jest$ planowania

Niech ${\ displaystyle r_ {n}}$ będzie najmniejszą liczbą rzeczywistą taką, że dla każdego wejścia S FFD o pojemności ${\ Displaystyle r_ {n} \ cdot OPT (S ,n)}$ wykorzystuje maksymalnie n pojemników.

Górne granice

Coffman, Garey i Johnson udowadniają następujące górne granice na ${\ displaystyle r_ {n}}$ :

${\ Displaystyle r_ {n} \ równoważnik 8/7 \ około 1,14}$ n = 2
${\ Displaystyle r_ {n} \ równoważnik 15/13 \ około 1,15}$ n = 3
${\ Displaystyle r_ {n} \ równoważnik 20/17 \ około 1,176}$ = 4,5,6,7 ;
$równoważnik 122/100 = 1,22}$ dla wszystkich ≥ 8.

Podczas algorytmu MultiFit dolna granica L jest zawsze pojemnością, dla której nie można upakować S do n pojemników. Dlatego ${\ Displaystyle L <r_ {n} \ cdot OPT (S, n)}$ . Początkowo różnica $co$ sumę ( ) / n , czyli ${\ Displaystyle OPT (S, n)}$ . Po uruchomieniu algorytmu MultiFit przez k iteracji różnica zmniejsza się k razy o połowę, więc ${\ Displaystyle UL \ równoważnik (1/2) ^ { k}\cdot OPT(S,n)}$ . Dlatego ${\ Displaystyle U \ równoważnik (r_ {n} + (1/2) ^ {k}) \ cdot OPT (S, n)}$ . $optymalna$ związku z tym harmonogram zwracany przez MultiFit . Gdy $wystarczająco$ , współczynnik przybliżenia MultiFit można dowolnie zbliżyć do ${\ displaystyle r_ {n}}$ , co najwyżej 1,22 .

Późniejsze prace przeprowadzili bardziej szczegółową analizę MultiFit i dowiedli, że jego współczynnik aproksymacji wynosi co najwyżej 6/5 = 1,2 , a później co najwyżej 13/11 ≈ 1,182 . Oryginalny dowód na to pominął niektóre przypadki; przedstawił pełny i prostszy dowód. 13/11 nie można poprawić: istnieje przypadek z n = 13, w którym współczynnik aproksymacji wynosi dokładnie 13/11.

Dolne granice

Dla n 4 $=$ : co ciasno Wejścia to 9,7,6,5,5, 4,4,4,4,4,4,4,4,4. Można je zapakować do 4 pojemników o pojemności 17 w następujący sposób:

9, 4, 4
7, 6, 4
5, 4, 4, 4
5, 4, 4, 4

Ale jeśli uruchomimy FFD z pojemnością pojemnika mniejszą niż 20, to wypełnione pojemniki to:

9,7 [4 nie pasuje]
6,5,5 [4 nie pasuje]
4,4,4,4 [4 nie pasuje]
4,4,4,4
4

Zauważ, że suma w każdym z pierwszych 4 pojemników wynosi 16, więc nie możemy umieścić w nim kolejnych 4. Dlatego 4 pojemniki to za mało.

Dla n = 13 $że$ poniższe pokazuje . Wejścia można upakować w 13 pojemnikach o pojemności 66 w następujący sposób:

40,13,13 {8 razy}
25,25,16 {3 razy}
25,24,17 {2 razy}

Ale jeśli uruchomimy FFD z pojemnością pojemnika mniejszą niż 66*13/11 = 78, to wypełnione pojemniki to:

40,25 {8 razy}
24, 24, 17
17, 16, 16, 16
13, 13, 13, 13, 13 {3 razy}
13

Zauważ, że suma w każdym z pierwszych 13 pojemników wynosi 65, więc nie możemy umieścić w nim kolejnych 13. Dlatego 13 pojemników to za mało.

Wydajność z jednolitymi maszynami

MultiFit może być również używany w bardziej ogólnym ustawieniu zwanym planowaniem jednolitych maszyn , w którym maszyny mogą mieć różne prędkości przetwarzania. Gdy istnieją dwie jednolite maszyny, współczynnik aproksymacji wynosi ${\ displaystyle {\ sqrt {6}}/2}$ . Gdy MultiFit jest połączony z algorytmem LPT , stosunek poprawia się do ${\ displaystyle {\ sqrt {2}} + 1/2}$ . ^{[ wymagane wyjaśnienie ]}

Wydajność dla maksymalizacji najmniejszej sumy

Podwójnym celem minimalizacji największej sumy (makespan) jest maksymalizacja najmniejszej sumy. Deuermeyer, Friesen i Langston twierdzą, że MultiFit nie ma dobrego współczynnika przybliżenia dla tego problemu:

„W rozwiązaniu problemu makespan za pomocą MULTIFIT łatwo jest skonstruować przykłady, w których jeden procesor nigdy nie jest używany. ^{[ wymagane wyjaśnienie ]} Takie rozwiązanie jest do przyjęcia dla problemu makespan, ale jest całkowicie nie do zaakceptowania dla naszego problemu _{[od najmniejszej sumy jest 0]} . Można opracować modyfikacje MULTIFIT, które byłyby bardziej odpowiednie dla naszego problemu, ale nie mogliśmy znaleźć żadnej, która dawałaby lepsze ograniczenie najgorszego przypadku niż LPT ” .

Pomysł na dowód

Minimalne kontrprzykłady

Górne granice na $udowodnione$ sprzeczność. Dla dowolnych liczb całkowitych $)$ ≥ q , , to ( p / q , zdefiniowany jako instancja i liczba n takie że

S można upakować w n pojemnikach o pojemności q ;
FFD nie udaje się spakować S do n pojemników o pojemności p .

Jeśli istnieje taki kontrprzykład, to istnieje również kontrprzykład minimalny (p/q) , czyli kontrprzykład ( p / q ) z najmniejszą liczbą elementów w S i najmniejszą liczbą pojemników n . W kontrprzykładzie minimalnym (p/q) , FFD pakuje wszystkie elementy w S z wyjątkiem ostatniego (najmniejszego) do n pojemników o pojemności p . Biorąc pod uwagę minimalny (p/q) -kontrprzykład, oznaczmy przez P ₁ ,...,P _n (niekompletne) upakowanie FFD do tych n pojemników o pojemności p , przez P _n+1 pojemnik zawierający pojedynczy najmniejszy element, a przez Q ₁ ,...,Q _n (pełne) optymalne upakowanie do n pojemników o pojemności q . Można udowodnić następujące lematy:

Żadna suma k podzbiorów z {Q _1,..., Q _n } nie jest zdominowana przez sumę k podzbiorów z {P _1,..., P _n+1 } („zdominowany” oznacza, że każdy element w zdominowanym podzbiór jest mapowany na słabo większy element w podzbiorze dominującym). W przeciwnym razie moglibyśmy otrzymać mniejszy kontrprzykład w następujący sposób. [1] Usuń wszystkie elementy w P _i . Oczywiście niekompletne opakowanie FFD wymaga teraz n - k pojemników, a mimo to najmniejszy element (lub cały pojemnik) pozostaje rozpakowany. [2] W optymalnym upakowaniu Q _i , zamień każdy przedmiot z jego dominującym przedmiotem. Teraz k podzbiorów Q _i jest większych (prawdopodobnie większych niż q ), ale wszystkie inne n - k podzbiorów są mniejsze (w szczególności co najwyżej q ). Dlatego po usunięciu wszystkich elementów z P _i pozostałe elementy można zapakować do co najwyżej n - k pojemników o rozmiarze q .
Każde z Q _1,..., Q _n zawiera co najmniej 3 pozycje. Dzieje się tak dlatego, że [a] każde Q _i z pojedynczym przedmiotem jest zdominowane przez Pj _, które zawiera ten przedmiot; [b] dla każdego Q _i z dwoma pozycjami x i y , jeśli oba x i y są w tym samym P _j , to Q _i jest zdominowane przez to P _j ; [c] Załóżmy, że x≥y, x jest w jakimś Pj _, a y jest w jakimś _Pk na prawo. Oznacza to, że y nie pasowało do P _j . Ale x+y ≤ q. Oznacza to, że P _j musi zawierać jakiś element z ≥ y. Zatem Q _i jest zdominowane przez P _j . [d] Załóżmy, że x≥y, x jest w pewnym P _j , a y jest w pewnym P _k na lewo od niego. Oznacza to, że musi istnieć poprzedni element z ≥ x. Zatem Q _i jest zdominowane przez P _k .
W przeciwnym razie mielibyśmy dominację i zgodnie z poprzednim lematem moglibyśmy otrzymać mniejszy kontrprzykład.
Każdy z P _1,..., P _n zawiera co najmniej 2 pozycje. Dzieje się tak, ponieważ jeśli jakieś P _i zawiera tylko jeden element, oznacza to, że ostatni (najmniejszy) element do niego nie pasuje. Oznacza to, że ten pojedynczy przedmiot musi być sam w optymalnym pakiecie, co jest sprzeczne z poprzednim lematem.
Niech s będzie wielkością najmniejszego przedmiotu. wtedy ${\ Displaystyle s> {\ Frac {n} {n-1}} (pq)}$ . Dowód : Ponieważ s nie pasuje do pierwszych n wiązek, mamy ${\ Displaystyle sum (P_ {i}) + s> p}$ , więc ${\ Displaystyle \ suma _ {i = 1} ^ {n} suma (P_ {i}) + n \ cdot s> n \ cdot p}$ . Z drugiej strony, ponieważ wszystkie przedmioty mieszczą się w n pojemnikach o pojemności q , mamy ${\ Displaystyle \ suma _ {i = 1} ^ {n} suma (P_ {i}) + s \ równoważnik n \ cdot q}$ . Odejmując nierówności daje ${\ Displaystyle s> {\ Frac {n} {n-1}} (pq)}$ .
Rozmiar każdego elementu wynosi co najwyżej ${\ displaystyle q-2s}$ . Dzieje się tak, ponieważ w każdym optymalnym pojemniku (o pojemności q ) znajdują się co najmniej 3 przedmioty .
Suma elementów w każdym pojemniku P _{1, ...,} P _n jest większa niż ${\ displaystyle ps}$ ; w przeciwnym razie moglibyśmy dodać najmniejszy element.

5/4 Górna granica

Z powyższych lematów można już udowodnić luźną górną granicę ${\ Displaystyle r_ {n} \ równoważnik 5/4 = 1,25$ } dowód . Niech S , n będzie minimalnym (5/4)-kontrprzykładem. Powyższe lematy implikują, że -

${\ Displaystyle s> {\ Frac {n} {n-1}} (5-4)> 1}$ . Ponieważ optymalna pojemność to 4, żaden optymalny pojemnik nie może zawierać 4 lub więcej przedmiotów. Dlatego każdy optymalny kosz musi zawierać co najwyżej 3 elementy, a liczba elementów to co najwyżej 3 n .
Rozmiar każdego elementu wynosi co najwyżej $5$ każdego pojemnika FFD jest większy niż $displaystyle 5-s}$ . Gdyby jakiś pojemnik FFD zawierał tylko dwa elementy, jego suma wynosiłaby co najwyżej ${\ Displaystyle 8-4s = 5 + (3-3s) -s <5-s}$ ; więc każdy pojemnik FFD musi zawierać co najmniej 3 elementy. Ale to oznacza, że FFD daje dokładnie n pojemników - sprzeczność.

Struktura opakowania FFD

Aby udowodnić ściślejsze granice, należy przyjrzeć się bliżej upakowaniu FFD minimalnego ( p / q )-kontrprzykładu. Pozycje i pojemniki FFD P ₁ ,..., P _n są określane w następujący sposób:

Zwykła pozycja to pozycja dodana do jakiegoś pojemnika P _{i , zanim} został otwarty kolejny pojemnik P _{i+1 .} Równoważnie, zwykły przedmiot to przedmiot w P _i , który jest co najmniej tak duży jak każdy przedmiot w każdym pojemniku _Pj dla j > i .
Pozycja rezerwowa to pozycja dodana do jakiegoś pojemnika P _{i po} otwarciu kolejnego pojemnika P _{i+1 .} Równoważnie, pozycja rezerwowa to pozycja w P _i , która jest mniejsza niż największa pozycja w P _i+1 .
Zwykły k-pojemnik to pojemnik, który zawiera k zwykłych elementów i żadnych elementów rezerwowych.
Awaryjny k-bin to kosz, który zawiera k zwykłych elementów i kilka elementów rezerwowych.

Następujące lematy wynikają bezpośrednio z tych definicji i działania FFD.

Jeśli k ₁ < k ₂ , to wszystkie pojemniki k ₁ znajdują się na lewo od wszystkich pojemników k ₂ . Wynika to z faktu, że wszystkie pojemniki mają taką samą pojemność, więc jeśli do pojemnika zmieści się więcej zwykłych przedmiotów, muszą one być mniejsze, więc należy je przydzielić później.
Jeśli P _ja jest k -bin, to suma k regularnych elementów w P _ja jest większa niż ${\ Displaystyle {\ Frac {k} {k + 1}} \ cdot p}$ , ponieważ w przeciwnym razie moglibyśmy dodać kolejny element przed otwarciem nowego pojemnika.
Jeśli P _i i P _i+1 są k -przedziałami, to suma k elementów regularnych w P _i jest co najmniej tak duża jak w P _i+1 (to dlatego, że elementy są uporządkowane według malejącego rozmiaru).
Wszystkie zwykłe k -pojemniki znajdują się na lewo od wszystkich rezerwowych k -pojemników. Wynika to z faktu, że wszystkie pojemniki mają taką samą pojemność, więc jeśli w pojemniku zmieści się więcej elementów rezerwowych, elementy te muszą być mniejsze, więc muszą zostać przydzielone później.

W minimalnym kontrprzykładzie nie ma regularnych 1-pojemników (ponieważ każdy przedział zawiera co najmniej 2 elementy), więc zgodnie z powyższymi lematami, pojemniki FFD P ₁ ,...,P _n są uporządkowane według typu:

Zero lub więcej rezerwowych 1-pojemników;
Następnie zero lub więcej zwykłych 2-pojemników;
Następnie zero lub więcej rezerwowych 2-pojemników;
Następnie zero lub więcej zwykłych 3-pojemników;
Następnie zero lub więcej rezerwowych 3-pojemników;
i tak dalej.

1,22 górna granica

Górna granica $udowodniona przez$ minimalnego (122/100) Każdemu artykułowi przypisywana jest waga na podstawie jego rozmiaru i pojemnika w opakowaniu FFD. Wagi są określane w taki sposób, że całkowita waga w każdym pojemniku FFD wynosi co najmniej x , a całkowita waga w prawie każdym optymalnym pojemniku wynosi co najwyżej x (dla niektórych z góry określonych x ). Oznacza to, że liczba pojemników FFD jest co najwyżej liczbą pojemników optymalnych, co przeczy założeniu, że jest to kontrprzykład.

Z powyższych lematów wiemy, że:

Rozmiar najmniejszego elementu spełnia s > p - q = 22, więc s = 22+ D dla pewnego D > 0.
Każdy optymalny kosz zawiera co najwyżej 4 elementy (podłoga (100/22)), a każdy kosz FFD zawiera co najwyżej 5 elementów (podłoga (122/22)).
Rozmiar każdego elementu to co najwyżej q -2 s = 56-2 D .
Suma w każdym pojemniku FFD jest większa niż p - s = 100 - D .
Nie ma 1-pojemników, ponieważ w 1-pojemniku rozmiar zwykłego elementu musi wynosić co najmniej p /2=61, podczas gdy tutaj rozmiar każdego elementu jest mniejszy niż 56.

Jeśli D > 4, rozmiar każdego elementu jest większy niż 26, więc każdy optymalny pojemnik (o pojemności 100) musi zawierać co najwyżej 3 elementy. Każdy element jest mniejszy niż 56-2 D , a każdy pojemnik FFD ma sumę większą niż 100- D , więc każdy pojemnik FFD musi zawierać co najmniej 3 elementy. Dlatego jest co najwyżej n pojemników FFD - sprzeczność. Więc od teraz zakładamy D≤ 4. Pozycjom przypisuje się typy i wagi w następujący sposób.

Dwa elementy w każdym zwykłym 2-pojemniku, z wyjątkiem ostatniego, mają rozmiar większy niż (100- D )/2 każdy. Wszystkie takie elementy nazywane są typem-X2 _i mają przypisaną wagę (100- D )/2. Ostatni 2-regularny pojemnik jest przypadkiem szczególnym: jeśli oba jego elementy mają rozmiar większy niż (100- D )/2, to również są typu X _{2 ;} w przeciwnym razie nazywane są type-Z , a ich waga jest równa ich rozmiarowi.
Dwa zwykłe elementy w każdym rezerwowym 2-pojemniku mają łączny rozmiar większy niż 2*122/3; nazywane są typem-Y ₂ , a ich waga jest równa ich rozmiarowi minus D .
Trzy elementy w każdym zwykłym 3-pojemniku, z wyjątkiem ostatniego, mają rozmiar większy niż (100- D )/3 każdy. Wszystkie takie pozycje nazywane są typem-X ₃ i mają przypisaną wagę (100- D )/3. Ostatni 3-zwykły pojemnik to przypadek szczególny: jeśli wszystkie elementy w nim zawarte mają rozmiar większy niż (100- D )/3, to również są typu X _{3 ;} w przeciwnym razie nazywane są typem Z , a ich waga jest równa ich rozmiarowi.
Trzy zwykłe elementy w każdym rezerwowym 3-pojemniku mają łączny rozmiar większy niż 3*122/4; nazywane są typem-Y ₃ , a ich waga jest równa ich rozmiarowi minus D .
Cztery elementy w każdym zwykłym 4-pojemniku, z wyjątkiem ostatniego, mają rozmiar większy niż (100- D )/4 każdy. Wszystkie takie elementy nazywane są typem-X ₄ i mają przypisaną wagę (100- D )/4. Ostatni 4-zwykły pojemnik to przypadek szczególny: jeśli wszystkie elementy w nim zawarte mają rozmiar większy niż (100- D )/4, to również są typu X _{4 ;} w przeciwnym razie nazywane są typem Z , a ich waga jest równa ich rozmiarowi.
Pozostałe elementy (w tym wszystkie zapasowe elementy w rezerwowych 2-pojemnikach i 3-pojemnikach, wszystkie rezerwowe 4-pojemniki i wszystkie inne 5-elementowe pojemniki) są nazywane type-X 5 , a ich waga wynosi 22 ( _jeśli D ≤ 12 /5) lub (100- D )/4 (w przeciwnym razie). Próg 12/5 został obliczony w taki sposób, że waga zawsze wynosi co najwyżej 22+ D , tak więc waga jest zawsze mniejsza niż rozmiar.

Zwróć uwagę, że waga każdego przedmiotu to co najwyżej jego rozmiar (waga może być postrzegana jako rozmiar „zaokrąglony w dół”). Mimo to łączna waga przedmiotów w każdym pojemniku FFD wynosi co najmniej 100- D :

Dla zwykłych 2-pojemników, zwykłych 3-pojemników i zwykłych 4-pojemników:
- Dla nieostatnich jest to natychmiastowe.
- Ostatnie takie pojemniki zawierają tylko przedmioty typu Z, których waga jest równa ich rozmiarowi, więc łączna waga tych pojemników jest równa ich całkowitemu rozmiarowi, który jest większy niż 100- D .
Awaryjne 2-pojemniki zawierają dwa elementy typu Y ₂ o łącznej wadze większej niż 2*122/3-2 D oraz co najmniej jeden element typu X ₅ o wadze co najmniej 22 (jeśli D ≤ 12/5) lub (100 - D )/4 (inaczej). W obu przypadkach łączna waga przekracza 100- D .
Awaryjne 3-pojemniki zawierają trzy przedmioty typu Y ₃ o łącznej wadze większej niż 3*122/4-3 D oraz co najmniej jeden przedmiot typu X ₅ o wadze co najmniej 22. Zatem łączna waga jest większa niż 3*122 /4+22-3 re = 113,5-3 re ≥ 105,5- re > 100- re , ponieważ D ≤ 4.
Pojemniki 5-elementowe zawierają 5 elementów o rozmiarze co najmniej 22+ D i wadze co najmniej 22, więc ich łączna waga jest oczywiście większa niż 100- D .

Całkowita waga przedmiotów w najbardziej optymalnych pojemnikach wynosi maksymalnie 100- D :

Jest to jasne dla każdego optymalnego pojemnika zawierającego element typu -Y ₂ lub typu -Y ₃ , ponieważ ich waga to ich rozmiar minus D , waga innych elementów to co najwyżej ich rozmiar, a całkowity rozmiar optymalnego pojemnika wynosi najwyżej 100.
Dla optymalnych pojemników zawierających tylko elementy typu -X ₂ , typ -X ₃ , typ -X ₄ i typ -X ₅ można sprawdzić wszystkie możliwe konfiguracje (wszystkie kombinacje mieszczące się w pojemniku optymalnym o rozmiarze 100) i zweryfikować że całkowity ciężar w każdej konfiguracji wynosi co najwyżej 100- D .
Optymalne pojemniki zawierające elementy typu Z mogą mieć łączną wagę większą niż 100- D . Ponieważ całkowita waga wynosi co najwyżej 100, istnieje „nadwaga” wynosząca co najwyżej D dla każdego takiego pojemnika. Jednak liczba pozycji typu Z jest ograniczona:
- Jeśli D > 12/5, to jest co najwyżej 5 elementów typu Z (2 w ostatnim zwykłym 2-pojemniku i 3 w ostatnim zwykłym 3-pojemniku; pozycje w ostatnim zwykłym 4-pojemniku są wszystkie typu X ₄ ). Dlatego nadwaga wynosi co najwyżej 5 D . Porównanie całkowitej masy FFD z optymalnymi pojemnikami daje s <5 D ≤ 20 <22, sprzeczność.
- W przeciwnym razie jest co najwyżej 9 pozycji typu Z (2+3+4). Dlatego nadwaga wynosi co najwyżej 9 D . Porównanie całkowitej masy FFD z optymalnymi pojemnikami daje s <9 D ≤ 108/5 <22, sprzeczność.

13/11 górna granica

R ${\ Displaystyle r_ {n} \ równoważnik 13/11 \ około 1,182}$ przez założenie minimalnego ((120-3 d /100) -kontrprzykładu, z pewnym d < 20/33 i wyprowadzając sprzeczność.

Niemonotoniczność

MultiFit nie jest monotonny w następującym sensie: możliwe jest, że dane wejściowe maleją , podczas gdy maksymalna suma w partycji zwracanej przez MultiFit rośnie . Załóżmy na przykład, że n = 3, a liczby wejściowe to:

44, 24, 24, 22, 21, 17, 8, 8, 6, 6.

FFD pakuje te dane wejściowe do 3 pojemników o pojemności 60 (co jest optymalne):

44, 8, 8;
24, 24, 6, 6;
22, 21, 17.

Ale jeśli „17” zmieni się w „16”, to FFD o pojemności 60 potrzebuje 4 pojemników:

44, 16;
24, 24, 8;
22, 21, 8, 6;
6.

więc MultiFit musi zwiększyć pojemność np. do 62:

44, 16;
24, 24, 8, 6;
22, 21, 8, 6.

Uogólnienie: sprawiedliwy podział obowiązków

Multifit został rozszerzony na bardziej ogólny problem przydziału obowiązków zgodnie z maksyminem . W tym problemie S jest zbiorem obowiązków i istnieje n agentów, którzy przypisują obowiązkom potencjalnie różne wartościowania. Celem jest przydzielenie każdemu agentowi zestawu obowiązków wartych co najwyżej r- krotność wartości maksymalnej w optymalnym harmonogramie opartym na i wyceny. Naiwnym podejściem jest pozwolenie każdemu agentowi po kolei na użycie algorytmu MultiFit do obliczenia progu, a następnie użycie algorytmu, w którym każdy agent używa własnego progu. Gdyby to podejście zadziałało, otrzymalibyśmy przybliżenie 13/11. Jednak to podejście zawodzi ze względu na niemonotoniczność FFD .

Przykład

Oto przykład. Załóżmy, że jest czterech agentów, którzy mają wyceny dwóch typów:


Typ A:	51	27,5	27,5	27,5	27,5	25	12	12	10	10	10	10	10	10	10	10	10
Typ B.:	51	27,5	27,5	27,5	27,5	24	20	20	8.33	8.33	8.33	8.33	8.33	8.33	8.33	8.33	8.33

Oba typy mogą podzielić obowiązki na 4 części o łącznej wartości 75. Typ A:

51, 12, 12
27,5, 27,5, 10, 10
27,5, 27,5, 10, 10
25, 10, 10, 10, 10, 10

Typ B.:

51, 24
27,5, 27,5, 20
27,5, 27,5, 20
8,33 {9 razy}

Jeśli wszyscy czterej agenci są tego samego rodzaju, wówczas FFD z progiem 75 wypełnia 4 optymalne przedziały. Ale załóżmy, że jest jeden agent typu B, a pozostali są typu A. Wtedy w pierwszej rundzie agent typu B bierze pakiet 51, 24 (inni agenci nie mogą go wziąć, ponieważ dla nich wartości to 51 ,25, których suma jest większa niż 75). W kolejnych rundach wypełniane są następujące paczki dla agentów typu A:

27,5, 27,5, 12 [suma to 67 - nie ma miejsca na kolejne 10]
27,5, 27,5, 12 [suma to 67 - nie ma miejsca na kolejne 10]
10, 10, 10, 10, 10, 10, 10 [suma to 70 - nie ma miejsca na kolejne 10]

więc ostatnie dwa obowiązki pozostają nieprzydzielone.

Korzystając z bardziej wyrafinowanych obliczeń progowych, można zagwarantować każdemu agentowi co najwyżej 11/9≈1,22 jego wartości optymalnej, jeśli znana jest wartość optymalna, i co najwyżej 5/4≈1,25 jego wartości optymalnej (przy użyciu czasu wielomianowego algorytm), jeśli optymalna wartość nie jest znana.

Implementacje

Python: pakiet prtpy zawiera implementację multifit .