|
From: | Nitin Patel |
Subject: | Re: [Help-glpk] Stock Cutting problem |
Date: | Sun, 10 Mar 2013 15:04:06 +0530 |
Thank you Mr Jeff Thanks for quick replay. Actual problem has more stocks (10 to 15 different lengths with 500 quantities) and demands (10 to 15 different lengths with 200 quantities). I am new to GLPK-Mathprog . It will take some time to learn things. I know VB / Excel VBA. I do not understand matter you have mention in second paragraph. It is my fault as I am new to this subject. (OR & GLPK) AS per you “Larger problems would require more care. In particular, stock cutting is often solved using a column generation.” Can you provide some more information for the same? For below small data it took 413 Seconds. Can we reduce time using “column generation”? param : PRODUCTS : pLength demand := '110m' 110 1 '107m' 107 6 '105m' 105 4 '103m' 103 3 '100m' 100 2 '96m' 96 4 '94m' 94 1 '91m' 91 3 '86m' 86 3 '78m' 78 2 '76m' 76 2 '69m' 69 5; param : RAW : rLength avail := '280m' 280 14; Thanks Niitn Patel From: Jeffrey Kantor [mailto:address@hidden This is a relatively small scale problem so it can be solved as the assignment of product pieces to stock pieces. Appended below is a MathProg solution which you can cut and paste into http://MathP.org or http://www.nd.edu/~jeff/mathprog/mathprog.html for testing. This solution uses indexed sets to enumerate the individual product and stock pieces of materials. For the given data is no waste piece could be less than 1 meter, so it isn't necessary to consider the issue of minimizing small scrap. That could be handled with an additional binary variable for each piece of raw material, but wasn't necessary given the problem data. Another aspect is that minimizing the number of pieces cut leaves a lot of solution symmetries. The computation is faster by introducing weights, which has the nice side effect of producing a 'no-waste' solution for the given problem data. Larger problems would require more care. In particular, stock cutting is often solved using a column generation. Jeff # Stock Cutting Problem # Product catalog set PRODUCTS; param pLength{PRODUCTS}; param demand{PRODUCTS}; # Raw Materials set RAW; param rLength{RAW}; param avail{RAW}; # Set of production pieces indexed by products set Q{p in PRODUCTS} := 1..demand[p] ; # Set of stock pieces indexed by raw materials set S{r in RAW} := 1..avail[r]; # Cutting assignments var y{p in PRODUCTS, q in Q[p], r in RAW, s in S[r]} binary; # Indicator if an item of raw material is used var u{r in RAW, s in S[r]} binary; # Length of waste from each piece of raw material var w{r in RAW, s in S[r]} >= 0; # Cut each product piece only once s.t. A{p in PRODUCTS, q in Q[p]} : sum{r in RAW, s in S[r]} y[p,q,r,s] = 1; # For each product, cut enough pieces to exactly meet demand s.t. B{p in PRODUCTS} : sum{q in Q[p], r in RAW, s in S[r]} y[p,q,r,s] = demand[p]; # For each piece of raw material, do not exceed length s.t. C{r in RAW, s in S[r]} : sum{p in PRODUCTS, q in Q[p]} pLength[p]*y[p,q,r,s] + w[r,s] = rLength[r]; # Determine if a piece of raw material is used. s.t. D{r in RAW, s in S[r]} : 15*u[r,s] >= sum{p in PRODUCTS, q in Q[p]} y[p,q,r,s]; # Minimize number of bars, with weights to favoring long pieces minimize NumberOfBars: sum{r in RAW, s in S[r]} rLength[r]*u[r,s]; solve; printf "Cutting Plan\n"; for {r in RAW} : { printf " Raw Material Type %s \n", r; for {s in S[r]} : { printf " Piece %g : Remainder = %2g : Cut products ", s, w[r,s]; for {p in PRODUCTS} : { for {q in Q[p] : y[p,q,r,s]} : { printf "%s ", p; } } printf "\n"; } printf "\n"; } printf "Production Plan\n"; for {p in PRODUCTS} : { printf " Product %s \n", p; for {q in Q[p]} : { printf " Piece %g : Cut from stock ", q; for {r in RAW} : { for {s in S[r] : y[p,q,r,s]} : { printf "%s ", r; } } printf "\n"; } printf "\n"; } data; param : PRODUCTS : pLength demand := '7m' 7 3 '6m' 6 2 '4m' 4 6 '3m' 3 1 ; param : RAW : rLength avail := '15m' 15 3 '10m' 10 3; end; On Sat, Mar 9, 2013 at 12:07 PM, Nitin Patel <address@hidden> wrote: How to solve stock cutting problem with multiple length stock available and demand is under. Stock length available--- 15 m – 3 Numbers 10 m – 3 Numbers Demand--- 7m – 3 Numbers 6m – 2 Numbers 4m – 6 Numbers 3m – 1 Number How to solve it so that minimize wastage We should utilize minimum number of stocks If unused length is more than 0.5 m then we can utilize it for next cutting schedule and it is not wastage. Thanks Nitin patel
|
[Prev in Thread] | Current Thread | [Next in Thread] |