# What algorithm to use for distribution of pieces

Hi am working for for a manufacturing company whose operation works in this manner

We get rolls of a material in a particular size our supplier lets say 8000 meteres per roll. Then we get orders from different customers of smaller sizes such as 2000 metres, 3000 metres etc. I am trying to develop a software for this and was wondering if there is any mathematical technique in which they simply input their current roll size and the different orders we have at the moment it can generate the best way to cut the different rolls so as to minimize the wastage.

For example at a particular point in time we may have the following orders 2 pieces of 3000 metres 2 pieces of 4000 metres 6 pieces of 1500 metres

Then all we should have to input is the above orders alongwith the roll size our supplier provides us for this example we assume its is 8000 metres.

Then the software should generate output such as Roll 1 - Two pieces of 4000 metres Roll Wasted 0 Roll 2 -Two pieces of 3000 metres and 1 piece of 1500 (Roll Wasted 500) Roll 3 - Five pieces of 15000 (Roll Wasted 500)

The script should be optimized as the above example is quite small. Typically we will have orders for about 200 pieces at a time

I know we can do this through brute force trying each combination. But are there any other sorting algorithms and techniques which can help in this case reducing the load on the computer.Currently we do this manually and it takes day for our staf

-
Doing this manually? Deary my. Just brute forcing would take less than an hour on a modern computer, especially with the help of some basic heuristics. –  nbubis Apr 28 '12 at 19:13
Just to formalize things: given a set $S$ of positive real numbers each less than some fixed number $x$, you wish to write $S$ as a union of subsets $S_i$ such that the sum $x_i$ of all the elements in the set $S_i$ is less than $x$, and you wish to do so in a manner that minimizes $$\sum_i (x - x_i).$$ –  user29743 Apr 28 '12 at 19:15
@nbubis I am a little skeptical of brute forcing but am not an expert on CS. He has to loop through all partitions of a finite set - I guess it's true he can throw out lots of them if he's careful. What is the run time? I'm not versed enough in combinatorics to say, but it looks like at least $O(2^{\#S})$, right? –  user29743 Apr 28 '12 at 19:17
@countinghaus - I assume customers aren't ordering small fractions, so that we can quantitize the values of $S$. additionally, the average size is probably a lot larger then that minimum. I'm not sure what the OP values are, but is seems that it should be feasible. –  nbubis Apr 28 '12 at 19:24

Your problem is know as Bin packing problem, the problem is NP-hard so I doubt, even for small number, that brute forcing can solve the problem.

A possible solution is build a combination of heuristics (like best first, as suggested by nbubis), pruning (eg. process the items in non-increasing order) and randomization (if your building process is not deterministic, you can repeat it several times, and take the best possible solution).

Another good heuristic is solving as subproblem the knapsack problem: try to fill the first roll, minimizing the wasted roll. If there is a relatively small number of possible cut (eg. every lenght is an interger number of meters, so the possible cut are 8000) this problem can be solved via dynamic programming (see wikipedia article) that is O(number of possible cut * number of items).

Another usefull thing is try to build a partial solution with some method, then take 2 roll in the partial solution with some wasted spaces (eg. 5000+2500 and 4500+1500+1500, both with 500 left) and try to rearrange them so the wasted space is maximized (in this case, 5000+1500+1500 and 4500+2500, the first one full and the other one with 1000 left), then maybe you can fill another item in the new bigger space, or you can re-do this process with the second roll and a new one, trying to increase the maximum wasted space, untill a new item can be placed there. This sub-problem can also be solved with knapsack's dynamic programming.

Other optimization can depends a lot on other proprety of the order that you receive, eg. if often the requested items are of the same sizes you may prefer write a sub-program for this particular problem, because different optimization can needed to find a solution for 100x73m + 100x550m than 200 items of random size. Or maybe you know that 90% of the items are between 550m and 450m, so you can prefer optimize the problem using that thing. Or that you have a lot of small pieces (10 m), so gaps can be easily filled. Or other peculiar thing in your problem, that can help build a better program for this particular problem.

I strongly suggest build a program for solve this problem, most of the times you can find an optimal solution by hand, but writing a program can save you time and every now and then a full roll.

-

Whilst there is a lot of interesting math behind bin packing problems, and many interesting algorithms that can get nearly-optimal solutions, in your case what you want is probably a simple heuristic that is 'good enough' nearly all the time.

I coded up a simple implementation of the first fit decreasing algorithm, which sorts the objects to be packed in descending order, and puts them into the first bin that they fit into. You can find the code at GitHub. It generates random objects between 0 and 4000 metres (in intervals of 100) and then applies the algorithm.

Output from a typical run looks like this:

Objects packed: 200
Bins used: 63
Space wasted: 2.0 percent
Time taken: 0.00 seconds


If you can handle 2% wastage and an algorithm that runs so fast that its running time is zero to 2 decimal places, then this may be the approach you need.

-

A basic heuristic:

1. Find the largest piece needed (say 5000).
2. Find the next largest piece that fits (say 2500).
3. Continue stage 2 until you there are no more room on the roll.

Send off the order and repeat.

-