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.
The FFD algorithm works as follows.
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.
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.
The performance of FFD was analyzed in several steps. Below, denotes the number of bins used by FFD for input set S and bin-capacity C.
The lower bound example given in by Dósa is the following: Consider the two bin configurations:
If there are 4 copies of and 2 copies of in the optimal solution, FFD will compute the following bins:
That is, 8 bins total, while the optimum has only 6 bins. Therefore, the upper bound is tight, because .
This example can be extended to all sizes of : [5] in the optimal configuration there are 9k+6 bins: 6k+4 of type B1 and 3k+2 of type B2. But FFD needs at least 11k+8 bins, which is .
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
Contrary to intuition, is not a monotonic function of C. [7]: Fig.4 Similarly, 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 example, suppose the input is:
44, 24, 24, 22, 21, 17, 8, 8, 6, 6.
With capacity 60, FFD packs 3 bins:
But with capacity 61, FFD packs 4 bins:
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:
But with capacity 76, it needs 5 bins:
Consider the above example with capacity 60. If the 17 becomes 16, then the resulting packing is:
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:
This algorithm was first studied by Johnson and Garey [9] in 1985, where they proved that . This bound was improved in the year 1995 by Yue and Zhang [10] who proved that .
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.
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.
The FFD algorithm works as follows.
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.
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.
The performance of FFD was analyzed in several steps. Below, denotes the number of bins used by FFD for input set S and bin-capacity C.
The lower bound example given in by Dósa is the following: Consider the two bin configurations:
If there are 4 copies of and 2 copies of in the optimal solution, FFD will compute the following bins:
That is, 8 bins total, while the optimum has only 6 bins. Therefore, the upper bound is tight, because .
This example can be extended to all sizes of : [5] in the optimal configuration there are 9k+6 bins: 6k+4 of type B1 and 3k+2 of type B2. But FFD needs at least 11k+8 bins, which is .
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
Contrary to intuition, is not a monotonic function of C. [7]: Fig.4 Similarly, 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 example, suppose the input is:
44, 24, 24, 22, 21, 17, 8, 8, 6, 6.
With capacity 60, FFD packs 3 bins:
But with capacity 61, FFD packs 4 bins:
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:
But with capacity 76, it needs 5 bins:
Consider the above example with capacity 60. If the 17 becomes 16, then the resulting packing is:
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:
This algorithm was first studied by Johnson and Garey [9] in 1985, where they proved that . This bound was improved in the year 1995 by Yue and Zhang [10] who proved that .
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.