翻译原文.pdf

Modeling multistage cutting stock problems Eugene J Zak Majiq Inc 8343 154th Avenue NE Redmond WA 98052 USA Received 12 June 2000 accepted 28 August 2001 Abstract In multistage cutting stock problems CSP the cutting process is distributed over several successive stages Every stage 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 fi nished products suffi cient to meet customer demands If the intermediate sizes are given the column generation technique can be applied to multistage cutting 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 column generation The method uses an auxiliary problem embedded into the frame of the revised simplex algorithm It is a non linear knapsack problem that can be solved effi ciently In contrast to the column generation method the developed technique cannot guarantee the optimal solution However the results of computational experiments are very promising and prove that the method is a valuable addition to the set of tools for modeling and solving multistage CSPs 2002 Elsevier Science B V All rights reserved Keywords Linear programming Multistage cutting stock problem Large scale optimization Row and column generation 1 Introduction A one dimensional cutting stock problem CSP has an important practical generalization when a cutting process is distributed over several successive stages This multistage CSP includes not just cutting patterns and their activities but also the intermediate products and their quantities produced at every stage of the cutting process except the last one and consumed at every stage of the cutting process except the fi rst one These intermediate products are cut to produce smaller intermediate sizes or fi nished sizes The in termediate products are both output and input during the cutting process This kind of problem occurs in almost every industry where a classic CSP takes place paper fi lm leather steel etc Although the article s results are equally applicable to any industry where multistage cutting takes place for the purpose of subject area illustration we will use terminology accepted in the paper industry In particular we will refer European Journal of Operational Research 141 2002 313 327 Tel 1 452 881 7100 fax 1 452 881 5084 E mail address zak E J Zak 0377 2217 02 see front matter 2002 Elsevier Science B V All rights reserved PII S0377 2217 02 00127 3 to a roll as a product geometrically defi ned by its width Roll diameter total length of unrolled paper and paper 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 are used to produce nine types of fi nished rolls F1 F9 It is interesting to note that stock rolls can supply any stage of the process Here S1 goes to the fi rst stage S2 goes to the second and S3 goes to the third Conversely the fi nished rolls can be produced at any stage Three types of intermediate rolls I1 I2 and I3 are cut at the fi rst two stages Clearly we may see proliferation of stock types intermediate products and even cutting stages in real world problems Multistage is an overloaded word particularly in the Operations Research and CSP areas Gilmore and Gomory 7 refer to a two dimensional CSP solved by cutting strips along fi rst then by cutting the strips themselves across as a multistage problem In our case all cuts are along lengthwise and the problem is a one dimensional CSP Dyckhoff 3 introduced multistage for a so called one cut model with multistage cutting The one cut model is an extreme case opposed to a usual and well known case of a one stage problem with unlimited cuts It is interesting to note that those one cut and multi cut models are just two diff erent formulations of the same problem while in a real world situation the one stage CSP is often a relaxation of the multistage CSP The one stage relaxation provides a reasonable lower bound for the original multistage CSP Several researchers have attacked a multistage CSP Haessler 9 addresses a two stage problem with a winder at the fi rst stage and a production rewinder at the second He explores an LP approach with pattern generation either beforehand or during simplex iterations using a column generation technique He rep resents a winder pattern in terms of fi nished rolls and checks whether the pattern can be broken up into a combination of legitimate intermediate rolls If such a combination is permissible the pattern is admitted into the problem matrix Although the approach is workable it has some drawbacks It potentially in cludes a large number of diff erent intermediate rolls and defi ning whether a pattern can be partitioned is a complicated bin packing problem Also the approach does not scale easily to cutting processes with more than two stages Ferreira and others 4 also investigate the two stage problem which they refer to as a two phased problem The authors adapted Haessler s sequential heuristic procedure 8 initially developed for a classic CSP to a two stage cutting process At every step of the sequential procedure they are trying to fi nd a set of good intermediate rolls ensuring a good pattern for the fi rst stage and good patterns for the second If the pattern for the fi rst stage is accepted a residual problem in terms of fi nished rolls is updated reducing the Fig 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 313 327 ordered quantity by the amount defi ned by the pattern and its activity Apparently this heuristic resembles a manual procedure for solving a two stage CSP The main diffi culty with this heuristic is generating a set of good intermediate rolls Carvalho and Rodrigues 1 follow an LP approach Their problem however is subject to a techno logical restriction fi nished rolls of one width should comprise every intermediate roll The restriction allows for predefi ning a list of possible intermediate rolls The authors reformulate an initial LP problem posed in terms of fi nished rolls into a LP problem in terms of intermediate rolls A column generation technique 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 a row and column generation technique for solving a multistage one dimensional CSP The technique is a generalization of the seminal column generation technique suggested by Gilmore and Gomory 5 6 for solving 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 of rows corresponding to new intermediate rolls We expand both rows and columns in the LP matrix A fi nite number 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 are borrowed from the author s paper 12 2 Model with a given list of intermediate rolls There are three lists of roll sizes List of stock sizes List of intermediate sizes List of fi nished sizes Please see Fig 2 a which shows the relationship between these three types of rolls For stock sizes the available amounts are known Stock sizes can potentially be consumed at every stage of the cutting process and can be cut into intermediate or fi nished rolls Intermediate rolls are both input and output The technological constraints for intermediate rolls are strict for every size the total number of consumed rolls cannot exceed the produced amount Ideally there should be a total balance otherwise some excessive amount of unclaimed intermediate rolls should go to stock in a warehouse if there is storage space available But this is another question of tradeoff 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 considering an open problem with inequality constraints and we regard unclaimed intermediate rolls as waste For a fi nished roll we have an ordered amount that should be satisfi ed Here we consider a two stage CSP with one width of stock roll that is to be cut at the fi rst stage into several 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 fi rst stage and going to the second one satisfi es minimum maximum restrictions The width of every intermediate roll should also incorporate a minimum edge to be trimmed at the second stage Let w and y be vectors of the fi nished and intermediate roll widths respectively Cutting patterns of the fi rst stage and the second stage are represented by matrices A11and A22 respectively To make up a full LP matrix we defi ne another matrix A12showing the relations between the two Every column j of the con necting matrix A12is a vector 0 0 1 0 0 T where exactly one non zero element 1 appears in E J Zak European Journal of Operational Research 141 2002 313 327315 the position i corresponding to the intermediate roll i that should be cut according to the cutting pattern defi ned by column j in matrix A22 Now we can formulate an LP model for the multistage CSP Minimize1T0T x1 x2 1 subject to A11A12 0A22 x1 x2 P 0 b 2 x1 x2P0 3 Here vectors x1and x2 are pattern activities for the fi rst and the second stages respectively b is a vector of customer demands on fi nished rolls Fig 2 Graphs depicting roll relations a general case b case under consideration 316E J Zak European Journal of Operational Research 141 2002 313 327 The objective function 1 is to minimize the number of used stock rolls that is defi ned by the term 1Tx1 Constraints 2 ensure that consumption of intermediate rolls A12x2at the second stage should not exceed their production A11x1at the fi rst stage and customer demand of fi nished rolls b should be met Notice that the overall LP matrix has a special structure There are two diagonal blocks A11and A22 representing cutting patterns for two stages connecting block A12 and a block of 0 s in the lower left corner The right hand side is made up by 0 demand on intermediate rolls and the vector b Model 1 3 is a LP presentation of a two stage CSP that explicitly involves intermediate rolls The LP matrix might be full if 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 matrix remains unchanged since the list of possible intermediate sizes is given 2 1 Dual problem Let us consider the dual problem associated with 1 3 Maximize0TbT u1 u2 4 subject to AT 11 0 AT 12 AT 22 u1 u2 6 1 0 5 u1 u2P0 6 Here vectors u1and u2 are vectors of dual variables corresponding to intermediate rolls and fi nished rolls respectively The dual problem 4 6 leads to two types of auxiliary problem that should be solved at the column selection step of the revised simplex algorithm 2 2 Column generation The fi rst type of auxiliary problem is generation of a cutting pattern related to the fi rst stage of the cutting process The list of intermediate rolls remains unchanged Clearly this type is associated with the fi rst group of constraints 5 of the dual problem and the auxiliary problem is essentially the same knapsack problem as we have in a classic or a single stage CSP The auxiliary problem can be stated as the following knapsack problem Knapsack I MaximizeuT 1a subject toyTa6w0 aP0 and integer Hereu1 isavectorofobjectivefunctioncoeffi cientsthatarevaluesofthedualvariablesofthemasterproblem 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 fi rst stage is generated This condition immediately follows from the fi rst group of the constraints 5 which can be presented as uT 1A1161 T The solution vector enters as a column into matrix A11 E J Zak European Journal of Operational Research 141 2002 313 327317 The second type of auxiliary problem is associated with cutting patterns generated for fi nished rolls utilizing existing intermediate rolls This type is associated with the second group of constraints 5 For each intermediate roll yjwe should solve the following knapsack problem Knapsack II MaximizeuT 2a subject towTa6yj emin aP0 and integer Here u2 is a vector of objective function coeffi cients that are values of the dual variables of the master problem w is a vector of fi 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 function value exceeds u1j a new column a for the second stage is generated This condition immediately follows from the second group of the constraints 5 which can be presented as uT 2A226 u T 1A12 Given the matrix A12structure the right hand side boils down to a vector of dual variables corresponding to intermediate rolls 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 Knapsack I and Knapsack II are suffi cient to solve the problem optimally 3 Model with unknown intermediate rolls If intermediate rolls are unknown we face a more complicated situation We are free to pick any suitable intermediate size y from a given range ymin ymax Since every intermediate roll and a fi nished roll is as sociated with a row of the LP matrix uncertainty in the LP matrix stretches in both directions columns and rows 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 We can estimate the potential number of diff erent intermediate rolls in real life situations Let Dy be the range of intermediate roll widths Parameter Dy is machine dependent but usually Dy 800 mm Let d be the least roll width accuracy Normally d 0 5 mm Thus the number of diff erent rolls n Dy d This for mula gives us an estimate n 1600 Certainly for particular instances of the multistage CSP the estimate may 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 The great diversity in intermediate rolls at a time slows down the material fl ow complicates roll tracking tasks and provides less fl exibility in cutting operations Invariably a paper mill tends to operate with the least number of diff erent intermediate roll sizes Needless to say it would be highly desirable to have an intelligent approach generating intermediate rolls as 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 generation Along with Knapsack I and Knapsack II we may face a third type of auxiliary problem associated with simultaneous generation of new intermediate rolls and cutting patterns We should remember here that rows of the LP matrix present intermediate and fi nished rolls If we had constraints on stock rolls we would include stock rolls as additional rows as well The columns of the LP matrix are patterns for cutting stock rolls into intermediate rolls and intermediate rolls to fi nished ones 318E J Zak European Journal of Operational Research 141 2002 313 327 Here we are trying to adapt the revised simplex to a task that is not typical for it It is known that on every step of the revised simplex a column is entering the basis and replacing another column that is leaving the basis If columns are not known in advance we use a column generation technique expanding the LP matrix in the column direction Nothing in the revised simplex gives us the ability to generate unknown rows 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 on every step of the revised simplex Thus we are supposed to generate a new row of the LP matrix and in the non degenerate case the rank of the LP matrix will be eff ectively increased by 1 The basis matrix should also be expanded by one row and one column and since only one column leaves the basis during a pivoting step we conclude that two new columns should actually be generated during a simplex step One of them should be added up to the basis matrix unconditionally and the other one should replace the existing one in a pivoting step Let vector y be intermediate roll sizes that have been in the model so far variable z be a new intermediate roll size and v be a corresponding dual variable We face the following nonlinear integer programming problem Knapsack III MaximizeuT 1a11 va 7 subject toyTa11 za6w0 8 wTa226z emin 9 uT 2a22 v 10 vP0 11 ymin6z6ymax 12 a11 a22P0 and integers 13 The variables here are two new columns column a11 for the fi rst stage and column a22for the second stag