First-fit-decreasing bin packing

First-fit-decreasing (FFD) 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, so we use an approximately-optimal heuristic.

Description

The FFD algorithm works as follows.

Order the items from largest to smallest.
Open a new empty bin, bin #1.
For each item from largest to smallest, find the first bin into which the item fits, if any.
- If such a bin is found, put the new item in it.
- Otherwise, open a new empty bin put the new item in it.

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

An equivalent description of the FFD algorithm is as follows.

Order the items from largest to smallest.
While there are remaining items:
- Open a new empty bin.
- For each item from largest to smallest:
  - If it can fit into the current bin, insert it.

In the standard description, we loop over the items once, but keep many open bins. In the equivalent description, we loop over the items many times, but keep only a single open bin each time.

Performance analysis

The performance of FFD was analyzed in several steps. Below, $FFD(S,C)$ denotes the number of bins used by FFD for input set S and bin-capacity C.

In 1973, D.S. Johnson proved in his doctoral thesis^[1] that $FFD(S,C)\leq 11/9\mathrm {OPT} (S,C)+4$ for any instance S and capacity C.
In 1985, B.S. Backer^[2] gave a slightly simpler proof and showed that the additive constant is not more than 3.
Yue Minyi^[3] proved that $FFD(S,C)\leq 11/9\mathrm {OPT} (S,C)+1$ in 1991 and, in 1997, improved this analysis to $FFD(S,C)\leq 11/9\mathrm {OPT} (S,C)+7/9$ together with Li Rongheng.^[4]
In 2007 György Dósa^[5] proved the tight bound $FFD(S,C)\leq 11/9\mathrm {OPT} (S,C)+6/9$ and presented an example for which $FFD(S,C)=11/9\mathrm {OPT} (S,C)+6/9$ .

Worst-case example

The lower bound example given in by Dósa is the following: Consider the two bin configurations:

$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 \}$ .

If there are 4 copies of $B_{1}$ and 2 copies of $B_{2}$ in the optimal solution, FFD will compute the following bins:

4 bins with configuration $\{1/2+\varepsilon ,1/4+2\varepsilon \}$ ,
1 bin with configuration $\{1/4+\varepsilon ,1/4+\varepsilon ,1/4+\varepsilon \}$ ,
1 bin with configuration $\{1/4+\varepsilon ,1/4-2\varepsilon ,1/4-2\varepsilon ,1/4-2\varepsilon \}$ ,
1 bin with configuration $\{1/4-2\varepsilon ,1/4-2\varepsilon ,1/4-2\varepsilon ,1/4-2\varepsilon \}$ ,
1 one final bin with configuration $\{1/4-2\varepsilon \}$ ,

That is, 8 bins total, while the optimum has only 6 bins. Therefore, the upper bound is tight, because $11/9\cdot 6+6/9=72/9=8$ .

This example can be extended to all sizes of ${\text{OPT}}(S,C)$ :^[5] in the optimal configuration there are 9k+6 bins: 6k+4 of type B₁ and 3k+2 of type B₂. But FFD needs at least 11k+8 bins, which is ${\frac {11}{9}}(6k+4)+{\frac {6}{9}}$ .

Performance with divisible item sizes

An important special case of bin-packing is that which the item sizes form a divisible sequence (also called factored). A special case of divisible item sizes occurs in memory allocation in computer systems, where the item sizes are all powers of 2. In this case, FFD always finds the optimal packing.^[6]^: Thm.2

Monotonicity properties

Contrary to intuition, $FFD(S,C)$ is not a monotonic function of C. ^[7]^: Fig.4 Similarly, $FFD(S,C)$ is not a monotonic function of the sizes of items in S: it is possible that an item shrinks in size, but the number of bins increases.

However, the FFD algorithm has an "asymptotic monotonicity" property, defined as follows.^[7]^: Lem.2.1

For every instance S and integer m, let MinCap(S,m) be the smallest capacity C such that $OPT(S,C)\leq m$
For every integer m, let MinRatio(m) be the infimum of the numbers r≥1 such that, for all input sets S, $FFD(S,r\cdot {\text{MinCap}}(S,m))\leq m$ . This is the amount by which we need to "inflate" the bins such that FFD attains the optimal number of bins.
Then, for every input S and for every r ≥ MinRatio(m), $FFD(S,r\cdot {\text{MinCap}}(S,m))\leq m$ . This shows, in particular, that the infimum in the above definition can be replaced by minimum.

