Cut logic

[aTekTipsUser]

I'm trying to write a program that will calculate the best way to cut a piece of material. I am trying to avoid 3rd party software.

Has anyone done something similar to this? Does anyone know of some good resources that I could go to to find how to cut material with the least amount of waste? I've been searching the internet, but have not had any luck. I know this probably isn't the right place to post this message, but I'm stuck and maybe someone else has done this before.

Thanks in advance.

 

[chiph]

This is an NP-complete problem, and as such, the computational cost of finding the one-good-way to cut a piece of material to minimize waste is really excessive.

A good parallel is the knapsack problem, where you have to place items into a knapsack in a certain order to maximize the number of items that can be placed in it. As you might imagine, UPS and FedEx are very interested in a solution to this problem, as that would let them pack more boxes into their trucks.

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

and

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

You might want to investigate some genetic algorithmic approaches.

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

Chip H.


____________________________________________________________________
If you want to get the best response to a question, please read FAQ222-2244 first