TransWikia.com

offline Bin Packing problem with multiple size bins

Computational Science Asked by mhk on June 4, 2021

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

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP