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.

what's the smallest order size and how many partial rolls can you store before wasting? — Bradley
– Bradley, Commented May 7, 2012 at 21:00

Li-aung Yip · Accepted Answer · 2012-04-28 19:51:08Z

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.

edited Apr 28, 2012 at 19:51

answered Apr 28, 2012 at 19:08

Li-aung Yip

12.5k5 gold badges36 silver badges51 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

Cybercartel Over a year ago

Downvote from me because cutting stock problem is more 2d related.

Li-aung Yip Over a year ago

@David: uhh..... have you read the Wikipedia description of the cutting stock problem? The cutting stock problem is exactly the problem the OP is trying to solve.

Cybercartel Over a year ago

Cool. You can write it for him? Also did you downvote my answer for the tsp question a while ago?

Li-aung Yip Over a year ago

@David: Why are you being so adversarial? And no, I didn't downvote any of your answers recently. (Downvoting is not a tool for revenge.)

Cybercartel Over a year ago

I don't need to read the wikipedia article because I wrote such a thing and I won a prize. But you are right I deleted my answer.

|

Cybercartel · Accepted Answer · 2012-04-28 19:06:55Z

0

You are looking for a 1d bin-packing algorithm. There are many strategies to solve it First-Fit, Best-Fit, Random-Fit. I've wrote a php solution at phpclasses.org. You can download my program for free (bin-packing). In fact I've won a prize for it. If your problem isn't so big I would try a brute-force method.

answered Apr 28, 2012 at 19:06

Cybercartel

12.6k7 gold badges39 silver badges73 bronze badges

2 Comments

Li-aung Yip Over a year ago

Not quite bin packing - bin packing is when all the bins (or rolls, in this case) are the same size. Cutting-stock is the more general problem.

Cybercartel Over a year ago

@Li-aung-Yip: Maybe. Aren't the rolls not the same length? I doubt that and also I wrote 1d problem which is exactly what OP asked?

Collectives™ on Stack Overflow

What algorithm to use for distribution of pieces

2 Answers 2

6 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

6 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related