Next-fit-decreasing bin packing

Next-fit-decreasing (NFD) is an algorithm for bin packing. Its input is a list of items of different sizes. Its output is a packing - a partition of the items into bins of fixed capacity, such that the sum of sizes of items in each bin is at most the capacity. Ideally, we would like to use as few bins as possible, but minimizing the number of bins is an NP-hard problem. The NFD algorithm uses the following heuristic:

Order the items from largest to smallest.
Initialize an empty bin and call it the "open bin".
For each item in order, check if it can fit into the open bin:
- If it fits, then place the new item into it.
- Otherwise, close the current bin, open a new bin, and put the current item inside it.

In short: NFD orders the items by descending size, and then calls next-fit bin packing.

Performance upper bound

Baker and Coffman[1] proved that, for every integer r, when the size of all items is at most 1/r, the asymptotic approximation ratio of RFD satisfies

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

where $h_{\infty }(r)$ is a sequence whose first elements are approximately 1.69103, 1.42312, 1.30238. In particular, taking r=1 implies that

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

Later, NFD has also been analyzed probabilistically.[2]

Variants

Next-Fit packs a list and its inverse into the same number of bins. Therefore, Next-Fit-Increasing has the same performance as Next-Fit-Decreasing.[3]

However, Next-Fit-Increasing performs better when there are general cost structures.[4]

References

Baker, B. S.; Coffman, Jr., E. G. (1981-06-01). "A Tight Asymptotic Bound for Next-Fit-Decreasing Bin-Packing". SIAM Journal on Algebraic and Discrete Methods. 2 (2): 147–152. doi:10.1137/0602019. ISSN 0196-5212.{{cite journal}}: CS1 maint: multiple names: authors list (link)
Csirik, J.; Galambos, G.; Frenk, J.B.G.; Frieze, A.M.; Rinnooy Kan, A.H.G. (1986-11-01). "A probabilistic analysis of the next fit decreasing bin packing heuristic". 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 packs a list and its reverse into the same number of bins". 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). "Worst-Case Analysis of Heuristics for the Bin Packing Problem with General Cost Structures". Operations Research. 42 (2): 287–298. doi:10.1287/opre.42.2.287. ISSN 0030-364X.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Baker, B. S.; Coffman, Jr., E. G. (1981-06-01). "A Tight Asymptotic Bound for Next-Fit-Decreasing Bin-Packing". SIAM Journal on Algebraic and Discrete Methods. 2 (2): 147–152. doi:10.1137/0602019. ISSN 0196-5212.{{cite journal}}: CS1 maint: multiple names: authors list (link)

[2] Csirik, J.; Galambos, G.; Frenk, J.B.G.; Frieze, A.M.; Rinnooy Kan, A.H.G. (1986-11-01). "A probabilistic analysis of the next fit decreasing bin packing heuristic". 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 packs a list and its reverse into the same number of bins". 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). "Worst-Case Analysis of Heuristics for the Bin Packing Problem with General Cost Structures". Operations Research. 42 (2): 287–298. doi:10.1287/opre.42.2.287. ISSN 0030-364X.