Algorithm to maximise raw material 1

[TimPen]

I have a piece of string which I need to cut into lengths.
I need to determine the the number of cuts per lenght to minimise waste

Say the length of the string is 100mm

Example 1
I need lengths of 40mm, 20mm
I would cut 2 of 40mm & 1 of 20mm

Example 2
I need lengths of 30mm
I would cut 3 of 30mm and have 10mm waste

I never know how many lenght variables there may be

How can I do this in a module?

Thanks in advance

 

[SkipVought]

Hi,

What logic have you tried?

Skip,
[sub]
Just traded in my old subtlety...
for a NUANCE![/sub]

 

[dhookom]

You might be able to do this with SQL.
Create a table of numbers tblNums with a single numeric field Num and add values 1 - whatever.
[tt][blue]
tblNums
--------------
Num (values 1, 2, 3,...)
[/blue][/tt]

Create a table of string lengths:
[tt][blue]
tblStringLength
--------------
Num (values 20,40, ...)
[/blue][/tt]

Then create a cartesian query with as many copies of these two tables as there are records in tblStringLength:

SELECT tblNums.Num AS Num1, tblStringLength.StringLength AS Length1, tblNums_1.Num AS Num2, tblStringLength_1.StringLength AS Length2, [tblNums].[Num]*[tblStringLength].[StringLength]+[tblNums_1].[Num]*[tblStringLength_1].[StringLength] AS TotLength
FROM tblNums, tblStringLength, tblStringLength AS tblStringLength_1, tblNums AS tblNums_1
WHERE (((tblStringLength.StringLength)<>[tblStringLength_1].[StringLength]) AND (([tblNums].[Num]*[tblStringLength].[StringLength]+[tblNums_1].[Num]*[tblStringLength_1].[StringLength])<=100))
ORDER BY [tblNums].[Num]*[tblStringLength].[StringLength]+[tblNums_1].[Num]*[tblStringLength_1].[StringLength] DESC;

With 40 and 20 in the table, I get:
[tt]
Num1 Length1 Num2 Length2 TotLength
1 40 3 20 100
1 20 2 40 100
3 20 1 40 100
2 40 1 20 100
1 40 2 20 80
2 20 1 40 80
1 20 1 40 60
1 40 1 20 60
[/tt]




Duane
Hook'D on Access
MS Access MVP

 

[MajP]

You need to better describe what you start with and how this would be used. Your title hints at some kind of optimization model, but your examples are purely deterministic. Something is missing in your description. There are optimization models for something like:
"I have 20 ropes with different lengths (25mm, 25mm, 50mm, 100mm, 100mm, 200mm,...)
and I need lenghts cut of
(20,20,30,30,40, 100,150,...)
Determine the ropes to cut and how to cut them."
That would be a fitting optimization model.

But your example is not an optimization just a plain math problem
lengths: 100mm
and need 3@30
remainder is 10

You can do that with a function,if that is what you want? What information gets passed to the function and what would you like returned. Is this information in a database, or did you mistakenly place it in this forum. So if you have all your lengths in a database you could run the function against every record and return the lengths were the remainder is minimized. Need more info first.

 

[SkipVought]

Real world: extrusion, bar, board, bolt, sheet. Might also include test coupon length, chucking length

Academic world: string

???

Skip,
[sub]
Just traded in my old subtlety...
for a NUANCE![/sub]

 

[TimPen]

Hi MajP

You are 100% correct. I need a fitting optimization model as you described!

Here is a real example:

The string is 2440mm in length

It first needs to cut it into lengths of 442mm
This will give 5 lengths of 442mm, with 430mm left over.

The other lengths that need to cut are 142mm & 100mm

I need to figure out how to cut the 430mm piece to minimise waste.

I could cut:
* 4 pieces of 100mm and have 30mm waste
* 2 pieces of 142mm and 1 piece of 100mm and have 16mm waste
* 3 pieces of 142mm and have 4mm waste

