What algorithm to use for distribution of pieces

Question

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 was wondering how I should go about creating a software 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 am looking at doing this in PHP and MYSQL so it can be web based and people around the company can utilize it.

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.

Answer 1

This is the well-known cutting stock problem, where you want to minimise the waste after all orders are fufilled.

Here's how Wikipedia describes it:

The cutting-stock problem is an optimization problem, or more specifically, an integer linear programming problem. It arises from many applications in industry. Imagine that you work in a paper mill and you have a number of rolls of paper of fixed width waiting to be cut, yet different customers want different numbers of rolls of various-sized widths. How are you going to cut the rolls so that you minimize the waste (amount of left-overs)?

The general case is NP-hard, which means that there is no fast algorithm to produce the optimal result.

However you can write an algorithm that produces approximate solutions that are fast to calculate and "reasonably" good.

---

Edit (courtesy @David):

If the original rolls you get from the manufacturer are always the same size, in this case 8,000 metres, then the cutting-stock problem is reduced to the 1D bin packing problem, which is a little bit easier to solve (but still NP-hard.)

Greedy solutions, as proposed by @David in his deleted answer, are a fast and cheap way of getting an approximate solution.

---

Edit 2:

I mis-spoke slightly. There is no known polynomial time approximation scheme for the bin-packing problem. The greedy algorithm is actually pretty alright, though.