Linear Nesting algorithm in vb.net

[bguenther]

Hi,

I want to create a program that will calculate how much raw material I will need to cut a set of parts.

For example:
Structural Steel Tubing 2 x 1 x .125 x 288
95.75 36 pcs
41.875 89 pcs
10.5 45 pcs
2.875 720 pcs

I want to calculate the best layout so that i get the least amount of scrap and then i want it to tell me how many lenths will i need
of raw material.

I am not expecting anybody to write this program for me. I am just looking for some ideas on how to go about doing this.

Regards,
Ben

Ben Guenther
Custom Addins and Macros

http://www.lmsoftworks.ca

 

[MacGyverS2000]

This is a major area of PhD-level research as it's not a simple problem... expect to read some journal articles if you want the latest ideas. Still, Google will turn up some basic algorithms to play with. Linear is significantly easier than 2D (or God forbid, 3D!).

Dan - Owner

http://www.Hi-TecDesigns.com

 

[MacGyverS2000]

Hit reply too fast...

To get you started, consider it a Factorial problem, so just run each possible combination of lengths over your stock length. You can quickly trim down the possibilities by setting appropriate limits (e.g., you can't cut more than five 1' lengths on a 5' pipe, so don't try with six lengths). Even in a realtime environment, the calculations happen pretty fast, so you can test a lot of combinations.

Since your stock length is fixed, this is best classified as a bin packing problem. This Wiki page will prove useful for a bit of research:

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

Dan - Owner

http://www.Hi-TecDesigns.com

 

[bguenther]

Thanks for the past reply.
I am not planning as of now to get into 2D nesting because of its complexity and for sure not 3D (Would not have use for 3D anyway.).

I have used a program called Cutmaster2D and it works wonderfully, could not ask for more. It is really fast, if you have a long list of parts and high qty's then it takes a bit longer but still very fast. It is capable of 2D as well.

Yea i might have play with do all the possible combinations, just hard to find a start.

Any chance somebody could simplify "Formulation and solution approaches" from here ?

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

I do not understand them or i don't know what that means.

Ben Guenther
Custom Addins and Macros

http://www.lmsoftworks.ca

 

[bguenther]

The reason i am trying to create my own is because i want to create an addin so that i dont have to create the parts manually.

Ben Guenther
Custom Addins and Macros

http://www.lmsoftworks.ca

 

[IRstuff]

you could look here:

http://www.mathworks.com/matlabcentral/fileexchange/?term=knapsack

TTFN

FAQ731-376
Chinese prisoner wins Nobel Peace Prize

 

[bguenther]

Thats over my head IRstuff.
I know nothing about matlab and almost nothing about c++ cant get anything out of that.

But i appreciate the response.

Ben Guenther
Custom Addins and Macros

http://www.lmsoftworks.ca

 

[MacGyverS2000]

Ben,

That section of the Wiki article is nothing more than the math behind what I initially suggested... run all possibilities/patterns. The section goes further by assigning each pattern a rank, with the rank determining how well the pattern does to minimize waste. Several patterns may create the same minimal waste, so you can pick any one of them, but which one is irrelevant to you. Just run through all possible patterns, choose any one of them that has the lowest value, and use it.

Dan - Owner

http://www.Hi-TecDesigns.com

 

[IRstuff]

Well, if you actually intend to even come up with a non-optimum solution, you'll need to understand the math, and theory, particularly if you want to create an add-in as you stated. How are you going to program an add-in if you don't tackle the algorithm?

TTFN

FAQ731-376
Chinese prisoner wins Nobel Peace Prize

 

[bguenther]

Well i just don`t understand all the symbols that wiki used. I am attempting to write it now just with my own ideas of looping and trying different ways to check all the different possibilities, like you said.
I am self taught with almost everything, so i am easily lost.
I have made many add-ins so most of it will be easy its just figuring out the algorithm will be difficult. The add-ins i make are for Solidworks by the way.

Ben Guenther
Custom Addins and Macros

http://www.lmsoftworks.ca

 

[xwb]

Don't you have a bunch of orders and then you cut the tubing in a way that best fits your orders? Sounds like a similar algorithm to the one used to copy files to a bunch of floppies in the late 80s.

 

[bguenther]

We will have received an order for a certain item and then i will need to order tubing for it. We do not stock any tubing so i try to get as close to the correct amount as possible.(A little extra always).

So the user will be asked how many assemblies are on order an then it will put together a cut-list based on the solidworks assembly and the amount required for the order. Then the calculation will be performed to find out how much tubing is needed.
It will then show a report of the layouts that it used to get to that number or lengths used.
So you can print them out and use them when you are cutting so that you are using the best combination possible.

Yes this does sound like a similar algorithm they used for that.

This program will also be very use full when pricing an item then you need to know exactly how much tubing is used.


Ben Guenther
Custom Addins and Macros

http://www.lmsoftworks.ca

 

[DenisOptimalon]

Hi,

Instead of spending lots of time and money to find the solution of the problem you can use tested and recognised solution GNCutter32. It's a callable library that performs the cutting optimization for you (just google "GNCutter32")

 

[bguenther]

MacGyverS2000,
Why does that confuse you? How can you expect somebody to know something if he/she has not had much to do with it? My field of work has always been very simple math and programing with solidworks which has a very good support forum.

I am not offended at all by what you said but i do not understand why you wrote that or what you are trying to get at.

Anyway, Denis thanks i will look into that one. I also found this

http://www.optimalprograms.com/cut_1d_x.htm

which is much the same thing i think.

Ben Guenther
Custom Addins and Macros

http://www.lmsoftworks.ca