Search code examples
algorithmpackingchunks

Packing differently sized chunks of data into multiple bins

EDIT: It seems like this problem is called "Cutting stock problem"

I need an algorithm that gives me the (space-)optimal arrangement of chunks in bins. One way would be put the bigger chunks in first. But see how that algorithm fails in this example:

Chunks        Bins
-----------------------------
AAA BBB CC DD (       ) (   )

Algorithm     Result
-----------------------------
biggest first (AAABBB ) (CC )
optimal       (AAACCDD) (BBB)

"Biggest first" can't fit in DD. Maybe it helps to build a table like this:

Size 1: ---
Size 2: CC, DD
Size 3: AAA, BBB

Size 4: CCDD
Size 5: AAACC, AAADD, BBBCC, BBBDD
Size 6: AAABBB

Size 7: AAACCDD, BBBCCDD
Size 8: AAABBBCC, AAABBBDD
Size 10: AAABBBCCDD
Solution

  • This is basically a variant of the bin-packing problem. This problem is is known to be NP-hard, so don't expect to find an efficient optimal algorithm for complex cases (i.e. with many objects and bins).

    However, if your number of objects/bins is relatively small, you will probably be fine just exhaustively searching all the possible combinations with a depth-first search.

    This is pretty easy to implement: just take the first object, then recursively re-run the algorithm with the first object placed in each of the bins in turn (i.e. subtracting the size of the object from the available bin space). Finally, you just need to keep track of the best "solution" found so far and return this as your final answer once you have tried all combinations.

    You may also be able make this algorithm algorithm run faster by:

    • Considering all objects of equal size as equivalent
    • Pruning the search tree (i.e. returning early from a branch) if you can't possibly beat the current best solution e.g. when you have already found a perfect fit

    Updated based on comments on problem size

    Given that it looks like you have a very large number of chunks to deal with, you might want to try the following:

    • Fit the largest 10-20 chunks using an exhaustive search as above
    • Allocate the remainder using a largest fit approach