liveBook · Manning

First-fit heuristic

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

A bin-packing heuristic that places objects in their given order into the first available bin without ordering them by size.

The first-fit heuristic packs objects in their given order, placing each object into the first available bin without sorting by size. It is quick and simple, but may leave capacity unused. section 2.3

Six objects in bins of capacity seven

Objects sized 2, 4, 3, 6, 5, and 1 total 21, so three bins are the lower bound. First-fit uses four bins, while first-fit decreasing sorts by size and fits them into three fully utilized bins. section 2.3

Use first-fit when:

  • You need a fast, order-preserving packing rule rather than exhaustive search. section 2.3
  • You can accept that the resulting packing may be feasible but nonoptimal. section 2.3
  • You want to compare ordering strategies such as first-fit decreasing, smallest-first, or largest-first. section 2.3

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

How deep it goes
Defines the ordering rule and demonstrates its packing result, but does not provide a formal optimality guarantee.
Examples
Uses six objects in bins of capacity seven and contrasts four first-fit bins with three first-fit-decreasing bins.
What it assumes
Assumes object sizes and bin capacities; establishes the total-size lower bound through a worked calculation.
What you can do after
Apply a simple bin-packing rule and evaluate its capacity usage against alternative ordering heuristics.
How it connects
Connects bin packing with first-fit decreasing, smallest-first, largest-first heuristics, lower bounds, and brute-force search.
Cover of Optimization Algorithms: AI techniques for design, planning, and control problems
liveBookmanning.com
Read Optimization Algorithms: AI techniques for design, planning, and control problems on liveBook Get the book at manning.com

Related concepts

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.