As per my research on stack overflow communities, This is probably known as cutting stock problem / multiple Knapsack problem (a variant of the bin packing problem) which is NP hard.

here are the constraints:

  • lengths of variable sizes needs to be packed in bins of multiple sizes.
  • there are two integer arrays one has lengths (already defined), the other has the bin sizes (already defined), before computation starts.
  • lengths needs to be packed in any combination of bins (sizes are fixed and already defined), the desired solution will enlist ANY combination bins BUT total sum of empty space of all bins must be LEAST

Based on First Fit Decreasing (FFD) algorithm i am able to pack bin of A fixed size but to minimize the wastage need guidance how to utilize multiple bin sizes. Please Refer to an example scenario below it is obvious that one can get optimum results when mix size bins are used.

Example scenario Data:

Lengths: {2385,2385,2385,2385,2385,2385,1260,1260,1260,1260,1260,1260,337,337,210,210,125,125,108,108}
Bins: {3000,5000}

Results based on FFD algorithm of bin packing

When i use bin length of 3000 only the total wastage is 3434 Bin size 3000 wastage 3434 When i use bin length of 5000 only the total wastage is 1570 Bin size 5000 wastage 1570 When mix length bins (3000 and 5000) are used the total wastage is 570, the problem is what would be an optimum algorithm to achieve this or even better than this ? Bin size MULTIPLE wastage 570


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.