Optimized cutting of steel angles using EXCEL 2

[nitin36537]

Can someone suggest how to determine optimum cutting schedule from a give stocks of angle sections using excel?

Stock data
100*100*7 ---- 5000 mm 150 qty cost 1000 $/MT
100*100*7 ---- 6500 mm 25 qty cost 1050 $/MT
90*90*6 --- 6500 mm 100 qty cost 1020 $/MT
90*90*6 ---- 5500 mm 120 qty cost 1000 $/MT

Requirement
100*100*7 2000 mm 20 qty
100*100*7 2200 mm 25 qty
100*100*7 3000 mm 50 qty
90*90*6 2000 mm 75 qty

How optimize cutting schedule so that wastage is minimize.
There are ready made programs available but I want to develop it on Excel .

Thanks

 

[poli60]

nitin,
although I had to make some assumptions to fill the lack of definitions, I've tried to answer your question.
My solution is attached.
Please fill free to make comments.
Kind regards

 

[IDS]

Any chance of an Excel file, rather than a pdf, so we can see how it works?

Doug Jenkins
Interactive Design Services

http://newtonexcelbach.wordpress.com/

 

[nitin36537]

Can you please provide steps/methods ( Reading materials) required to find out solution. preferably with EXCEL/ EXCEL VBA

Regards
Nitin

 

[poli60]

nitin,
first of all, I need to know from you if the problem has been correctly understood.
Please note that the proposed solution is with excel only.
Regards

 

[IRstuff]

The worksheet would be useful; a casual calculation suggests that the wastage is higher than necessary, more like 27200, instead of 32800, using 25 6500 mm*6, 9 5000*7 mm and 33 6500*7 mm. Net cost is slightly lower at 69150.

TTFN
faq731-376

 

[poli60]

Ok. I was trying to have some comments from the originator before publishing the spreadsheet.
But, as too often it occurs, the "experts" seem more interested than the originators.
I've seen the comment of IRstuff but the Solver model in my spreadsheet is not able to reproduce his solution.
Anyway, on that base, I've found an error in the original model (ie one cut opton missed), corrected it and re-ran.
Now the solution is better (ie 71700 cost, 26500 waste) than before but not very stable.
So, I'm curious to see if IRstuff, IDS or others can improve the spreadsheet.
Thank you.

 

[IRstuff]

I'm not sure if there's a "simple" way to do the optimization; it would seem likely that a brute-force multi-combination testing approach would have to be undertaken. It looks like your sheet treats P1-P4 as separate entities, which is why my attempt can't be replicated, since I combined different Px's to try and get better utilization of the stock. This was done by hand, of course, since it looked like there was no simple way program something like that, and it wasn't even clear whether the OP had any groundrules about that. Not clear whether this is the way to go, or whether your approach is the way to go. The OP needs to chime in about what the end goal is; lower cost or lower wastage. Seems like minimum utilization of stock is actually the most desirable, as that preserves inventory. Your solution uses 70 pieces of stock, but mine uses 67. Since the solutions are all very close together optimization is more difficult to determine.

http://files.engineering.com/getfil...a-6cfab41c6bda&file=Cutting_Optimization.xlsx

TTFN
faq731-376

 

[nitin36537]

Dear all

During cutting if remaining Pieces length is less then 500 mm then it is a wastage.
If it is more than 500 mm then we can consider that same pieces will be utilized for other project.So minimum wastage is the goal.

Also please note that cost is define as $/MT. Excel file is attached for better understanding.The data in Excel file is only a sample one.

Regards

Nitin

 

[poli60]

nitin,
as I suspected not all the basis were given....
Some questions for you:
1) what is MT? In the present scenario, it could be either meter (m) or metric ton (t).
2) what is the physical meaning of the three parameters characterizing the stocks (eg 100*100*7)?
3) the model results will be different by minimizing either the cost or the wastage. Logically thinking, the cost should prevail on the wastage.
4) would you be able to modify the spreadsheet to obtain your target?
5) would you give a star to the spreadsheet?
Regards

 

[cowski]

Perhaps this article will yield more ideas/references/search terms

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

www.nxjournaling.com

 

[nitin36537]

1-MT stand for metric ton
2-100*100*7 is steel angle section ( L shape )with both flange having 100mm width and 7mm thickness.
3-Minimizing wastage is main criteria.If we minimize wastage balanced material can be used for other project.
4- ???
5- YES


Regard

 

[IRstuff]

"During cutting if remaining Pieces length is less then 500 mm then it is a wastage.
If it is more than 500 mm then we can consider that same pieces will be utilized for other project.So minimum wastage is the goal."

This is another constraint, so a subgoal is to aggregate the leftovers so that they are larger than 500mm.

@Cowski thanks for the article link. The article and subsequent websearches suggest that this is a relatively non-trivial problem. This one site:

http://www.delphiforfun.org/Programs/Cutting Stock.htm