Examples

For example, suppose the input is:

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

With capacity 60, FFD packs 3 bins:

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

But with capacity 61, FFD packs 4 bins:

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

This is because, with capacity 61, the 17 fits into the first bin, and thus blocks the way to the following 8, 8.

As another example,^[8]^{: Ex.5.1} suppose the inputs are: 51, 28, 28, 28, 27, 25, 12, 12, 10, 10, 10, 10, 10, 10, 10, 10. With capacity 75, FFD packs 4 bins:

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

But with capacity 76, it needs 5 bins:

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

Consider the above example with capacity 60. If the 17 becomes 16, then the resulting packing is:

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

Modified first-fit-decreasing

Modified first fit decreasing (MFFD)^[9] improves on FFD for items larger than half a bin by classifying items by size into four size classes large, medium, small, and tiny, corresponding to items with size > 1/2 bin, > 1/3 bin, > 1/6 bin, and smaller items respectively. Then it proceeds through five phases:

Allot a bin for each large item, ordered largest to smallest.
Proceed forward through the bins. On each: If the smallest remaining medium item does not fit, skip this bin. Otherwise, place the largest remaining medium item that fits.
Proceed backward through those bins that do not contain a medium item. On each: If the two smallest remaining small items do not fit, skip this bin. Otherwise, place the smallest remaining small item and the largest remaining small item that fits.
Proceed forward through all bins. If the smallest remaining item of any size class does not fit, skip this bin. Otherwise, place the largest item that fits and stay on this bin.
Use FFD to pack the remaining items into new bins.

This algorithm was first studied by Johnson and Garey^[9] in 1985, where they proved that $MFFD(S,C)\leq (71/60)\mathrm {OPT} (S,C)+(31/6)$ . This bound was improved in the year 1995 by Yue and Zhang^[10] who proved that $MFFD(S,C)\leq (71/60)\mathrm {OPT} (S,C)+1$ .

Other variants

Best-fit-decreasing (BFD) is very similar to FFD, except that after the list is sorted, it is processed by best-fit bin packing. Its asymptotic approximation ratio is the same as FFD - 11/9.

Implementations

Python: The prtpy package contains an implementation of first-fit decreasing.

References

^ Johnson, David S (1973). "Near-optimal bin packing algorithms" (PDF). Massachusetts Institute of Technology.
^ Baker, Brenda S. (1985). "A New Proof for the First-Fit Decreasing Bin-Packing Algorithm". J. Algorithms. 6 (1): 49–70. doi:10.1016/0196-6774(85)90018-5.
^ Yue, Minyi (October 1991). "A simple proof of the inequality FFD (L) ≤ 11/9 OPT (L) + 1, ∀L for the FFD bin-packing algorithm". Acta Mathematicae Applicatae Sinica. 7 (4): 321–331. doi:10.1007/BF02009683. S2CID 189915733.
^ Li, Rongheng; Yue, Minyi (August 1997). "The proof of FFD(L) < -OPT(L) + 7/9". Chinese Science Bulletin. 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 Decreasing Bin-Packing Algorithm is FFD(I) ≤ 11/9OPT(I) + 6/9". In Chen Bo; Mike Paterson; Zhang Guochuan (eds.). Combinatorics, Algorithms, Probabilistic and Experimental Methodologies. First International Symposium, ESCAPE 2007, Hangzhou, China, April 7–9, 2007. Lecture Notes in Computer Science. Vol. 4614. pp. 1–11. doi:10.1007/978-3-540-74450-4_1. ISBN 978-3-540-74449-8.
^ Coffman, E. G; Garey, M. R; Johnson, D. S (1987-12-01). "Bin packing with divisible item sizes". Journal of Complexity. 3 (4): 406–428. doi:10.1016/0885-064X(87)90009-4. ISSN 0885-064X.
^ ^a ^b Coffman, E. G. Jr.; Garey, M. R.; Johnson, D. S. (1978-02-01). "An Application of Bin-Packing to Multiprocessor Scheduling". SIAM Journal on Computing. 7 (1): 1–17. doi:10.1137/0207001. ISSN 0097-5397.
^ Huang, Xin; Lu, Pinyan (2021-07-18). "An Algorithmic Framework for Approximating Maximin Share Allocation of Chores". Proceedings of the 22nd ACM Conference on Economics and Computation. EC '21. New York, NY, USA: Association for Computing Machinery. pp. 630–631. arXiv:1907.04505. doi:10.1145/3465456.3467555. ISBN 978-1-4503-8554-1. S2CID 195874333.
^ ^a ^b Johnson, David S; Garey, Michael R (October 1985). "A 7160 theorem for bin packing". Journal of Complexity. 1 (1): 65–106. doi:10.1016/0885-064X(85)90022-6.
^ Yue, Minyi; Zhang, Lei (July 1995). "A simple proof of the inequality MFFD(L) ≤ 71/60 OPT(L) + 1,L for the MFFD bin-packing algorithm". Acta Mathematicae Applicatae Sinica. 11 (3): 318–330. doi:10.1007/BF02011198. S2CID 118263129.

