Next-fit-minskande kärlförpackning

Next-fit-decreasing (NFD) är en algoritm för papperspackning . 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å papperskorgar som möjligt, men att minimera antalet papperskorgar är ett NP-hårt problem. NFD-algoritmen använder följande heuristik :

Beställ varorna från största till minsta.
Initiera en tom papperskorg och kalla den "öppen papperskorg".
För varje artikel i ordning, kontrollera om den får plats i den öppna papperskorgen:
- Om det passar, placera sedan det nya föremålet i det.
- Annars, stäng den aktuella behållaren, öppna en ny behållare och lägg den aktuella artikeln i den.

Kort sagt: NFD beställer artiklarna efter fallande storlek och anropar sedan nästa passande behållare .

Prestanda övre gräns

Baker och Coffman bevisade att, för varje heltal r , när storleken på alla föremål är som mest 1/ r , uppfyller det asymptotiska approximationsförhållandet för RFD

$R_{NFD}^{\infty }({\text{size}}\leq 1/r)=h_{\infty } (r)$ ,

där $h_{\infty }(r)$ är en sekvens vars första element är ungefär 1,69103, 1,42312, 1,30238. I synnerhet innebär det att ta r =1

$R_{NFD}^{\infty }=h_{\infty }(1)\approx 1,69103$ .

Senare har NFD även analyserats probabilistiskt.

Varianter

Next-Fit packar en lista och dess invers i samma antal papperskorgar. Därför har Next-Fit-Increasing samma prestanda som Next-Fit-Decreasing.

Next-Fit-Increasing presterar dock bättre när det finns allmänna kostnadsstrukturer.

^ Bagare, BS; Coffman, Jr., EG (1981-06-01). "En tight asymptotisk bindning för nästa passform-minskande bin-packning" . SIAM Journal om algebraiska och diskreta metoder . 2 (2): 147–152. doi : 10.1137/0602019 . ISSN 0196-5212 .
^ Csirik, J.; Galambos, G.; Frenk, JBG; Frieze, AM; Rinnooy Kan, AHG (1986-11-01). "En sannolikhetsanalys av nästa passforms heuristik för minskande behållare för packning" . Operations Research Letters . 5 (5): 233–236. doi : 10.1016/0167-6377(86)90013-1 . hdl : 1765/11645 . ISSN 0167-6377 .
^ Fisher, David C. (1988-12-01). "Next-fit packar en lista och dess baksida i samma antal papperskorgar" . Operations Research Letters . 7 (6): 291–293. doi : 10.1016/0167-6377(88)90060-0 . ISSN 0167-6377 .
^ Anily Shoshana; Bramel, Julien; Simchi-Levi, David (1994-04-01). "Wors-case-analys av heuristik för problem med papperskorgenpackning med allmänna kostnadsstrukturer" . Operationsforskning . 42 (2): 287–298. doi : 10.1287/opre.42.2.287 . ISSN 0030-364X .

[1] Bagare, BS; Coffman, Jr., EG (1981-06-01). "En tight asymptotisk bindning för nästa passform-minskande bin-packning" . SIAM Journal om algebraiska och diskreta metoder . 2 (2): 147–152. doi : 10.1137/0602019 . ISSN 0196-5212 .

[2] Csirik, J.; Galambos, G.; Frenk, JBG; Frieze, AM; Rinnooy Kan, AHG (1986-11-01). "En sannolikhetsanalys av nästa passforms heuristik för minskande behållare för packning" . Operations Research Letters . 5 (5): 233–236. doi : 10.1016/0167-6377(86)90013-1 . hdl : 1765/11645 . ISSN 0167-6377 .

[:0-3] Fisher, David C. (1988-12-01). "Next-fit packar en lista och dess baksida i samma antal papperskorgar" . Operations Research Letters . 7 (6): 291–293. doi : 10.1016/0167-6377(88)90060-0 . ISSN 0167-6377 .

[4] Anily Shoshana; Bramel, Julien; Simchi-Levi, David (1994-04-01). "Wors-case-analys av heuristik för problem med papperskorgenpackning med allmänna kostnadsstrukturer" . Operationsforskning . 42 (2): 287–298. doi : 10.1287/opre.42.2.287 . ISSN 0030-364X .