Obviously the last is best!

Hope this makes sense

thanks

 

[SkipVought]

Unless you have DIFFERENT units of measure in the values given, 1) including the unit of measure in each transaction is totally superfluous and annoying and 2) units of measure ought not to be part of the value, but a separate parameter.

Sure 'sounds' like a classroom problem to me.

Skip,
[sub]
Just traded in my old subtlety...
for a NUANCE![/sub]

 

[dhookom]

I just used my suggested SQL solution and it returned:
[TT]
Num1 Length1 Num2 Length2 TotLength
0 100 3 142 426
3 142 0 100 426
4 100 0 142 400
0 142 4 100 400
2 142 1 100 384
1 100 2 142 384
2 100 1 142 342
1 142 2 100 342
3 100 0 142 300
0 142 3 100 300
0 100 2 142 284
2 142 0 100 284
1 142 1 100 242
1 100 1 142 242
0 142 2 100 200
2 100 0 142 200
1 142 0 100 142
0 100 1 142 142
1 100 0 142 100
0 142 1 100 100
0 142 0 100 0
0 100 0 142 0
[/TT]

Duane
Hook'D on Access
MS Access MVP

 

[MajP]

Sorry. Your examples do not really help in defining a generic problem. Here is my guess.
1) You only ever have one thing that can be cut. It is not like you have one string of 2440 and one of 3000 and one of 1000 and you have to figure out the best one to cut. If you can pick from many strings to cut this problem is much more complex.
2) The cuts can be of one or more sizes, and not all sizes have to be cut
2440 @ 442 : only provide one size to cut
430 @ 142 or 100: can be all 142 pieces, all 100 pieces, or combination of 142/100

Can there be more than two possible sizes to cut?
You show the input into the second round of cutting on the remainder of 430 (input is 142,100). Is this a second problem or do expect to pass this input into the original algorithm. In other words, after the first cut do you expect to show the user the remainder and have them provide inputs for the subsequent cuts? Or do you expect to provide the function/model all the possible sizes to cut up front? If so what are the rules?

Please provide more information on how you input the parameters, where and how to store results, and rules for cutting.

 

[MajP]

Still not sure what you really need and what are the inputs or how complex the real world problem is. But this type of model is known as a "cutting-stock" problem in the real world. Your problem may be far simpler if you are not providing all the required cuts up front, and if you are only cutting from a single piece.

Here is a real world example, but can be solved in Excel using the Optimizer add-in (I think it solves integer models).

http://en.wikipedia.org/wiki/Cutting_stock_problem

 

[TimPen]

Hi MajP

You have hit the nail on the head! Many thanks. The wiki article explains what I want

Now I need to find an Access module that does just this!

Any ideas where I can find one.
I am also happy to contribute towards it

 

[MajP]

Access is unlikely to have a dedicated module because solving linear/non linear programs is not a traditional database usage. However, Excel does come with a simple solver that can handle linear programs and specifically integer models like you describe. Depending on the complexity of your model will determine if the standard solver can handle it. There are more advanced add-ins to Excel to handle more complex linear/non-linear models. Insight, WhatsBest, AdvancedSolver, Solver Table, etc.
So you could query your database from Excel and code a model, or you could do it the other way and automate Excel from Access. There are probably a handful of people who know how to code optimization models in Access, and you are talking to one of them. So I would be interested in helping, but you need to provide as much detail as possible to explain the inputs, desired user interaction, source data, desired outputs, etc. Need first to determine if in fact the problem can/needs to be solved with a linear integer program.

 

[TimPen]

I manufacture wooden box’s and need to create a production order for the factory. The production order needs to include a cutting schedule so that the wood is cut to maximise usage (minimise waste)

A box essentially contains 4 components. 2 sides, 2 lengths, 1 base and 1 lid. (The base and lid can be different dimensions)

