1
$\begingroup$

I am investigating heuristics for optimising the packing a fixed number of knapsacks with a set of items of defined weights, however the knapsacks do not have a defined capacity limit. The objective of the optimisation is instead to find a configuration which minimises the difference in weights between the loaded knapsacks.

This differs from the traditional bin packing problem as it does not have an unlimited number of bins.

This seems to be a variant of the task scheduling problem, without a requirement for ordering.

Is there an existing name for this variant of the knapsack problem? Is it just the multiprocessor scheduling problem?

Thanks.

$\endgroup$
  • $\begingroup$ The number of bins is fixed in advance? If not, just put everything in the same bin and all bins (i.e., the only bin) contain the same weight of stuff. $\endgroup$ – David Richerby Nov 10 '16 at 9:36
  • $\begingroup$ Yes, this is equivalent to multiprocessor scheduling. Unfortunately that's NP-hard (as I recall there's a proof of this in Erik Demaine's MIT course notes). $\endgroup$ – j_random_hacker Nov 10 '16 at 13:25
  • $\begingroup$ To see weak NP-hardness, this can be reduced fairly easily to partition (in fact, partition is exactly this problem if you have two knapsacks). However, this problem is actually strongly NP-complete (if the number of machines is not a constant), which requires a standard, but slightly more involved reduction to 3-partition. $\endgroup$ – SamM Nov 10 '16 at 13:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.