has a Pascal program that does an optimization for the cutting problem. You'll need to enter the different (6 or 7) stock separately, but its solution uses only 6500mm 100*100*7 for those orders and uses 41 pieces. My hand solution used two types with 42 pieces. The source code is also on the site. I've not figured out how to actually use the files as inputs; I typed the info manually. The output of the program is below; the program also has a very pretty graphical representation of the solution.

 --- Initial Solution Cutting Patterns ---
 PATTERN(   1)
 Stock Length=6500.00  Qunatity used=   25.0000
 Order length=3000.00, Number to cut from each=2, Total cut=50.00
 PATTERN(   2)
 Stock Length=6500.00  Qunatity used=   12.5000
 Order length=2200.00, Number to cut from each=2, Total cut=25.00
 PATTERN(   3)
 Stock Length=6500.00  Qunatity used=    6.6667
 Order length=2000.00, Number to cut from each=3, Total cut=20.00
 COST OF USED STOCK = 46375.0000

********** Iteration # 1 ***********
 --- BTRAN : Calculate Dual variables (incremental costs) ---
For length 3000.00 Dual cost= 525.00000
For length 2200.00 Dual cost= 525.00000
For length 2000.00 Dual cost= 350.00000

 ---  DPKNAP : Solve Knapsack Problem  ---
     Optimal pattern to add 
2200.0, 2200.0, 2000.0, 


 ---  DPKNAP : Solve Knapsack Problem  ---
     Optimal pattern to add 
2200.0, 2200.0, 


---  ENTCOL : Generate Entering Column  ---
2200.0, 2200.0, 2000.0, 
 Selected source length  =  6500.00
 Reduced  cost           =    350.0000

 --- FTRAN : Update Column --- 
    0.0000
    1.0000
    0.3333

 ---  CHUZR : Choose pattern to drop  {PIVOT ROW} --- 
2-th pattern  is leaving, at min ratio     12.5000

 --- UPBINV: Update B Invers ---
(BI(i,j),i=1,NPART),j=1,NPART (only non-zero displayed)
b(1,1)=    0.5000
b(2,2)=    0.5000
b(3,2)=   -0.1667
b(3,3)=    0.3333

 --- UPSOL: Update Solution ---
index, basic variable solution
   1    25.0000
   2    12.5000
   3     2.5000
The new cost is = 42000.0000

********** Iteration # 2 ***********
 --- BTRAN : Calculate Dual variables (incremental costs) ---
For length 3000.00 Dual cost= 525.00000
For length 2200.00 Dual cost= 350.00000
For length 2000.00 Dual cost= 350.00000

 ---  DPKNAP : Solve Knapsack Problem  ---
     Optimal pattern to add 
2000.0, 2000.0, 2000.0, 


 ---  DPKNAP : Solve Knapsack Problem  ---
     Optimal pattern to add 
3000.0, 2000.0, 


---  ENTCOL : Generate Entering Column  ---

 Selected source length  =  6500.00
 Reduced  cost           =      0.0000



 --- Optimal Fractional Solution ---
Pattern(1)  Stock length:   6500.00  Needed:   25.00
	Order length:3000.00  Number cut from each stock piece:     2
	Unused from each stock piece 500.00
Pattern(2)  Stock length:   6500.00  Needed:   12.50
	Order length:2200.00  Number cut from each stock piece:     2
	Order length:2000.00  Number cut from each stock piece:     1
	Unused from each stock piece 100.00
Pattern(3)  Stock length:   6500.00  Needed:    2.50
	Order length:2000.00  Number cut from each stock piece:     3
	Unused from each stock piece 500.00
Stock cost =   42000.00
 Number of Iterations =  2

 --- Optimal Integer Solutuion ---
Pattern(1)  Stock length:   6500.00  Needed: 25
	Order length:3000.00  Number cut from each stock piece:     2
	Unused from each stock piece 500.00
Pattern(2)  Stock length:   6500.00  Needed: 13
	Order length:2200.00  Number cut from each stock piece:     2
	Order length:2000.00  Number cut from each stock piece:     1
	Unused from each stock piece 100.00
Pattern(3)  Stock length:   6500.00  Needed: 3
	Order length:2000.00  Number cut from each stock piece:     3
	Unused from each stock piece 500.00
Stock cost =   43050.00

TTFN
faq731-376

 

[IRstuff]

Oh, note that the fractional solution appears to be acceptable per OP's constraints, since the leftover piece is large; so only 40 pieces consumed.

TTFN
faq731-376

 

[IRstuff]

I did get the input files to work; you need to have the correct numbers for types of stock and types of product.

http://files.engineering.com/getfil...3-84f8-7eb46c2ac863&file=ET_test_solution.txt

TTFN
faq731-376

 

[zelgar]

Attached is a spreadsheet with a macro to do what you'd like.

 

[IRstuff]

Not solving the knapsack problem potentially leads to inefficient answers, since optimum combinations of lengths are left unconsidered.

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

TTFN
faq731-376

 

[poli60]

@IRStuff,
IMHO the solution you proposed is not correct (see attached cut_solver_IRS.pdf)

@zelgar,
can't see your solution since the macro doesn't run on my pc (my fault, for the time being I've no time available for understanding & debugging)

@all,
after implementing all the basis given by nitin (and added others to bound the solution), my proposed solution is attached (cut_solver2.pdf).
I think it is the best achievable from excel 2007 solver, but I'm curious to see if there are better ones.

Thanks, regards and smiles

 

[poli60]

ooops

 

[IRstuff]

??? It looks like your last sheet matches the output from the Pascal program?

TTFN
faq731-376