2 dimensional packing Problem with flexible objects

67 Views Asked by At

I have a kind of bin packing problem defined as follows: given: m bins $b_1,...,b_m$ of height $h_1,....,h_m$ and width w. The packing objects simply map $1,...,w$ to integers, hence these are functions $p_i$ with $0<i<n+1$. If $x_{ij}$ is a binary variable indicating that object i is assigned to bin j, then it must hold for all bins $b_j$ and all $0<k<w+1$ that $$\sum_{0<i<n+1} x_{ij} p_i(k) \le h_j.$$

The goal is to pack all the objects into the bins. One can assume that any $p_i$ does not have 'zero gaps' if we plot the function Graph with $1,...,w$ on the x-axis.

Any help in pointing towards the right papers and algorithms is appreciated.

Thanks Daniel