First-Fit Decreasing

Sort items largest-first, then place each in the first fitting bin.

Also called: First-Fit Decreasing · FFD · 퍼스트핏 감소

A bin packing heuristic that sorts items by decreasing size, then places each item into the first open bin it fits (opening a new bin if none fit). Known for classic approximation-ratio analysis, and used as a starting point for 2D/orthogonal variants.

Claims & evidence

Every relationship is a claim with an evidence grade; applicable problem-to-problem relationships also carry an equivalence level. See the evidence policy.

A–X describes evidence reliability; E0–E4 describes mathematical similarity between problems. The two axes are independent.

Relationships from this entry 1

shares method with
First-Fit Decreasing to Bottom-Left Fill
First-fit-decreasing and bottom-left-fill are both constructive placement heuristics that place items one by one under a fixed rule.
EvidenceB · Survey / tutorial / community
Equiv.E3 · structural analogy
Sources
- Source grade: A — Peer-reviewed / officialAn improved typology of cutting and packing problems
  Citation details
  Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.

Relationships from this entry
Relationship	Claim	Evidence	Equiv.	Sources
shares method with First-Fit Decreasing to Bottom-Left Fill	First-fit-decreasing and bottom-left-fill are both constructive placement heuristics that place items one by one under a fixed rule.	B · Survey / tutorial / community	E3 · structural analogy	Source grade: A — Peer-reviewed / officialAn improved typology of cutting and packing problems Citation details Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.

Relationships to this entry 2

uses method
2D Bin Packing to First-Fit Decreasing
First-fit-decreasing (FFD) style constructive heuristics are widely used for fast approximate bin packing.
EvidenceB · Survey / tutorial / community
Sources
- Source grade: A — Peer-reviewed / officialTwo-dimensional packing problems: A survey
  Citation details
  Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.
uses method
2D Strip Packing to First-Fit Decreasing
Level-based first-fit-decreasing rules (e.g. FFDH) are classic constructive heuristics for strip packing.
EvidenceB · Survey / tutorial / community
Sources
- Source grade: A — Peer-reviewed / officialTwo-dimensional packing problems: A survey
  Citation details
  Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.

Relationships to this entry
Relationship	Claim	Evidence	Equiv.	Sources
uses method 2D Bin Packing to First-Fit Decreasing	First-fit-decreasing (FFD) style constructive heuristics are widely used for fast approximate bin packing.	B · Survey / tutorial / community	—	Source grade: A — Peer-reviewed / officialTwo-dimensional packing problems: A survey Citation details Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.
uses method 2D Strip Packing to First-Fit Decreasing	Level-based first-fit-decreasing rules (e.g. FFDH) are classic constructive heuristics for strip packing.	B · Survey / tutorial / community	—	Source grade: A — Peer-reviewed / officialTwo-dimensional packing problems: A survey Citation details Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.