One-dimensional binpacking algorithm with relative costs

Question

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!

Answer 1

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.