[机械模具数控自动化专业毕业设计外文文献及翻译]【期刊】多级下料问题的建模-外文文献

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 last 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 nished products sucient to meetcustomer demands. If the intermediate sizes are given, the column generation technique 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 row-and-columngeneration. 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 eciently. In contrastto the column generation method the developed technique cannot guarantee the optimal solution. However, 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. C211 2002 Elsevier Science B.V. All rights reserved.Keywords: Linear programming; Multistage cutting stock problem; Large-scale optimization; 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 intermediate 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 rstone. These intermediate products are cut to produce smaller intermediate sizes or nished sizes. The in-termediate products are both output and input during the cutting process. This kind of problem occurs inalmost every industry where a classic CSP takes place: paper, lm, leather, steel, etc. Although the articlesresults are equally applicable to any industry where multistage cutting takes place, for the purpose ofsubject area illustration, we will use terminology accepted in the paper industry. In particular, we will referEuropean Journal of Operational Research 141 (2002) 313327/locate/dsw*Tel.: +1-452-881-7100; fax: +1-452-881-5084.E-mail address: (E.J. Zak).0377-2217/02/$ - see front matter C211 2002 Elsevier Science B.V. All rights reserved.PII: S0377-2217(02)00127-3to a roll as a product geometrically dened 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, S2, and S3 areused to produce nine types of nished rolls (F1F9). It is interesting to note that stock rolls can supply anystage of the process. Here, S1 goes to the rst stage, S2 goes to the second, and S3 goes to the third.Conversely, the nished rolls can be produced at any stage. Three types of intermediate rolls I1, I2, and I3are cut at the rst 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 refer to a two-dimensional CSP solved by cutting strips along rst, 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. Dyckho 3 introduced multistage for a so-called one-cut modelwith multistage 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 dierent formulations of the same problem, while in a real-world situation the one-stage CSP 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 rst stage and a production rewinder at the second. 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 nished rolls and checks whether the pattern can be broken up into acombination of legitimate intermediate rolls. If such 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 dierent intermediate rolls, and dening whether a pattern can be partitioned is acomplicated bin-packing problem. Also, 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 two-stage cutting process. At every step of the sequential procedure they are trying to nd a set ofgood intermediate rolls ensuring a good pattern for the rst stage and good patterns for the second. If thepattern for the rst stage is accepted, a residual problem in terms of nished rolls is updated, 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.314 E.J. Zak / European Journal of Operational Research 141 (2002) 313327ordered quantity by the amount dened by the pattern and its activity. Apparently, this heuristic resemblesa manual procedure for solving a two-stage CSP. The main diculty 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 restriction nished rolls of one width should comprise every intermediate roll. The restrictionallows for predening a list of possible intermediate rolls. The authors reformulate an initial LP problemposed in terms of nished rolls into a LP problem in terms of intermediate rolls. A column generationtechnique 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 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 column-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 nitenumber of iterations of simplex algorithm lead either to an optimal or a near-optimal solution.In the next sections we will formulate 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 sizes. List of intermediate sizes. List of nished 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 or nished 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 intermediate rolls should go to stock in a warehouse, if there is storage spaceavailable. But this is another question of tradeo between 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 problem with inequality constraints, and we regard unclaimed intermediate rolls as waste. For anished roll we have an ordered amount that should be satised.Here we consider a two-stage CSP with one width of stock roll that is to be cut at the rst stage intoseveral intermediate rolls (Fig. 2(b). Finished 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 rst stage and going tothe second one satises minimummaximum restrictions. The width of every intermediate roll should alsoincorporate a minimum edge to be trimmed at the second stage.Let w and y be vectors of the nished and intermediate roll widths, respectively. Cutting patterns of therst stage and the second stage are represented by matrices A11and A22, respectively. To make up a full LPmatrix we dene another matrix A12showing the relations between the two. Every column j of the con-necting matrix A12is a vector 0; .;0;C01;0; .;0T, where exactly one non-zero element )1 appears inE.J. Zak / European Journal of Operational Research 141 (2002) 313327 315the position i corresponding to the intermediate roll i that should be cut according to the cutting patterndened by column j in matrix A22.Now we can formulate an LP model for the multistage CSP:Minimize 1T0TC0C1x1x2C18C191subject toA11A120 A22C18C19x1x2C18C19P0bC18C19; 2x1;x2P0: 3Here vectors x1and x2are pattern activities for the rst and the second stages, respectively; b is a vector ofcustomer demands on nished rolls.Fig. 2. Graphs depicting roll relations: (a) general case; (b) case under consideration.316 E.J. Zak / European Journal of Operational Research 141 (2002) 313327The objective function (1) is to minimize the number of used stock rolls that is dened by the term 1Tx1.Constraints (2) ensure that consumption of intermediate rolls A12x2at the second stage should not exceed their production A11x1atthe rst stage, and customer demand of nished rolls b should be met.Notice that the overall LP matrix has a special structure. There are two diagonal blocks A11and A22representing cutting 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 fullif 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 rows 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):Maximize 0TbTC0C1u1u2C18C194subject toAT110AT12AT22C18C19u1u2C18C19610C18C19; 5u1;u2P0: 6Here vectors u1and u2are vectors of dual variables corresponding to intermediate rolls and nished 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 rst type of auxiliary problem is generation of a cutting pattern related to the rst stage of thecutting process. The list of intermediate rolls remains unchanged. Clearly, this type is associated with therst 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 auxiliary problem can be stated as thefollowing knapsack problem:Knapsack I Maximize uT1asubject to yTa6w0;aP0;and integer:Hereu1isavectorofobjectivefunctioncoecientsthatarevaluesofthedualvariablesofthemasterproblem;y is a vector of intermediate roll widths; w0is the stock roll width and vector a is a vector of variables.If the objective function value exceeds 1.0, a new column a for the rst stage is generated. This conditionimmediately follows from the rst group of the constraints (5) which can be presented as uT1A1161T. Thesolution vector enters as a column into matrix A11.E.J. Zak / European Journal of Operational Research 141 (2002) 313327 317The second type of auxiliary problem is associated with cutting patterns generated for nished rollsutilizing existing intermediate rolls. This type is associated with the second group of constraints (5). Foreach intermediate roll yjwe should solve the following knapsack problem:Knapsack II Maximize uT2a;subject to wTa6yjC0 emin;aP0;and integer:Here u2is a vector of objective function coecients that are values of the dual variables of the masterproblem; w is a vector of nished sizes; eminis a mandatory minimal edge, eminP0; yjis width of 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 constraints (5) which can be presented as uT2A226 C0uT1A12. 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 types of knapsacks shown above KnapsackIand Knapsack II are sucient 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. Since every intermediate roll and a nished 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 intermediate rolls may preclude generating all possibilities beforehand. Wecan estimate the potential number of dierent intermediate rolls in real life situations. Let Dy be the rangeof intermediate roll widths. Parameter Dy is machine-dependent, but usually Dy C25 800 mm. Let d be theleast roll width accuracy. Normally, d 0:5 mm. Thus the number of dierent rolls n C25 Dy=d. This for-mula gives us an estimate n C25 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 against advanced intermediate roll generation is an operational issue. Thegreat diversity in intermediate rolls at a time slows down the material ow, complicates roll-tracking tasks,and provides less exibility in cutting operations. Invariably a paper mill tends to operate with the leastnumber of dierent 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-and-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 nished rolls. (If we had constraints 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 nished ones.318 E.J. Zak / European Journal of Operational Research 141 (2002) 313327Here we are trying to 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 LPmatrix 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 roll 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 eectively increased by 1. The basis matrix shouldalso be expanded by one row and one column, and since only one column leaves the basis 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 been in the model so far, variable z be a new intermediateroll size, and