Variable-Sized Bin Packing

Pack into bins of several sizes/costs to minimize total bin cost.

Also called: Variable-Sized Bin Packing · Variable Sized Bin Packing Problem · VSBPP · 가변 크기 빈 패킹

Definition

Given bin types of different sizes and costs, pack all items without overlap while minimizing the total cost (or area) of the bins used — choosing which sizes of bin to use, not just how many. Standard bin packing minimizes the number of identical bins; here the bin assortment is part of the decision.

Example

Suppose two bin types — A: capacity 10, cost 10; B: capacity 6, cost 7. To pack items totalling weight 14, one A is not enough. One A plus one B (capacity 16, cost 17) suffices and is cheaper than two A's (cost 20). Because the objective is cost, not bin count, stacking only the large bin is not always best.

Family

A cost-weighted variant of 2D Bin Packing; its choice among several stock types also connects it methodologically to 1D Cutting Stock.

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 2

variant of
Variable-Sized Bin Packing to 2D Bin Packing
Variable-sized bin packing is the bin-packing variant with bins of several sizes/costs, minimizing total bin cost rather than bin count — distinguished along the 'bin assortment' dimension of the Wäscher et al. typology.
EvidenceA · Peer-reviewed / official
Equiv.E1 · same base, different side constraints
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.
shares method with
Variable-Sized Bin Packing to 1D Cutting Stock
Variable-sized bin packing and 1D cutting stock share the structure of choosing among several stock/bin types at minimum cost, and both are addressed with pattern/configuration formulations.
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
variant of Variable-Sized Bin Packing to 2D Bin Packing	Variable-sized bin packing is the bin-packing variant with bins of several sizes/costs, minimizing total bin cost rather than bin count — distinguished along the 'bin assortment' dimension of the Wäscher et al. typology.	A · Peer-reviewed / official	E1 · same base, different side constraints	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.
shares method with Variable-Sized Bin Packing to 1D Cutting Stock	Variable-sized bin packing and 1D cutting stock share the structure of choosing among several stock/bin types at minimum cost, and both are addressed with pattern/configuration formulations.	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.