One-dimensional binpacking algorithm with relative costs

2
votes

I'm wondering how to solve "One-dimensional binpacking problem with relative costs". We pack N volumes (with given sizes) into M bins (with given capacities) and have the matrix (NxM) of costs of each volume per each bin. So, the total cost should be minimized.

Can you advice any algorithm for solving this? Or, probably, any open-source lib for doing this?

Thanks!

1
algorithmoptimizationbin-packing
This sounds familiar... – shapiro yaacov
So there is no constraint of total size per assigned bin? – Codor
@Codor - there is a constraint on the size of bins (this is a follow up question) – shapiro yaacov

1 Answers

1
votes

If the problem under consideration is the generalized assignment problem, it is NP-hard but admits an approximation algorithm. From a brief look, the approximation ratio depends on the approximation ratio of an approximation algorithm for the knapsack problem, which in turn admits a fully polynomial time approximation scheme. In total. the generalized assignment problem also admits a fully polynomial time approximation scheme.