Första-passning-minskande kärlpackning

First-fit-decreasing (FFD) är en algoritm för bin packning . Dess ingång är en lista över föremål av olika storlekar. Dess produktion är en packning - en uppdelning av föremålen i fack med fast kapacitet, så att summan av storlekarna av föremål i varje fack är som mest kapaciteten. Helst skulle vi vilja använda så få lagerplatser som möjligt, men att minimera antalet lagerplatser är ett NP-hårt problem, så vi använder en ungefär optimal heuristik .

Beskrivning

FFD-algoritmen fungerar enligt följande.

Beställ varorna från största till minsta.
Öppna en ny tom papperskorg, fack #1.
För varje föremål från största till minsta, hitta den första behållaren som föremålet passar i, om någon.
- Om en sådan papperskorg hittas, lägg det nya föremålet i det.
- Annars öppnar du en ny tom papperskorg och lägger det nya föremålet i det.

Kort sagt: FFD beställer föremålen efter fallande storlek och anropar sedan förpackning för första passning .

En ekvivalent beskrivning av FFD-algoritmen är som följer.

Beställ varorna från största till minsta.
Medan det finns kvarstående föremål:
- Öppna en ny tom papperskorg.
- För varje föremål från största till minsta:
  - Om den får plats i den aktuella behållaren, sätt in den.

I standardbeskrivningen går vi över föremålen en gång, men håller många öppna papperskorgar. I motsvarande beskrivning går vi över föremålen många gånger, men behåller endast en öppen papperskorg varje gång.

Prestationsanalys

FFD:s prestanda analyserades i flera steg. Nedan anger $FFD(S,C)$ antalet fack som används av FFD för ingångsuppsättning S och bin-kapacitet C.

1973 bevisade DS Johnson i sin doktorsavhandling att $FFD(S,C)\leq 11/9\mathrm { OPT} (S,C)+4$ för valfri instans S och kapacitet C .
1985 gav BS Backer ett något enklare bevis och visade att additivkonstanten inte är mer än 3.
Yue Minyi bevisade att $FFD(S,C)\leq 11/9\mathrm {OPT} (S,C) +1$ 1991 och, 1997, förbättrade denna analys till $FFD(S,C)\leq 11 /9\mathrm {OPT} (S,C)+7/9$ tillsammans med Li Rongheng.
2007 bevisade György Dósa den snäva gränsen $FFD(S,C)\leq 11/9\mathrm {OPT } (S,C)+6/9$ och presenterade ett exempel där $FFD(S,C) =11/9\mathrm {OPT} (S,C)+6/9$ .

Värsta exempel

Exemplet med den nedre gränsen som ges av Dósa är följande: Tänk på de två lagerkonfigurationerna:

$B_{1}:=\{1/2+\varepsilon ,1/4+\varepsilon ,1 /4-2\varepsilon \}$ ;
$B_{2}:=\{1/4+2\ varepsilon ,1/4+2\varepsilon ,1/4-2\varepsilon ,1/4-2\varepsilon \}$ .

Om det finns 4 kopior av $B_{1}$ och 2 kopior av $B_{2}$ i den optimala lösningen, kommer FFD att beräkna följande fack:

4 fack med konfiguration $\{1/2+\varepsilon ,1/4+2\varepsilon \}$ ,
1 fack med konfiguration $\{1/4+\varepsilon ,1/4+\varepsilon ,1/4+\varepsilon \}$ ,
1 fack med konfiguration $\{1/4+\varepsilon ,1/4-2\ varepsilon ,1/4-2\varepsilon ,1/4-2\varepsilon \}$ ,
1 fack med konfiguration $\{1/4-2\varepsilon ,1/4- 2\varepsilon ,1/4-2\varepsilon ,1/4-2\varepsilon \}$ ,
1 en sista fack med konfiguration $\{1/4-2\varepsilon \}$ ,

Det vill säga totalt 8 fack, medan det optimala bara har 6 fack. Därför är den övre gränsen snäv, eftersom $11/9\cdot 6+6/9=72/9=8$ .

Detta exempel kan utökas till alla storlekar av ${\text{OPT}}(S,C)$ : i den optimala konfigurationen finns det 9 k +6 fack: 6 k +4 av typen B ₁ och 3 k +2 av typ B ₂ . Men FFD behöver minst 11 k +8 fack, vilket är ${\frac {11}{9}}(6k+4)+{\frac {6}{ 9}}$ .

Monotonicitetsegenskaper

Tvärtemot intuitionen är $FFD(S,C)$ inte en monoton funktion av C . Anta till exempel att ingången är:

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

Med kapacitet 60, packar FFD 3 fack:

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

Men med kapacitet 61, packar FFD 4 fack:

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