[johnson73-1] Johnson, David S (1973). "Near-optimal bin packing algorithms" (PDF). Massachusetts Institute of Technology.

[Backer85-2] Baker, Brenda S. (1985). "A New Proof for the First-Fit Decreasing Bin-Packing Algorithm". J. Algorithms. 6 (1): 49–70. doi:10.1016/0196-6774(85)90018-5.

[3] Yue, Minyi (October 1991). "A simple proof of the inequality FFD (L) ≤ 11/9 OPT (L) + 1, ∀L for the FFD bin-packing algorithm". Acta Mathematicae Applicatae Sinica. 7 (4): 321–331. doi:10.1007/BF02009683. S2CID 189915733.

[4] Li, Rongheng; Yue, Minyi (August 1997). "The proof of FFD(L) < -OPT(L) + 7/9". Chinese Science Bulletin. 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 Decreasing Bin-Packing Algorithm is FFD(I) ≤ 11/9OPT(I) + 6/9". In Chen Bo; Mike Paterson; Zhang Guochuan (eds.). Combinatorics, Algorithms, Probabilistic and Experimental Methodologies. First International Symposium, ESCAPE 2007, Hangzhou, China, April 7–9, 2007. Lecture Notes in Computer Science. Vol. 4614. pp. 1–11. doi:10.1007/978-3-540-74450-4_1. ISBN 978-3-540-74449-8.

[6] Coffman, E. G; Garey, M. R; Johnson, D. S (1987-12-01). "Bin packing with divisible item sizes". Journal of Complexity. 3 (4): 406–428. doi:10.1016/0885-064X(87)90009-4. ISSN 0885-064X.

[:0-7] Coffman, E. G. Jr.; Garey, M. R.; Johnson, D. S. (1978-02-01). "An Application of Bin-Packing to Multiprocessor Scheduling". SIAM Journal on Computing. 7 (1): 1–17. doi:10.1137/0207001. ISSN 0097-5397.

[:3-8] Huang, Xin; Lu, Pinyan (2021-07-18). "An Algorithmic Framework for Approximating Maximin Share Allocation of Chores". Proceedings of the 22nd ACM Conference on Economics and Computation. EC '21. New York, NY, USA: Association for Computing Machinery. pp. 630–631. arXiv:1907.04505. doi:10.1145/3465456.3467555. ISBN 978-1-4503-8554-1. S2CID 195874333.

[JohnsonGarey19852-9] Johnson, David S; Garey, Michael R (October 1985). "A 7160 theorem for bin packing". Journal of Complexity. 1 (1): 65–106. doi:10.1016/0885-064X(85)90022-6.

[YueZhang19952-10] Yue, Minyi; Zhang, Lei (July 1995). "A simple proof of the inequality MFFD(L) ≤ 71/60 OPT(L) + 1,L for the MFFD bin-packing algorithm". Acta Mathematicae Applicatae Sinica. 11 (3): 318–330. doi:10.1007/BF02011198. S2CID 118263129.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]