《外文翻译--多级下料问题的建模 英文版》由会员分享，可在线阅读，更多相关《外文翻译--多级下料问题的建模 英文版（15页珍藏版）》请在金锄头文库上搜索。
1、Modeling multistage cutting stock problemsEugene J. Zak*Majiq Inc., 8343 154th Avenue NE, Redmond, WA 98052, USAReceived 12 June 2000; accepted 28 August 2001AbstractIn multistage cutting stock problems (CSP) the cutting process is distributed over several successive stages. Everystage except the la
2、st one produces intermediate products. The list of intermediate products may be given or arbitrary.The goal is to minimize the total amount of material taken out of stock to cut finished products sufficient to meetcustomer demands. If the intermediate sizes are given, the column generation technique
3、 can be applied to multistagecutting problems. If the intermediate sizes are not given then another dimension is added to the problem complexity.We propose a special procedure for this case that dynamically generates both rows (intermediate sizes) and columns(patterns). We refer to this method as ro
4、w-and-column generation. The method uses an auxiliary problem embedded intothe frame of the revised simplex algorithm. It is a non-linear knapsack problem that can be solved efficiently. In contrastto the column generation method the developed technique cannot guarantee the optimal solution. However
5、, the resultsof computational experiments are very promising and prove that the method is a valuable addition to the set of tools formodeling and solving multistage CSPs. ? 2002 Elsevier Science B.V. All rights reserved.Keywords: Linear programming; Multistage cutting stock problem; Large-scale opti
6、mization; Row-and-column generation1. IntroductionA one-dimensional cutting stock problem (CSP) has an important practical generalization when acutting process is distributed over several successive stages. This multistage CSP includes not just cuttingpatterns and their activities, but also the inte
7、rmediate products and their quantities produced at every stageof the cutting process except the last one, and consumed at every stage of the cutting process except the firstone. These intermediate products are cut to produce smaller intermediate sizes or finished sizes. The in-termediate products ar
8、e both output and input during the cutting process. This kind of problem occurs inalmost every industry where a classic CSP takes place: paper, film, leather, steel, etc. Although the articlesresults are equally applicable to any industry where multistage cutting takes place, for the purpose ofsubje
9、ct area illustration, we will use terminology accepted in the paper industry. In particular, we will referEuropean Journal of Operational Research 141 (2002) +1-452-881-7100; fax: +1-452-881-5084.E-mail address: (E.J. Zak).0377-2217/02/$ - see front matter ? 2002 Elsevier Science B.V. All rights r
10、eserved.PII: S0377-2217(02)00127-3to a roll as a product geometrically defined by its width. Roll diameter, total length of unrolled paper, andpaper caliper are not relevant for the current investigation.Fig. 1 illustrates a three-stage cutting process. In this example three types of stock rolls S1,
11、 S2, and S3 areused to produce nine types of finished rolls (F1F9). It is interesting to note that stock rolls can supply anystage of the process. Here, S1 goes to the first stage, S2 goes to the second, and S3 goes to the third.Conversely, the finished rolls can be produced at any stage. Three type
12、s of intermediate rolls I1, I2, and I3are cut at the first two stages. Clearly, we may see proliferation of stock types, intermediate products, andeven cutting stages in real-world problems.Multistage is an overloaded word, particularly in the Operations Research and CSP areas. Gilmoreand Gomory 7 r
13、efer to a two-dimensional CSP solved by cutting strips along first, then by cutting thestrips themselves across, as a multistage problem. In our case all cuts are along (lengthwise) and theproblem is a one-dimensional CSP. Dyckhoff3 introduced multistage for a so-called one-cut modelwith multistage
14、cutting. The one-cut model is an extreme case opposed to a usual and well-known case of aone-stage problem with unlimited cuts. It is interesting to note that those one-cut and multi-cut modelsare just two different formulations of the same problem, while in a real-world situation the one-stage CSP
15、isoften a relaxation of the multistage CSP. The one-stage relaxation provides a reasonable lower bound forthe original multistage CSP.Several researchers have attacked a multistage CSP. Haessler 9 addresses a two-stage problem with awinder at the first stage and a production rewinder at the second.
16、He explores an LP approach with patterngeneration either beforehand or during simplex iterations using a column generation technique. He rep-resents a winder pattern in terms of finished rolls and checks whether the pattern can be broken up into acombination of legitimate intermediate rolls. If such
17、 a combination is permissible, the pattern is admittedinto the problem matrix. Although the approach is workable, it has some drawbacks. It, potentially, in-cludes a large number of different intermediate rolls, and defining whether a pattern can be partitioned is acomplicated bin-packing problem. A
18、lso, the approach does not scale easily to cutting processes with morethan two stages.Ferreira and others 4 also investigate the two-stage problem, which they refer to as a two-phasedproblem. The authors adapted Haesslers sequential heuristic procedure 8, initially developed for a classicCSP, to a t
19、wo-stage cutting process. At every step of the sequential procedure they are trying to find a set ofgood intermediate rolls ensuring a good pattern for the first stage and good patterns for the second. If thepattern for the first stage is accepted, a residual problem in terms of finished rolls is up
20、dated, reducing theFig. 1. Three stage cutting process: Stock rolls: S1, S2, and S3; Intermediate rolls: I1, I2, and I3; Finished rolls: F1, F2, F3, F4, F5, F6,F7, F8, and F9.314E.J. Zak / European Journal of Operational Research 141 (2002) 313327ordered quantity by the amount defined by the pattern
21、 and its activity. Apparently, this heuristic resemblesa manual procedure for solving a two-stage CSP. The main difficulty with this heuristic is generating a set ofgood intermediate rolls.Carvalho and Rodrigues 1 follow an LP approach. Their problem, however, is subject to a techno-logical restrict
22、ion finished rolls of one width should comprise every intermediate roll. The restrictionallows for predefining a list of possible intermediate rolls. The authors reformulate an initial LP problemposed in terms of finished rolls into a LP problem in terms of intermediate rolls. A column generationtec
23、hnique with a regular knapsack as an auxiliary problem is applied.The idea of an intelligent generation of intermediate rolls emerged in 10 when a two-stage system skiving and cutting was investigated. In the present paper we crystallize the idea and propose arow-and-column generation technique for
24、solving a multistage one-dimensional CSP. The technique is ageneralization of the seminal column generation technique suggested by Gilmore and Gomory 5,6 forsolving a classic CSP, or, in our notation, a single-stage CSP. For a multistage problem, a more compli-cated auxiliary problem may result in c
25、olumn-candidates entering the basis, together with a combination ofrows corresponding to new intermediate rolls. We expand both rows and columns in the LP matrix. A finitenumber of iterations of simplex algorithm lead either to an optimal or a near-optimal solution.In the next sections we will formu
26、late two basic models for the two-stage CSP, present the row-and-column generation method, and then analyze the computational experiments. Some of the results areborrowed from the authors paper 12.2. Model with a given list of intermediate rollsThere are three lists of roll sizes: List of stock size
27、s. List of intermediate sizes. List of finished sizes.Please see Fig. 2(a), which shows the relationship between these three types of rolls. For stock sizes theavailable amounts are known. Stock sizes can potentially be consumed at every stage of the cutting process,and can be cut into intermediate
28、or finished rolls. Intermediate rolls are both input and output. Thetechnological constraints for intermediate rolls are strict: for every size the total number of consumed rollscannot exceed the produced amount. Ideally there should be a total balance; otherwise, some excessiveamount of unclaimed i
29、ntermediate rolls should go to stock in a warehouse, if there is storage spaceavailable. But this is another question of tradeoffbetween cost associated with material waste and ware-housing cost, which is beyond the scope of the current investigation. So we assume that we are consideringan open prob
30、lem with inequality constraints, and we regard unclaimed intermediate rolls as waste. For afinished roll we have an ordered amount that should be satisfied.Here we consider a two-stage CSP with one width of stock roll that is to be cut at the first stage intoseveral intermediate rolls (Fig. 2(b). Fi
31、nished rolls are produced at the second stage by cutting the in-termediate rolls. We assume that the width of an intermediate roll coming out of the first stage and going tothe second one satisfies minimummaximum restrictions. The width of every intermediate roll should alsoincorporate a minimum edg
32、e to be trimmed at the second stage.Let w and y be vectors of the finished and intermediate roll widths, respectively. Cutting patterns of thefirst stage and the second stage are represented by matrices A11and A22, respectively. To make up a full LPmatrix we define another matrix A12showing the rela
33、tions between the two. Every column j of the con-necting matrix A12is a vector 0;.;0;?1;0;.;0T, where exactly one non-zero element )1 appears inE.J. Zak / European Journal of Operational Research 141 (2002) 313327315the position i corresponding to the intermediate roll i that should be cut according
34、 to the cutting patterndefined by column j in matrix A22.Now we can formulate an LP model for the multistage CSP:Minimize1T0T?x1x2?1subject toA11A120A22?x1x2?P0b?;2x1;x2P0:3Here vectors x1and x2are pattern activities for the first and the second stages, respectively; b is a vector ofcustomer demands
35、 on finished rolls.Fig. 2. Graphs depicting roll relations: (a) general case; (b) case under consideration.316E.J. Zak / European Journal of Operational Research 141 (2002) 313327The objective function (1) is to minimize the number of used stock rolls that is defined by the term 1Tx1.Constraints (2)
36、 ensure that consumption of intermediate rolls A12x2at the second stage should not exceed their production A11x1atthe first stage, and customer demand of finished rolls b should be met.Notice that the overall LP matrix has a special structure. There are two diagonal blocks A11and A22representing cut
37、ting patterns for two stages, connecting block A12, and a block of 0s in the lower-leftcorner. The right-hand side is made up by 0-demand on intermediate rolls and the vector b. Model (1)(3) isa LP presentation of a two-stage CSP that explicitly involves intermediate rolls. The LP matrix might be fu
38、llif the problem is relatively small. In this case all patterns for all stages can be presented in the matrix.Otherwise, on-line column generation is an appropriate technique for column selection. But in both cases,whether we generate all columns in advance, or use column generation, the number of r
39、ows in the matrixremains unchanged, since the list of possible intermediate sizes is given.2.1. Dual problemLet us consider the dual problem associated with (1)(3):Maximize0TbT?u1u2?4subject toAT110AT12AT22?u1u2?610?;5u1;u2P0:6Here vectors u1and u2are vectors of dual variables corresponding to inter
40、mediate rolls and finished rolls,respectively.The dual problem (4)(6) leads to two types of auxiliary problem that should be solved at the columnselection step of the revised simplex algorithm.2.2. Column generationThe first type of auxiliary problem is generation of a cutting pattern related to the
41、 first stage of thecutting process. The list of intermediate rolls remains unchanged. Clearly, this type is associated with thefirst group of constraints (5) of the dual problem, and the auxiliary problem is essentially the sameknapsack problem as we have in a classic or a single-stage CSP. The auxi
42、liary problem can be stated as thefollowing knapsack problem:Knapsack IMaximizeuT1asubject toyTa6w0;aP0;and integer:Hereu1isavectorofobjectivefunctioncoefficientsthatarevaluesofthedualvariablesofthemasterproblem;y is a vector of intermediate roll widths; w0is the stock roll width and vector a is a v
43、ector of variables.If the objective function value exceeds 1.0, a new column a for the first stage is generated. This conditionimmediately follows from the first group of the constraints (5) which can be presented as uT1A1161T. Thesolution vector enters as a column into matrix A11.E.J. Zak / Europea
44、n Journal of Operational Research 141 (2002) 313327317The second type of auxiliary problem is associated with cutting patterns generated for finished rollsutilizing existing intermediate rolls. This type is associated with the second group of constraints (5). Foreach intermediate roll yjwe should so
45、lve the following knapsack problem:Knapsack IIMaximizeuT2a;subject towTa6yj? emin;aP0;and integer:Here u2is a vector of objective function coefficients that are values of the dual variables of the masterproblem; w is a vector of finished sizes; eminis a mandatory minimal edge, eminP0; yjis width of
46、inter-mediate roll j and vector a is a vector of variables.Let u1jbe a value of the dual variable corresponding to the intermediate size j. If the objective functionvalue exceeds u1j, a new column a for the second stage is generated. This condition immediately followsfrom the second group of the con
47、straints (5) which can be presented as uT2A226 ? uT1A12. Given the matrixA12structure, the right-hand side boils down to a vector of dual variables corresponding to intermediaterolls.The solution vector enters as a column into matrix A22.If we do not have uncertainty in the intermediate rolls, two t
48、ypes of knapsacks shown above KnapsackI and Knapsack II are sufficient to solve the problem optimally.3. Model with unknown intermediate rollsIf intermediate rolls are unknown, we face a more complicated situation. We are free to pick any suitableintermediate size y from a given range ymin;ymax. Sin
49、ce every intermediate roll and a finished roll is as-sociated with a row of the LP matrix, uncertainty in the LP matrix stretches in both directions: columns androws. For this reason, a column generation technique alone cannot solve the problem. On the other hand,the potentially huge number of inter
50、mediate rolls may preclude generating all possibilities beforehand. Wecan estimate the potential number of different intermediate rolls in real life situations. Let Dy be the rangeof intermediate roll widths. Parameter Dy is machine-dependent, but usually Dy ? 800 mm. Let d be theleast roll width ac
51、curacy. Normally, d 0:5 mm. Thus the number of different rolls n ? Dy=d. This for-mula gives us an estimate n ? 1600. Certainly for particular instances of the multistage CSP the estimatemay be much less. Nevertheless the full size of the LP matrix tends to be very large.Another argument that is aga
52、inst advanced intermediate roll generation is an operational issue. Thegreat diversity in intermediate rolls at a time slows down the material flow, complicates roll-tracking tasks,and provides less flexibility in cutting operations. Invariably a paper mill tends to operate with the leastnumber of d
53、ifferent intermediate roll sizes.Needless to say, it would be highly desirable to have an intelligent approach generating intermediate rollsas can be done for cutting patterns only when needed. Next, we will present the row-and-column gen-eration technique for the two-stage problem (1)(3).3.1. Row-a
54、nd-column generationAlong with Knapsack I, and Knapsack II, we may face a third type of auxiliary problem associated withsimultaneous generation of new intermediate rolls and cutting patterns. We should remember here thatrows of the LP matrix present intermediate and finished rolls. (If we had const
55、raints on stock rolls wewould include stock rolls as additional rows as well.) The columns of the LP matrix are patterns for cuttingstock rolls into intermediate rolls and intermediate rolls to finished ones.318E.J. Zak / European Journal of Operational Research 141 (2002) 313327Here we are trying t
56、o adapt the revised simplex to a task that is not typical for it. It is known that onevery step of the revised simplex a column is entering the basis and replacing another column that is leavingthe basis. If columns are not known in advance we use a column generation technique, expanding the LPmatri
57、x in the column direction. Nothing in the revised simplex gives us the ability to generate unknownrows. The question is how can unknown intermediate rolls be generated using a step of the revised simplex?Let us restrict the intermediate roll search by generating not more than one new intermediate ro
58、ll onevery step of the revised simplex. Thus we are supposed to generate a new row of the LP matrix, and, in thenon-degenerate case, the rank of the LP matrix will be effectively increased by 1. The basis matrix shouldalso be expanded by one row and one column, and since only one column leaves the b
59、asis during a pivotingstep, we conclude that two new columns should actually be generated during a simplex step. One of themshould be added up to the basis matrix unconditionally, and the other one should replace the existing one ina pivoting step.Let vector y be intermediate roll sizes that have be
60、en in the model so far, variable z be a new intermediateroll size, and v be a corresponding dual variable. We face the following nonlinear integer programmingproblem:Knapsack IIIMaximizeuT1a11 va7subject toyTa11 za6w0;8wTa226z ? emin;9uT2a22 v;10vP0;11ymin6z6ymax;12a11;a22P0;and integers:13The varia
61、bles here are two new columns: column a11for the first stage and column a22for the second stage,intermediate roll width z, the dual variable for the new row v, and the number of rolls a for the new in-termediate width in the cutting pattern of the first stage. Note that constraints (10) have an equa
62、lity form.As a result of solving Knapsack III we will find a new intermediate roll size, and two cutting patterns for thefirst and the second stages, respectively.Theoretically, the limitation imposed above restricts our choices for generating intermediate rolls. In-deed, a situation may occur when
63、there exist no new cutting patterns involving just one new intermediateroll. At least two new intermediate rolls should be included in a cutting pattern on the first stage. We canimagine that this situation is more probable at the beginning of the revised simplex, when the initial set ofintermediate
64、 rolls is scarce. As soon as the procedure generates more intermediate rolls, this situationbecomes less probable. As we show later, the one intermediate roll at a time restriction is justified for awide range of real world CSPs.3.2. A modified column selection in the revised simplex algorithmLet us
65、 prove the following proposition first.Proposition 1. Let B be a non-singular matrix of m ? m, and Babe its extension formed by adding one row andone column as shown below:BaBa0T?1?;14E.J. Zak / European Journal of Operational Research 141 (2002) 313327319where a is a vector of dimension m, and 0 is
66、 a vector of zeros of dimension m. Then, an inverse matrix B?1aexists and is defined asB?1aB?1B?1a0T?1?:15Proof. It is not difficult to verify that BaB?1a I, where I is an identity matrix.?The modified column selection step of the revised simplex algorithm is as follows:Step 1. Solve Knapsack I. If
67、the optimal value of the functional exceeds 1.0, solution a11is a column toenter the basis at the pivoting step of the revised simplex algorithm. Otherwise go to the next step.Step 2. Solve Knapsack II for each existing intermediate roll yj, j 1;.;k. If the optimal value for theproblem j exceeds u1j
68、then solution a22is a column to enter the basis at the pivoting step of the revisedsimplex algorithm. Otherwise go to the next step.Step 3. Solve Knapsack III. If the optimal value of the functional exceeds 1.0, we should expand the basis matrix by one row and one column, and pick the other column a
69、s a column to enter the basis at the pivoting step of the revised simplex algorithm.It does not matter which column should be added explicitly first. In our implementation we add the columncorresponding to the cutting pattern of the second stage first.The basis matrix is expanded according to (14),
70、where B is a basis matrix found so far, and a is a newadded column. The expanded inverse matrix retains the current inverse matrix B?1as its sub-matrix and it isedged appropriately by zeros in the row and by B?1a elements in the column as shown in (15).If the optimal solution of Knapsack III does no
71、t exceed 1.0, and the reduced costs of slack variables arenon-negative, then the current solution is optimal.The column selection looks more complex than in the case of a classic column generation. Actually twoadditional steps 2 and 3 are involved. Now we investigate the auxiliary problem itself.3.3
72、. A nonlinear Knapsack problemWhile the first two types of an auxiliary problem Knapsack I and Knapsack II are traditional andwell covered by the literature (see 11, or 2), the third type Knapsack III requires a special investigation.Knapsack III is a non-linear knapsack with several additional cons
73、traints (7)(13). The non-linearity isstipulated by two terms: va in the objective function (7) and za in the constraint (8).Proposition 2. It is sufficient to consider only those intermediate rolls whose width may be presented as alinear combination of finished roll widths plus minimum edge emin:z e
74、min wTx;16where xP0 is a vector of integers.Proof. Let us assume that we have found a solution of the two-stage problem (1)(3), and at least oneintermediate roll width z cannot be presented as (16). Then we can safely drop its width z to the nearestvalue, identified either by a linear combination (1
75、6), or by ymin. Such reduction does not violate anyproblem constraints. All patterns at both stages involving the intermediate roll z keep their validity. Moretrim loss at the first stage will be compensated by less trim loss at the second stage. The objective functionkeeps it value.?320E.J. Zak / E
76、uropean Journal of Operational Research 141 (2002) 313327We suggest an economical method for solving Knapsack III. The idea is to partition Knapsack III intoseveral simpler sub-problems, solve them separately, and then pick the best solution among them. Theobvious candidate for partitioning is varia
77、ble a. Its possible values are integers in the range from 1 tobw0? emin=yminc. Note that the case a 0 is out of consideration since it reduces Knapsack III toKnapsack I.Now, Proposition 2 and constraints (9) and (10) allow for the elimination of variables z and v from theproblem model using the line
78、ar presentations of variables a22. The modified problem is presented by thefollowing knapsack problem:Knapsack III0MaximizeuT1a11 uT2a22a17subject toyTa11 wTa22a6w0? emina;18ymin6emin wTa226ymax;19a11;a22P0; and integers:20Notice that the element a is a parameter here, a 1;2;.;bw0? emin=yminc. Intro
79、ducing new parameters adjusted widths w0i wia, and adjusted values u02i u2ia, Knapsack III0is getting a form of a regularknapsack problem but with an additional two-sided constraint (19).Next, we outline a branch-and-bound procedure for solving Knapsack III0.3.4. Lexicographic algorithm for the Knap
80、sack problemThe classic Knapsack problem isMaximizecTxsubject toaTx6b;xP0; and integers:All problem parameters fc;a;bg, objective function coefficients and single-constraint parameters, are as-sumed to be positive. The lexicographic algorithm proposed by Gilmore and Gomory 6 in the Chvatal 2notation
81、 is the following:Step 1. Arrange the items in the descending order of ratios: ci=ai, i 1;.;m, where m is the vectorsdimension. Without loss of generality, we may assume that c1=a1Pc2=a2P ? Pcm=am. Initialize an indexof the branching variable, k 0, a record value of the objective function f? 0, and
82、a working parameterof the algorithm a remaining (unfilled) part of the knapsack brest b. (You cannot trace this workingparameter in the original paper, but it emerges inevitably as soon as you start coding the algorithm.)Step 2. Find the most promising extension of the current branch. Iteratively fr
83、om i k 1 to m set:xi brest=aibc;andbrest brest? aixi:Step 3. Is an improved solution obtained? Calculate the value of the objective function f cTx andcompare it with the record. If f f?, then update the record solution x?with x, and the record value f?with f.Step 4. Backtrack to the next branch. If
84、k 1, then stop, otherwise decrement k iteratively by 1 until thefirst k with xk 0 encounters. If k 1, then set:xk xk? 1;E.J. Zak / European Journal of Operational Research 141 (2002) 313327321andbrest brest ak:Step 5. Is the branch worth exploring? The branch potential is estimated by an upper bound
85、 of theknapsack tail functional. The knapsack tail starts with index k 1, and its optimal non-integer solution isxk1 brest=ak1, xk2 ? xm 0. So ifPki1cixi ck1brest=ak1 f?, then the branch is worth of ex-ploring. Go to step 2. Otherwise, go to step 4.This is a basic lexicographic algorithm. For Knapsa
86、ck III0, step 2 is complemented by checking thevalidity of the two-sided constraint (19). If the checking fails go to step 4.3.5. Finding a good initial solutionIt is desirable to start with a feasible solution close to the optimal. Looking back at Proposition 2 above,we conclude that an initial lis
87、t of intermediate rolls should at least include yminsince it may not be presentedby a linear combination of finished roll widths. Besides that to provide a warm starting we generate aninitial list of intermediate rolls using the following procedure.Start. The initial list is Y fy1g, where y1 ymin.It
88、eration. For each finished roll width wkwe identify an intermediate roll width ykasak ymax? emin=wk?;21yk emin wkak:22Obviously yk6ymax. If ykPymin, and it differs from the roll widths that are already in the list Y, then we willadd roll width ykto the list: Y : Y yk.Foreveryintermediaterollwidthykd
89、efinedby(21),(22)weidentifyacuttingpattern0? ? 1?0?ai?0 for finished roll i, where ai byk? emin=wic and )1 is associated with inter-mediate roll width yk. In a similar way we identify initial patterns for the first stage. The overall proceduremay be regarded as a generalization of the greedy procedu
90、re suggested by Chvatal 2.4. A sample problemSuppose there are four finished rolls to be cut. Two machines perform two-stage cutting consecutively:the first machine cuts stock rolls into intermediate rolls, and the second one cuts the intermediate rolls intofinished rolls. The input data are given i
91、n Tables 1 and 2.To start with, we will generate an initial solution. Let us restrict the initial list of intermediate rolls byone obligatory roll: y1 ymin 1200 mm. So we have one pattern for the first stage producing 1200 mmrolls and four patterns of the second stage for every finished roll.The ini
92、tial basis matrix is highlighted in Table 3. The objective function value is 60.777.Table 1Stock and finished rollsiwi(mm)biRoll type05000Stock132072Finished234088Finished3450150Finished4500108Finished322E.J. Zak / European Journal of Operational Research 141 (2002) 313327Table 4 shows the problem-s
93、olving dynamic. It is interesting to track how the algorithm generates newcolumns (patterns) and new rows (intermediate sizes). The problem was started with initial matrix seen inthe bold frame. Then patterns 9 and 10 were generated during column generation steps. Next an inter-mediate size of 1900
94、mm was generated along with two new patterns: pattern 11 and pattern 12. Then thealgorithm takes advantage of the new size and generates new columns 1316. Then a new intermediate sizeof 1690 mm was generated along with two new patterns 17 and 18, and so on.Table 2MachinesStageymin(mm)ymax(mm)emin(mm
95、)Maximum rolls out103212001900505Table 3Initial basis matrixTable 4The problem-solving dynamicE.J. Zak / European Journal of Operational Research 141 (2002) 313327323The algorithm finds an optimal solution with 36 sets of the first stage, in other words, 36 stock rolls areneeded to cut the ordered a
96、mount. How can we prove the optimality? We can calculate a lower bound byallowing all finished rolls to be cut directly at the first stage. The optimal solution of the relaxed problem,that is a single-stage CSP, is also 36 sets.It is interesting to note that the solution is a degenerate solution sin
97、ce only six non-zero basic variablesare in the basis of nine elements. The basic patterns are highlighted in Table 4. There are four intermediaterolls of 1200, 1390, 1710, and 1900 mm in the optimal solution.Next we will show how to improve the operational quality of the solution.5. Intermediate rol
98、ls reductionCeteris paribus, a schedule with the least number of different intermediate sizes is the most desirable. Thesituation is analogous to pattern reduction in the single-stage problem. The exact algorithms for solving thisproblem are still waiting for attention from the Operations Research c
99、ommunity. What we possess now area few heuristics that conduct post-optimal analysis trying iteratively to replace one intermediate roll withanother one that is already in the solution, or to replace two existing intermediate rolls by a new one, orthree existing intermediate rolls by two new ones, e
100、tc.Here we demonstrate how two-to-one conversion works. Let us look at the sample we just investi-gated. In the solution there are four intermediate rolls: 1200, 1390, 1710, and 1900 mm. In the patterns ofthe first stage we can notice that the only appearance of rolls of 1390 and 1710 mm is pattern
101、22, and bothrolls have factor 1. Let us attempt the following substitution:w w1 w2=2:23According to (23) we will define a new intermediate roll size 1550 mm 1390 mm 1710 mm=2. Sopattern 22 will be almost intact with one exception: instead of one appearance of 1390 and 1710 mm eachwe will get two app
102、earances of 1550 mm. Now we also should transform patterns of the second stageassociated with rolls of 1390 mm and 1710 mm. These patterns are 23 and 25. Please notice that these twopatterns have an identical number of sets 22. Now we can replace these two patterns by one pattern of1550 mm 50 mm 320
103、 mm 2 ? 340 mm 500 mm of 44 sets.So we have not degraded a solutions efficiency, but we have reduced the total number of intermediaterolls: instead of four different sizes we have three different sizes. It is a big improvement from an operationalpoint of view.Intermediate roll reduction techniques a
104、s demonstrated above proved to be simple but effective tools inimproving quality of solutions.6. ExperimentsThe main goals we pursued during the experiment were: to identify whether the one intermediate roll at a time rule provides a decent quality of solutions, to estimate how many intermediate siz
105、es are in solutions, and to estimate the effect of warm starting.We implemented the revised simplex algorithm with two extensions: column generation method, androw-and-column generation method using Microsoft Visual C+. We have developed a generator ofrandom two-stage problems. In addition, we ran a
106、 relaxation of each trim problem eliminating the secondcutting stage by allowing all finished rolls to be cut directly at the first stage. The problem relaxations weresolved with the regular column generation technique.324E.J. Zak / European Journal of Operational Research 141 (2002) 313327The compu
107、tational results are presented in Table 5, and Figs. 3 and 4. The computational experimentsbrought several surprises.1. The solutions found by row-and-column generation almost perfectly match its lower bounds definedby one-stage problems. We ran the program on randomly generated problems with sizes
108、between one orderand 50 orders. The exact parameters of the random generator are in Table 6. We calculated the gap as100%f ? fest=fest;24where f is a functional value, and festis the optimal value of the functional of the estimate problem.On a sample of 1000 randomly generated problems the maximum g
109、ap is 11.1%. It has been reached ontwo instances only, and both are tiny problems with three orders. Only eight instances had a gap over 0.5%.So in a few cases only optimality of the solutions is questionable.Table 5Computational results, minimum edge50 mmNumber of ordersNumber of patterns generated
110、Number of iterationsCPU time (seconds)101191912.281202566685.3283032613397.71940504296720.34350720327146.68760813663374.78170110310726205.93780110710667234.797909448842182.84310010119717231.641Fig. 3. Performance as a function of the number of orders.Fig. 4. Number of intermediate rolls in a solutio
111、n as a function of the number of orders.E.J. Zak / European Journal of Operational Research 141 (2002) 3133273252. The number of intermediate rolls in a solution is not a monotonic function of number of orders. Whenthe number of orders is small it increases reaching some modest values and after a ce
112、rtain point it startsdeclining. For large-scale problems the number of different intermediate sizes that are in solutions tends tobe a very small. The best explanation of this phenomenon is the following: as the number of orders grows,the second-stage patterns get so diverse that only a few intermed
113、iate sizes are required to provide highefficiency of the second-stage cutting. The high efficiency of the first stage cutting is guaranteed by choosingintermediate sizes to be well fit to the stock sizes. For example, in many instances only two intermediatesizes for 5000 mm stock sizes have been gen
114、erated: 1585 and 1830 mm providing a perfect first stagepattern: 2 ? 1585 mm 1830 mm. Of course, the problem may have solutions with a big number of in-termediate rolls but the advantage of the developed algorithm is that it can generate solutions with a few.3. Performance also turns out to be scala
115、ble. When the problem size is relatively small it has significantgrowth. The number of iterations is growing as Om2, where m is the number of finished sizes. But after acertain point, as we explained above, the growth stabilizes.4. Unexpectedly, the warm starting did not perform well. Moreover, whil
116、e warm starting was a valuableaddition for relatively small problems, it drove performance down for large problems, where in the end onlyfew intermediate rolls were used.As we expected, the data granularity or data accuracy affected the performance. Allowing all widths tobe rounded to integers of mi
117、llimeters instead of maintaining accuracy as small as half a millimeter, im-proved performance considerably.7. ConclusionsA cutting process spanning several stages brings another dimension to the CSP, making it even harderand therefore more challenging. Adequate modeling of multistage CSP results in
118、 two types of models: onewith a given set of intermediate sizes, and the other with unknown intermediate sizes. These models arecomplementary, and both should be implemented in commercial software packages for solving multistageCSP. The current results, especially an elegant row-and-column generatio
119、n technique, are very promisingfor effective solving large multistage models. Computational experiments demonstrate the procedures ef-fectiveness and the high quality of its solutions.Although we have demonstrated the technique for the case of a two-stage CSP, it can be adapted to ageneral case of a
120、 multistage CSP.AcknowledgementsThe author would like to thank Chris Rennick, and two anonymous referees for valuable comments andsuggestions that greatly improved the paper.Table 6Problem generator parametersParameterMinMaxDistributionStock size (mm)50005000Number of orders150UniformOrder width (mm
121、)300500UniformOrder amount10100UniformIntermediate width (mm)12001900UniformMinimum edge (mm)050Predetermined values326E.J. Zak / European Journal of Operational Research 141 (2002) 313327References1 J.M.V. Carvalho, A.J.G. Rodrigues, An LP-based approach to a two-stage cutting stock problem, Europe
122、an Journal ofOperational Research 84 (3) (1995) 580589.2 V. Chvatal, Linear Programming, Freeman, New York, 1983.3 H. Dyckhoff, Bridges between two principal model formulations for cutting stock processes, Paper for the Workshop onProduction Management in Pecs, Hungary, September 69, 1988, pp. 4051.
123、4 J.S. Ferreira, M.A. Neves, P.F. Castro, A two-phase roll cutting problem, European Journal of Operational Research 44 (2)(1990) 185196.5 P.C. Gilmore, R.E. Gomory, A linear programming approach to the cutting-stock problem, Operations Research 8 (1961) 849859.6 P.C. Gilmore, R.E. Gomory, A linear
124、programming approach to the cutting-stock problem. Part 2, Operations Research 11 (1963)863888.7 P.C. Gilmore, R.E. Gomory, Multistage cutting stock problems of two and more dimension, Operations Research 13 (1965) 94120.8 R.W. Haessler, A heuristic programming solution to a nonlinear cutting stock
125、problem, Management Science 17 (12) (1971) 793802.9 R.W. Haessler, Solving the two-stage cutting stock problem, Omega, The International Journal of Management Science 7 (2)(1979) 145151.10 M.P. Johnson, C. Rennick, E. Zak, Skiving addition to the cutting stock problem in the paper industry, SIAM Rev
126、iew 39 (3)(1997) 472483.11 S. Martello, P. Toth, Knapsack Problems Algorithms and Computer Implementations, Wiley, Chichester, 1990.12 E. Zak, Row and column generation technique for a multistage cutting stock problem, Computers and Operations Research,International Journal 29 (9) (2002) 11431156.E.J. Zak / European Journal of Operational Research 141 (2002) 313327327
