I use a special variant of BinPack problem. I use a naïve algorithm, atm, so I like to know how it might be called to do some initial research. Or does anyone know how to reduce this problem to something known?
The problem: There are items I and bins B in specific quantity and size.
|I| ∈ ℕ, |B| ∈ ℕ
s : (I ∪ B) → ℕ
The sum of all item-sizes is at least the size of the sum of all bins.
∑ _{i∈I} s(i) ≥ ∑ _{b∈B} s(b)
Each bin has to be filled with items or parts of items so that it is filled completely. s(b,i) is the size of that part of i that is in b, or 0 iff not.
∀ b ∈ B, i ∈ I: s(b,i) ∈ ℕ ∪ {0}
∀ i ∈ I: ∑ _{b∈B} s(b,i) ≤ s(i)
∀ b ∈ B: ∑ _{i∈I} s(b,i) ≥ s(b)
The goal is to minimize the number of item-parts needed to fill all bins.
numparts = |{ (b,i) ∈ B×I | s(b,i)>0 }|
find min(numparts)
Finally!
It is called bin packing with size preserving fragmentation (BP-SPF).
There exists this paper
Approximation Schemes for Packing with Item Fragmentation Omer Yehezkely (November 2006)