Detta beror på att, med kapacitet 61, passar 17:an i den första behållaren och blockerar därmed vägen till följande 8, 8.

Ett annat exempel

Som ett annat exempel, anta att ingångarna är: 51, 28, 28, 28, 27, 25, 12, 12, 10, 10, 10, 10, 10, 10, 10, 10. Med kapacitet 75, packar FFD 4 fack:

51, 12, 12
28, 28, 10
28, 27, 10, 10
25, 10, 10, 10, 10, 10

Men med kapacitet 76 behöver den 5 papperskorgar:

51, 25
28, 28, 12
28, 27, 12
10, 10, 10, 10, 10, 10, 10
10

På liknande sätt är $FFD(S,C)$ inte en monoton funktion av storleken på föremål i S : det är möjligt att ett föremål krymper i storlek, men antalet papperskorgar ökar. Betrakta exemplet ovan med kapacitet 60. Om 17 blir 16 blir den resulterande packningen:

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

Emellertid har FFD-algoritmen en "asymptotisk monotoni"-egenskap, definierad enligt följande.

För varje instans S och heltal m , låt MinCap( S,m ) vara den minsta kapaciteten C så att ${\displaystyle OPT(S,C)\leq m$
För varje heltal m , låt MinRatio( m ) vara infimum av talen r ≥1 så att för alla ingångsmängder S , $FFD( S,r\cdot {\text{MinCap}}(S,m))\leq m$ . Detta är den mängd som vi behöver för att "blåsa upp" lådorna så att FFD uppnår det optimala antalet fack.
Sedan, för varje ingång S och för varje r ≥ MinRatio( m ), $FFD(S,r\cdot {\text{MinCap}} (S,m))\leq m$ . Detta visar särskilt att infimumet i definitionen ovan kan ersättas med minimum.

Modifierad first-fit-minskande

Modified first fit decreasing (MFFD) förbättrar FFD för föremål som är större än en halv papperskorg genom att klassificera föremål efter storlek i fyra storleksklasser stor, medium, liten och liten, motsvarande föremål med storlek > 1/2 bin, > 1/3 bin, > 1/6 bin respektive mindre föremål. Sedan fortsätter det genom fem faser:

Tilldela en papperskorg för varje stort föremål, beställt från största till minsta.
Fortsätt framåt genom soporna. På varje: Om det minsta kvarvarande medelstora föremålet inte får plats, hoppa över den här papperskorgen. Annars placerar du det största kvarvarande medelstora föremålet som passar.
Fortsätt bakåt genom de papperskorgar som inte innehåller ett medium föremål. På varje: Om de två minsta kvarvarande små föremålen inte får plats, hoppa över den här soptunnan. Annars placerar du det minsta kvarvarande lilla föremålet och det största kvarvarande lilla föremålet som passar.
Fortsätt framåt genom alla papperskorgar. Om det minsta kvarvarande föremålet av någon storleksklass inte passar, hoppa över den här papperskorgen. I annat fall placerar du det största föremålet som passar och stannar på den här papperskorgen.
Använd FFD för att packa de återstående föremålen i nya papperskorgar.

Denna algoritm studerades först av Johnson och Garey 1985, där de bevisade att $MFFD( S,C)\leq (71/60)\mathrm {OPT} (S,C)+(31/6)$ . Denna gräns förbättrades år 1995 av Yue och Zhang som bevisade att $MFFD(S,C)\ leq (71/60)\mathrm {OPT} (S,C)+1$ .

Andra varianter

Best-fit-decreasing (BFD) är mycket lik FFD, förutom att efter att listan har sorterats, bearbetas den genom best-fit bin packing . Dess asymptotiska approximationsförhållande är detsamma som FFD - 11/9.

Genomföranden

Python: Paketet prtpy innehåller en implementering av first-fit minskande .

Se även

Multifit-algoritm - en algoritm för schemaläggning av identiska maskiner, som använder FFD som en subrutin.

^ Johnson, David S (1973). "Nästan optimala bin packing algoritmer" (PDF) . Massachusetts Institute of Technology .
^ Baker, Brenda S. (1985). "Ett nytt bevis för den första anpassningsbara algoritmen för förpackning av fack". J. Algoritmer . 6 (1): 49–70. doi : 10.1016/0196-6774(85)90018-5 .
^ Yue, Minyi (oktober 1991). "Ett enkelt bevis på ojämlikheten FFD (L) ≤ 11/9 OPT (L) + 1, ∀L för FFD bin-packing-algoritmen". Acta Mathematicae Applicatae Sinica . 7 (4): 321–331. doi : 10.1007/BF02009683 . S2CID 189915733 .
^ Li, Rongheng; Yue, Minyi (augusti 1997). "Beviset på FFD(L) < -OPT(L) + 7/9". Kinesisk vetenskapsbulletin . 42 (15): 1262–1265. Bibcode : 1997ChSBu..42.1262L . doi : 10.1007/BF02882754 . S2CID 93280100 .
^ ^a ^b Dósa, György (2007). "The Tight Bound of First Fit Minskande Bin-Packing Algoritm är FFD(I) ≤ 11/9OPT(I) + 6/9". Kombinatorik, algoritmer, probabilistiska och experimentella metoder. FLYKT . doi : 10.1007/978-3-540-74450-4_1 .
^ ^a ^b Coffman, Jr., EG; Garey, MR; Johnson, DS (1978-02-01). "En tillämpning av bin-packning till multiprocessor-schemaläggning" . SIAM Journal on Computing . 7 (1): 1–17. doi : 10.1137/0207001 . ISSN 0097-5397 .
^ Huang, Xin; Lu, Pinyan (2021-07-18). "Ett algoritmiskt ramverk för att uppskatta maximal andel fördelning av sysslor" . Proceedings of the 22nd ACM Conference on Economics and Computation . EC '21. New York, NY, USA: Association for Computing Machinery: 630–631. arXiv : 1907.04505 . doi : 10.1145/3465456.3467555 . ISBN 978-1-4503-8554-1 .
^ ^a ^b Johnson, David S; Garey, Michael R (oktober 1985). "En 7160-sats för soppackning" . Journal of Complexity . 1 (1): 65–106. doi : 10.1016/0885-064X(85)90022-6 .
^ Yue Minyi; Zhang, Lei (juli 1995). "Ett enkelt bevis på olikheten MFFD(L) ≤ 71/60 OPT(L) + 1,L för MFFD bin-packing-algoritmen". Acta Mathematicae Applicatae Sinica . 11 (3): 318–330. doi : 10.1007/BF02011198 . S2CID 118263129 .

[johnson73-1] Johnson, David S (1973). "Nästan optimala bin packing algoritmer" (PDF) . Massachusetts Institute of Technology .

[Backer85-2] Baker, Brenda S. (1985). "Ett nytt bevis för den första anpassningsbara algoritmen för förpackning av fack". J. Algoritmer . 6 (1): 49–70. doi : 10.1016/0196-6774(85)90018-5 .

[3] Yue, Minyi (oktober 1991). "Ett enkelt bevis på ojämlikheten FFD (L) ≤ 11/9 OPT (L) + 1, ∀L för FFD bin-packing-algoritmen". Acta Mathematicae Applicatae Sinica . 7 (4): 321–331. doi : 10.1007/BF02009683 . S2CID 189915733 .

[4] Li, Rongheng; Yue, Minyi (augusti 1997). "Beviset på FFD(L) < -OPT(L) + 7/9". Kinesisk vetenskapsbulletin . 42 (15): 1262–1265. Bibcode : 1997ChSBu..42.1262L . doi : 10.1007/BF02882754 . S2CID 93280100 .

[Dosa07-5] Dósa, György (2007). "The Tight Bound of First Fit Minskande Bin-Packing Algoritm är FFD(I) ≤ 11/9OPT(I) + 6/9". Kombinatorik, algoritmer, probabilistiska och experimentella metoder. FLYKT . doi : 10.1007/978-3-540-74450-4_1 .

[:0-6] Coffman, Jr., EG; Garey, MR; Johnson, DS (1978-02-01). "En tillämpning av bin-packning till multiprocessor-schemaläggning" . SIAM Journal on Computing . 7 (1): 1–17. doi : 10.1137/0207001 . ISSN 0097-5397 .

[:3-7] Huang, Xin; Lu, Pinyan (2021-07-18). "Ett algoritmiskt ramverk för att uppskatta maximal andel fördelning av sysslor" . Proceedings of the 22nd ACM Conference on Economics and Computation . EC '21. New York, NY, USA: Association for Computing Machinery: 630–631. arXiv : 1907.04505 . doi : 10.1145/3465456.3467555 . ISBN 978-1-4503-8554-1 .

[JohnsonGarey19852-8] Johnson, David S; Garey, Michael R (oktober 1985). "En 7160-sats för soppackning" . Journal of Complexity . 1 (1): 65–106. doi : 10.1016/0885-064X(85)90022-6 .

[YueZhang19952-9] Yue Minyi; Zhang, Lei (juli 1995). "Ett enkelt bevis på olikheten MFFD(L) ≤ 71/60 OPT(L) + 1,L för MFFD bin-packing-algoritmen". Acta Mathematicae Applicatae Sinica . 11 (3): 318–330. doi : 10.1007/BF02011198 . S2CID 118263129 .