First-fit decreasing heuristic

As explained in Optimization Algorithms: AI techniques for design, planning, and control problems

A bin-packing heuristic that sorts objects by decreasing size before placing each object into the first available bin.

First-fit decreasing packs objects into bins by sorting them from largest to smallest, then placing each object in the first bin where it fits. Sorting improves utilization compared with preserving the original order. section 2.3

Packing six objects

With bin capacity 7 and object sizes 2, 4, 3, 6, 5, and 1, the total size is 21, so at least three bins are required. First-fit decreasing orders the objects as 6, 5, 4, 3, 2, 1 and packs them into three fully utilized bins, matching that lower bound. section 2.3

Figure 2.17 Handling the bin packing problem using first-fit and first-fit decreasing heuristics

Compare ordinary first-fit placement with first-fit decreasing placement in the bin-packing diagram. section 2.3

Use the heuristic with these practical cautions:

• Treat the result as a heuristic: ordering choices do not guarantee an optimal solution, and generalized layouts can remain infeasible or suboptimal. section 2.3
• Adapt the ordering rule when objects have width and height; smallest-first can place all five illustrated objects, while largest-first leaves one out. section 2.3

How Optimization Algorithms: AI techniques for design, planning, and control problems covers it

How deep it goes

Works through a capacity example and contrasts outcomes, but stops short of proving optimality or guaranteeing it.

Examples

Demonstrates sizes 2, 4, 3, 6, 5, and 1 in capacity-7 bins, achieving three fully utilized bins.

What it assumes

Assumes basic object sizes and bin capacity, then develops lower-bound reasoning through a concrete packing problem.

What you can do after

Apply the heuristic to organize objects, estimate a lower bound, and compare packing efficiency against alternative orderings.

How it connects

Connects bin packing with lower bounds, first-fit heuristics, brute-force search, and feasibility versus optimality.

liveBookmanning.com

Read Optimization Algorithms: AI techniques for design, planning, and control problems on liveBook Get the book at manning.com

Related concepts

• bin packing problemaddresses · A combinatorial problem of assigning objects with sizes to the fewest fixed-capacity bins without exceeding bin capacity.
• first-fit heuristicalternative to · A bin-packing heuristic that places objects in their given order into the first available bin without ordering them by size.

This explainer was generated by Manning's knowledge graph from the text of Optimization Algorithms: AI techniques for design, planning, and control problems. The section links point to the parts of the book it draws on.