What I manually do is:
* calculate the width of each component. (I need to allow for saw blade thickness etc.)
* I know the dimensions of the board that will be used to manufacture the box. (the board dimensions can change for each box / component).
* In the factory the board is first cut into strips the width of each component. So I calculate the number of strips required by dividing the board length by the component length and multiply this with the numbers of boxes to manufacture. This tells me how many boards I require to produce that component
* This process gets repeated for each component of the box.

Whilst this works, it is not the most efficient because there are always offcuts at the end of each strip. If two, or more, components have the same width I should be using these offcuts! They do this in the factory, but I don’t do this in my costings so I sometimes loose orders on price.

In Access, I have a form in which I enter the dimensions of each component. I also enter the required number of boxes. So I know the exact dimensions and required number of components to complete the order.

Pertinent information that I would need to pass to a function would include:
QuotationId (so I know what data belongs to what quotation!)
Board Length
Strip Width
Component Length & Number of Components required (this can be variable from a single component to multiple components

I know need to determine the most optimum usage of the board. So I need to know:
• How many strips do I need to cut
• How do I cut each strip into the various component lengths

I would like to write this information to a table. The fields in the table would include:
QuotationId
StripNumber
StripWidth
ComponentLength
NumberOfComponents

For example:
StripNumber StripWidth ComponentLength NumberOfComponents
1 100 442 5
1 100 142 1
2 147 447 5
3 147 447 5
etc

Ideally the user would only need to enter the dimensions of the various components. The results will be returned to the user either in a form or report.

Hope this is sufficient
Many thanks

 

[MajP]

OK still trying to fully understand. It may take a while. Also a lot of times when trying to answer a question like this, the poster comes back and says "well actually that was just a simple example, in reality it is more complicated ..." This causes you to go back to the drawing board and come up with a complete different approach.

1) are all the strips the same length? In other words are they ripping it from a stock of a specified length (i.e. 4x8)and you get the full length? If so what is that length? Or can you choose the length?
2) Are you concerned about maximizing how the boards are ripped in the factory? Or is that their issue?
3) Are you placing multiple orders of different size boxes, or just lots of the same size boxes at any one time?
4) Are you tracking your leftovers in your database? Once you make your boxes and you have left over stock, do you need to query what you have locally before ordering? Obviously far more complicated algorithm.
5) Can the direction be rotated? Or does grain direction matter? if the box sides are 1 ft high by 3 ft long can the strip be 3 ft wide and then cut into 1 ft sections or does it need to be 1 ft wide and cut into 3 ft sections? If this can be rotated obviously the complexitiy of the solution goes up.

If you can provide a realistic simple example using real measurements, how the strips would get cut (dimensions), and how you would cut it, and what waste you would have, that may clear things up. If you can provide a diagram of this that would even be better.

If the choices are limited, the amount of possibilities limited, you may be able to code a solution to iterate all possibilities without having to go to a complex solver. I just have to really understand the whole problem to do that. So I will probably ask a lot more questions.
With some optimization the possible outcomes are infinite or so large that you cannot iterate all possibilities in a reasonable time/resources. This may or may not be the case.

 

[MajP]

http://www.ams.jhu.edu/~castello/362/Handouts/CuttingStockExample.pdf

Here is an example of how to model in Excel. The trick would be writing the code to format the model first.

 

[TimPen]

Many thanks
Answers at end of each question

1) are all the strips the same length? In other words are they ripping it from a stock of a specified length (i.e. 4x8)and you get the full length? If so what is that length? Or can you choose the length? Yes the are the same length. I will need to pass the length to you.

2) Are you concerned about maximizing how the boards are ripped in the factory? Or is that their issue? Yes I am. Ideally I don't want to leave any decisions to the factory!

3) Are you placing multiple orders of different size boxes, or just lots of the same size boxes at any one time? Lots of the same size.

