I am trying to work on Cutting Stock Problem. I have seen some algorithm. Can anybody suggest the best 2D cutting stock problem algorithm?
I am looking for kind of best acceptable solution for 2D Glass Cutting problem. The constraints/features for this are as follows: Input to this problem is a set of Large Rectengular Glass Sheets (say approximately 100) with varied Length and Breaths called stocks. Requirement is cut Rectengular Glass pieces out of them (say approximately 200) with varied length and breadth. All (stocks & output sheets) are rectangular. Also,cuts has to be guillotine cuts that mean each cut has to be end to end.
Example of input:Stock (200 X 100 X 10, 200 X 90 X 5, etc), Required Glasses (50 X 50 X 8, 50 X 40 X 8, etc) in format of (Length X Width X No of sheets)
Here is small history of my approach for the problem: I wrote algorithm which would in following 4 passes:
Pass1: Take One Stock. Create a tree with all cuts possible for all the public required glasses. Also, I could rotate the glass. This step created a huge tree and is exponential.
Pass2: Iterate Pass2 for all the stocks.
Pass3: Iterate each of the tree and covert the problem into ILP problem, as is done for 1D-CSP.
Pass4: Solve the ILP to get the best solution.
The problem with this approach is that at the first step itself the tree becomes so huge for big number of required glasses that it could not be completed in desired amount of time.
Hope this helps, please let me know if extra information is required.
Regards Sandeep Jindal