4) Are you tracking your leftovers in your database? Once you make your boxes and you have left over stock, do you need to query what you have locally before ordering? Obviously far more complicated algorithm. Would be nice to have, but no.

5) Can the direction be rotated? Or does grain direction matter? if the box sides are 1 ft high by 3 ft long can the strip be 3 ft wide and then cut into 1 ft sections or does it need to be 1 ft wide and cut into 3 ft sections? If this can be rotated obviously the complexitiy of the solution goes up. Direction cannot be changed. The strip width is always against the grain, and the component length is always with the grain.

If you can provide a realistic simple example using real measurements, how the strips would get cut (dimensions), and how you would cut it, and what waste you would have, that may clear things up. If you can provide a diagram of this that would even be better. Example file attached

If the choices are limited, the amount of possibilities limited, you may be able to code a solution to iterate all possibilities without having to go to a complex solver. I just have to really understand the whole problem to do that. So I will probably ask a lot more questions.
With some optimization the possible outcomes are infinite or so large that you cannot iterate all possibilities in a reasonable time/resources. This may or may not be the case.

 

[MajP]

I will need to digest the Spread Sheet but that helps a lot. Still trying to visualize. A couple of notes.

1) There is a ton of software out there for commercial and hobbyists that does stock cut optimization. I was kind of suprised about how much there is. Most seem to be in the 160-180 range.
Here is one and you can demo the free version. It is too limited for your use because you can only do 100 total cuts

http://www.astrokettle.com/pr1dsc.html

However instead of doing 400 boxes I ran it doing 20 boxes for your first example. And it gives you this mix
4 @ 442,442,442,442,442,142 waste 88
1 @ 142,142,142,142,142,142,142,142,142,142,142,142,142,142,142,142 waste 168
It actually provides this information in a table that could then get input into access for tracking of orders. I am not advocating anything since there are lots of others, but the freeware was user freindly and has lots of options.

You may want to look for other freeware as well. Google "Stock Cut optimizer, Cutting Stock, 1d Stock Cutting, 2d Stock Cutting, etc.

2) Most software handles a 1d problem or a 2d problem. A 1D problem is like ordering rebar where you are cutting a bar to specific lengths. The only concern in the pattern is which lengths to cut. The 2D problems are like in a glass/mirror shop where you are cutting patterns out of a sheet. 3D would be like cutting shapes out of foam blocks.

3) If I understand your problem it may be a hybrid of a 2d and 1d adding some complexity. 2D in that you are picking a combination of strip sizes and 1D in the cutting of the strips. (It appears you are currently not doing that, but if you mixed orders where you have different widths of strips).

4)Most solutions and algorithms (both theoretical and practical) start with defining all feasible patterns. A feasible pattern is one where the amount of leftover is smaller then the samallest piece required to cut. A lot of generic optimizers like Excel require you have to figure this out in order to formulate the problem. That could be pretty complicated by itself. So if I was doing this using Excel I would write the code to have a basic input screen and then it would formulate the problem by enumerating the feasible patterns. Obviously the dedicated software does this for you. The algorithms then minimizes the waste by figuring out the correct combination of feasible patterns.

In order to visualize how you do this I will asks questions on the first order
LENGTH WIDTH HEIGHT #boxes
420 120 85 440

1)It appears that strips are cut from a board of 2440 X 1220?
(or an 8'X4' sheet of plywood/laminate)

2)You show strip widths of 100 and 147. Where does that come from?
Is 100, 85 for the box ht plus some buffer. Is 147 for the base and top the width of the box plus some overlap?

3) I assume the strips are ripped like this
long way (giving you strips that are 100/147 wide by 2440 long)

1220
___________
| | | |
| | | |
| | | |
| | | |
| | | | 2440
| | | |
| | | |
| | | |
| | | |
-----------

4)The sides, base and lid are all cut from seperate stock and not interchangeable due to different thickness of stock? That appears to simplify things a whole lot. If that is the case then you are only optimizing the sides. It is a 1D problem. Only trying to determine the mix of long and short sides on a pattern.

All tops (or bottoms) get cut out of their own piece of stock. you do not have a lot of choices (unless you can mix with a later order). You have to rip enough strips to make your tops and your stuck with whatever waste you have after cutting.

I was originally thinking that tops, bottoms, and sides all could be cut from the same stock, and you could mix orders. That would be orders of magnitude more complicated.

5)How is strip cut size determined? I am assuming you start with a strip of 2440 (or 1220 depending on direction you rip) and then cut it down. But in the first example the long side is cut to 442
and you get 5. Is 442 some buffer to get a finished side of 420?

6) That then leads another question. If you are cutting 5@442 would you have a blade loss of something like 5 X .25? Thus something less than 230 for your waste.

I will keep looking for a free way to do this. Building your own algorithm may be tough, but I will see what I can do.

7) With that said do you really need to do this in Access? What data is saved/stored. Could you use an application like 1D Stock Optimizer then save the data into Acess.

 

[TimPen]

Many thanks

http://www.astrokettle.com/pr1dsc.html

They want to charge $1200! This is what they quoted me, and it is simply too expensive. I don't mind contributing, but this is too expensive

I see my solution as a 1d.

In order to visualize how you do this I will asks questions on the first order
LENGTH WIDTH HEIGHT #boxes
420 120 85 440

1)It appears that strips are cut from a board of 2440 X 1220?
(or an 8'X4' sheet of plywood/laminate) Correct

2)You show strip widths of 100 and 147. Where does that come from?I take the width of the product and add allocations like saw thichness, sanding etc. You don't need to worry about any of this. I will pass the actual cut sizes.

3) I assume the strips are ripped like this
long way (giving you strips that are 100/147 wide by 2440 long)

1220
___________
| | | |
| | | |
| | | |
| | | |
| | | | 2440
| | | |
| | | |
| | | |
| | | |
-----------

Correct

All tops (or bottoms) get cut out of their own piece of stock. you do not have a lot of choices (unless you can mix with a later order). You have to rip enough strips to make your tops and your stuck with whatever waste you have after cutting.

Correct

5)How is strip cut size determined? I know from the box dimension what the strip size needs to be. Agian, I will pass this to the calculation function. The function does not need to calculate this.

I will keep looking for a free way to do this. Building your own algorithm may be tough, but I will see what I can do.

Much appreciated

7) With that said do you really need to do this in Access? What data is saved/stored. Could you use an application like 1D Stock Optimizer then save the data into Acess. I use Access as the database. I am not worried what application I use! I would like to use something that I can automate with Access

 

[MajP]

Now that I understand your problem I think this is simple enough to use the Xcel solver, or do a brute force heuristic to come up with a better solution (maybe not the best). Your not doing multiple size boxes (mixed orders) and multiple size strips. I will work on an excel solution and see what i can come up with. I think I found a freeware solution as well.

These commercial products use either some variant of a column generation, branch and bound, or dynamic programming algorithm. All beyond my ability to code from scratch without a lot of time on my hand and a lot of research. However, if you come across any code on the web please pass along.

 

[MajP]

Good news. I modeled in Excel and it solved with no problem. Here is one thing that confused me though. For the first problem you show that the required boxes is 400. In my mind that is 400 tops, 400 bottoms and 800 long sides, 800 short sides. But your answer is
per strip strips
long 5 13
short 17 4
top 5 10
bottom 5 10

Which is only 65 long, 68 short, and 50 top bottom?

Here is my excel solution for 400 boxes (sides only) based on my assumption of 800 long and short.

144 strps @ (1 x 142, 5 x 442) waste 88
10 strips @ (4 x 142, 4 x 442 waste 104
44 strips @ (14 x 142, 1 x 442) waste 10

total strips 198
total short sides: 800
total long sides: 804 (could choose not to cut last strip)