《外文翻译--计算机与运筹学研究一种最佳切割方式的确定算法英文版》由会员分享，可在线阅读，更多相关《外文翻译--计算机与运筹学研究一种最佳切割方式的确定算法英文版（18页珍藏版）》请在金锄头文库上搜索。
1、*Corresponding author. Tel.: #30-31-498-143; fax: #30-31-498-180.E-mail address: georgiadcperi.certh.gr (M.C. Georgiadis).Computers & Operations Research 29 (2002) 10411058An algorithm for the determination of optimal cutting patternsGordian Schilling?, Michael C. Georgiadis?*?Ciba Specialty Chemica
2、ls Inc., CH-1870 Monthey, Switzerland?Centre for Research and Technology - Hellas, Chemical Process Engineering Research Institute, P.O. Box 361,Thermi 57001, Thessaloniki, GreeceReceived 1 June 2000; received in revised form 1 September 2000; accepted 1 October 2000AbstractThis paper presents a new
3、 mathematical programming formulation for the problem of determining theoptimal manner in which several product rolls of given sizes are to be cut out of raw rolls of one or morestandard types. The objective is to perform this task so as to maximize the prot taking account of therevenuefrom the sale
4、s, the costs of the original rolls, the costs of changingthe cutting pattern and the costs ofdisposal of the trim. A mixed integer linear programming (MILP) model is proposed which is solved toglobal optimality using standard techniques. A number of example problems, including an industrial casestud
5、y, are presented to illustrate the e$ciency and applicability of the proposed model.Scope and purposeOne-dimensional cutting stock (trim loss) problems arise when production items must be physicallydivided into pieces with a diversity of sizes in one dimension (e.g. when slitting master rolls of pap
6、er intonarrower width rolls). Such problems occur when there are no economies of scale associated with theproduction of the larger raw (master) rolls. In general, the objectives in solving such problems are to 5:? minimize trim loss;? avoid production over-runs and/or;? avoid unnecessary slitter set
7、ups.The above problem is particularly important in the paper converting industry when a set of paper rolls needto be cut from raw paper rolls. Since the width of a product is fully independent of the width of the raw papera highly combinatorial problem arises. In general, the cutting process always
8、produces inevitable trim-losswhichhas to be burnedor processedin somewaste treatmentplant. Trim-lossproblems inthe paper industryhave, in recent years, mainly been solved using heuristic rules. The practical problem formulation has,therefore, in most cases been restricted by the fact that the soluti
9、on methods ought to be able to handle theentire problem. Consequently, only a suboptimal solution to the original problem has been obtained and0305-0548/02/$-see front matter ? 2002 Elsevier Science Ltd. All rights reserved.PII: S 0 3 0 5 - 0 5 4 8 ( 0 0 ) 0 0 1 0 2 - 7very often this rather signica
10、nt economic problem has been left to a manual stage. This work presentsa novel algorithm for e$ciently determining optimal cutting patterns in the paper converting process.A mixed-integer linear programming model is proposed which is solved to global optimality using availablecomputer tools. A numbe
11、r of example problems including an industrial case study are presented to illustratethe applicability of the proposed algorithm. ? 2002 Elsevier Science Ltd. All rights reserved.Keywords: Integer programming; Optimization; Trim-loss problems; Paper converting industry1. IntroductionAnimportantproble
12、mwhich is frequentlyencounteredin industriessuch as paperis related withthe most economic manner in which several product roll of given sizes are to be produced bycutting one or more wider raw rolls available in one or more standard widths. The solution of thisproblem involves several interacting de
13、cisions:? The number of product rolls of each size to be produced.This maybe allowedto varybetweengivenlower andupper bounds.The former normallyre#ectthe rm orders that are currently outstanding, while the latter correspond to the maximumcapacity of the market. However, certain discounts may have to
14、 be o!ered to sell sheets over andabove the quantities for which rm orders are available.? The number of raw rolls of each standard width to be cut.Rolls may be available in one or more standard widths, each of a di!erent unit price.? The cutting pattern for each raw roll.Cutting takes place on a ma
15、chine employing a number of knives operating in parallel on a roll ofstandard width. While the position of the knives may be changed from one roll to the next, suchchanges may incur certain costs. Furthermore, there may be certain technological limitations onthe knife positions that may be realized
16、by any given cutting machine.The optimal solution of the above problem is often associated with the minimization of thetrima waste that is generally unavoidable since rolls of standard widths are used. However,trim-loss minimization does not necessarily imply minimization of the cost of the raw mate
17、rials(rolls) being used especially if several standard roll sizes are available. A more direct economiccriterion is the maximization of the prot of the operation taking account of:? the revenue from product rolls sales, including the e!ects of any bulk discounts;? the cost of the rolls that are actu
18、ally used;? the costs, if any, of changing the knife positions on the cutting machine;? the cost of disposing of trim waste.The above constitutes a highly combinatorial problem and it is not surprising that traditionallyits solution has often been carried out manually based on human expertise. The s
19、implied versionof this problem is similar to the cutting stock problem known in the operation-research literature,where a number of ordered pieces need to be cut o! bigger stored pieces in the most economicfashion. In the 1960s and the 1970s, several scientic articles were published on the problem o
20、f1042G. Schilling, M.C. Georgiadis / Computers & Operations Research 29 (2002) 10411058minimizing trim loss, e.g. 1,2. Hinxman 3 presents a good overview of the available solutionmethods for trim-loss and assortment problems.Gilmore and Gomory 1 presented a basic linear programming approach to the c
21、utting stockproblem while relaxing some integer-characters of the problem. Gilmore and Gomory 2 de-scribed an iterative solution method that is suitable for very large number of orders and iscomputational cheap, but the resulting values for the number of cutting patterns to be used arenon-integer an
22、d it is not possible to prove the optimality or indicate the margin of optimality ofthese cutting patterns. Thus, the rounding values obtained by the algorithm of Gilmore andGomory 2 may very probably result in poor economic performance. Wascher 4 presenteda linear programming approach to cutting st
23、ock problems taking into account multiple objectivessuch as cost of the raw materials, cost of the overproduction storage, trim-loss removal costs, etc.Sweeny 5 proposed a heuristic procedure for solving one-dimensional cutting stock problemswith multiple quality grades. Ferreira et al. 6 considered
24、 the two-phase roll cutting problemsbased on a heuristic approach. Gradisar et al. 7 presented an e$cient sequential heuristicprocedure and a software tool for optimization of roll cutting in the clothing industry. Later,Gradisaret al. 8 developedan improvedsolution strategy based on a combination o
25、f approxima-tions and heuristics leading to almost optimal solutions for the one-dimensional stock cuttingproblems. A software tool was also developed.In recent years, integer programming techniques have been used for the solution of the trim-lossand production optimization problem in the paper indu
26、stry. The work of Westerlund andcoworkers at A ? bo Akademi University in Finland is a key contribution in this area. Harjunkoski9 considered a mathematicalprogrammingapproachto the trim-lossproblemand presentedtwodi!erent types of formulation. In the rst one, both the cutting patterns that need to
27、be used andthe number of rolls that have to be cut according to each such pattern are treated as unknowns.This results in an integer nonlinear mathematical problem (INLP) involving bilinear problems ofthe variables characterizing each cutting pattern and the corresponding number of rolls cut in this
28、way. Two di!erent ways of linearizing the INLP to obtain a mixed integer linear programming(MILP) mode were presented. However, these linearizations often result in a signicant increase inthe number of variables and constraints, as well as a large integrality gap. The second type offormulation prese
29、nted by Harjunkoski 9 is based on using a xed set of cutting patterns that isdecided a priori. This results in a MILP that has a much smaller integrality gap than the oneresulting from the linearization of the INLP formulation mentioned above. However, the solutionobtained is guaranteed to be optima
30、l only if all non-inferior cutting patterns are identied andtaken into consideration. The number of such patterns may be quite substantial for realisticindustrial problems. Extending the above work, Harjunkoski 10 presented linear and convexformulations for solving the non-convex trim-loss problems.
31、Westerlund 11 considered the two-dimensional trim-loss problem in paper converting. A non-convex optimization model was proposed where both the widths and the lengths of the raw paperwere considered as variables. A two-step solution procedure was used where all feasible cuttingpatterns were rst gene
32、rated and then a MILP problem was solved. In a similar fashion, theproduction optimization problem in the paper converting industry was addressed by Westerlund12. Scheduling aspects of the cutting machines in paper converting were simultaneously con-sidered with the trim-loss problem by Westerlund 1
33、3. Recently, Harjunkoski 14 incorporatedenvironmental impact considerations into a general framework for trim-loss minimization.G. Schilling, M.C. Georgiadis / Computers & Operations Research 29 (2002) 104110581043This paper presents an alternative mathematical programming formulation that results d
34、irectlyin a MILP of small integrality gap. The salient feature of this model is that it does not requirea priori enumeration of all possible cutting patterns. The next section presents a formal statementof the problem under consideration and the notation used. Section 3 considers the mathematicalfor
35、mulation of the objective function and the operational constraints. This is followed by someexample problems including an industrial case study illustrating the applicability and computa-tional behavior of the proposed formulation.2. Problem statement and dataThe task being considered here is to pro
36、duce product rolls of I di!erent types, the width of typei being denoted by B?, i1,2,I from one or more standard rolls. The lengths of all raw rolls andof the product rolls resulting from them are assumed to be identical and xed. It is beyond thescope of this work to consider the two-dimensional pro
37、blem where both the widths and the lengthsof raw paper rolls and the cutting patterns are considered variables.Product rolls are mostly produced to order. The minimum ordered quantity for product rolls ofwidth i is denoted by N?and is given, and so is the corresponding unit price p?. However,custome
38、rs may be willing to buy additional rolls of type i up to a maximum quantity N?subjectto a discount of c?for each product roll over and above the minimum number N?. In general,the number of additional rolls sold in this manner tends to be rather small since the main incentiveof such discounting from
39、 the point of view of the manufacturer is merely to decrease the lossthrough trim.The product rolls are to be cut from raw rolls of di!erent standard types. The unit price fora raw roll of type t is denoted by c?and its nominal width by B?. However, the useful width ofa roll of type t is determined
40、by the cutting machine used. In particular, each raw roll typet1,2, is characterized by a maximum possible total engagement B?denoting the maximumtotal width of all product rolls that can be cut from a raw roll of this type. There may also bea minimum required total engagement B?for this type of rol
41、l. In generalB?)B?)B?,t1,2,.The maximum number N?of product rolls that can be cut out of a raw roll of type t willgenerally be determined by the knives and other characteristics of the available machine.Moreover,in some cases, there maybe limitationsin the available number JH?of raw rolls of a given
42、type t.The cutting pattern for each raw roll is determined by the position of the knives. Frequentchanges in these positions are generally undesirable. Each such change may therefore be associatedwith a non-zero cost c?.The production of the required product rolls from the available raw rolls may re
43、sult in trimwaste which may need to be disposed of. The cost of such disposal per unit width of trim is denotedby c?.Based on the given data, we rst derive an upper bound J on the number of raw rolls that mayneed to be cut. This is obtained by assuming that the maximum number N?of product rolls ofea
44、ch type i will be produced; that raw rolls of the type t that permits the smallest minimum1044G. Schilling, M.C. Georgiadis / Computers & Operations Research 29 (2002) 10411058engagement B?will be used; and that each raw roll will be used to produce product rolls ofa single type only. Overall, this
45、leads to the following upper bound on the number of raw rolls thatmay be required:J?N? min?B?/B?.(1)We can also calculate a lower bound J? on the minimum number of raw rolls that arenecessary to satisfy the minimum demand for the existing orders. We do this by assuming that rollsof the type t allowi
46、ng the maximum possible engagement B?are used, and that no trim isproduced. However, we must also take account of possible limitations on the number of availableknives. Overall, this leads to the following lower bound on the number of rolls that maybe required:J?max?N?B?max?B?,?N?max?N?.(2)3. Mathem
47、atical formulationThe aim of the mathematical formulation is to determine the type t of each raw roll j to be cutand the number of product rolls of each type i to be produced from it.3.1. Key variablesThe following integer variables are introduced:n?: number of product rolls of type i to be cut out
48、of raw roll j?: number of product rolls of type i produced over and above the minimum number ordered.We note that n?cannot exceed:? the maximum number N?of product rolls of type i that can be sold;? the maximum number of product rolls of width B?that can be accommodated within a max-imum engagement
49、B?for a raw roll of type t;? the maximum number N?of knives that can be applied to a raw roll of type t.This leads to the following bounds for n?:0)n?)min?N?, max?B?B?, max?N?i1,2,I, j1,2,J?.(3)Also0)?)N?!N?,i1,2,I.(4)G. Schilling, M.C. Georgiadis / Computers & Operations Research 29 (2002) 10411058
50、1045We note that ?need to be included in the model only if N?N?. We also introduce thefollowing binary variables:y?1if the jth roll to be cut is of type t,0otherwise.z?1if the cutting pattern for paper roll j is different to that for roll j!1,0otherwise.We note that, in general, the index j will be
51、in the range 1,2,J?. However, the formulationto be presented will assign a type t only to the raw rolls j that are actually used. Hence, the totalnumber of rolls to be cut will also be determined by the solution of the optimization problem. Thiswill become clearer in the next subsection.3.2. Roll ty
52、pe determination constraintsEach raw roll j to be cut must be of a unique type t. This results in the following constraints:?y?1,j1,2,J?,(5a)?y?)1,jJ?#1,2,J?.(5b)Note that for jJ?, it is possible that y?0 for all types t; this simply implies that it is notnecessary to cut roll j.Furthermore, the lim
53、ited availability of raw rolls of a given type t may be expressed in terms ofthe constraint?y?)JH?,t1,2,.(6)3.3. Cutting constraintsWeneed to ensure that, if a roll j is to be cut, then the limitations on the minimumand maximumengagement are observed. This is achieved via the constraints?B?y?)?B?n?)
54、?B?y?,j1,2,J?.(7)We note that the quantity ?B?n?represents the total width of all product rolls to be cut out ofraw roll j. If y?1 for some roll type t, then constraint (7) ensures thatB?)?B?n?)B?.1046G. Schilling, M.C. Georgiadis / Computers & Operations Research 29 (2002) 10411058On the other hand
55、, if y?0 for all t, then constraint (7) e!ectively forces n?0 for all i1,2,I.This expresses the obvious fact that if roll j is not actually cut, then no product rolls of any type canbe produced from it.We also need to ensure that the number of product rolls cut out of any roll j of type t does notex
56、ceed the number of knives that can be deployed on rolls of this type. This is written as0)?n?)?N?y?,j1,2,J?.(8)3.4. Production constraintsThe total number of product rolls of each type i that are produced comprises the minimumordered quantity N?for this type plus the surplus production ?:?n?N?#?,i1,
57、2,I.(9)These constraints, together with the bounds on ?, ensure that the quantity of product rolls of typei produced lies between the minimum and maximum bounds N?and N?, respectively.3.5. Changeover constraintsIf changing the cutting pattern incurs a non-zero cost c?0, we need to determine whensuch
58、 changes will take place. To this end, we include the following constraint:!M?z?)n?!n?)M?z?,i1,2,I, j2,2,J?.(10)Note that this will allow z?to be zero only if n?n?for all product rolls i, i.e. if rolls j and j!1are cut in exactly the same way. Here, the constant M?is an upper bound on n?(see Section
59、 3.1).3.6. Objective functionThe objective of the optimization is to maximize the total prot of the operation taking accountof:? The income from the sales of product rolls of each type i.This comprises the income from selling the minimum ordered quantities N?at the full unitprice p?, plus the income
60、 of selling the additional quantities ?at the discounted unit pricep?!c?:?(p?N?#?(p?!c?).? The costs of the rolls to be cut.Generally, the cost of each roll depends on its type. The total cost can be written as?c?y?.G. Schilling, M.C. Georgiadis / Computers & Operations Research 29 (2002) 1041105810
61、47We note that, for each roll j, at most one term of the inner summation is non-zero (cf. constraints(5a) and (5b).? The costs of changing the positions of the knives.In general, the knife positions have to be changed if the cutting pattern used for a given roll j isdi!erent to that for the previous
62、 one. This is determinedby the variablesz?and results in the costtermc?z?,where the summation is equal to the total number of changes that are necessary.? The cost of disposing of any trim produced.The width of trim produced out of raw roll j is given by the di!erence between the roll width andthe t
63、otal width of all product rolls cut from it. The former quantity depends on the type of theroll and can be expressed as ?B?y?; once again, at most one of the terms in this summationcan be non-zero (cf. constraints (5a) and (5b). The latter quantity is given by ?B?n?. Overall,trim disposal results in
64、 the following cost termc?B?y?!?B?n?.The above terms can now be collected in the following objective function:max?(p?N?#?(p?!c?)!?c?y?!c?z?!c?B?y?!?B?n?.(11)Note that the rst term in the above objective function (i.e. ?p?N?) is actually a constant anddoes not a!ect the optimal solution obtained.3.7.
65、 Degeneracy reduction and constraint tighteningIn general, the basic formulation presented above is highly degenerate: given any feasible point,one can generate many others simply by forming all possible ordering of the rolls selected to be cut.Moreover,provided all raw rolls of the same type are cu
66、t consecutively, all these feasible points willcorrespond to exactly the same value of the objective function.Theabove propertymay haveadversee!ects on the e$ciencyof the searchprocedure.Therefore,in order to reduce the solution degeneracy without any loss of optimality, we introduce thefollowing or
67、dering constraints:?n?*?n?,j2,2,J?.(12)This ensures that the total number of product rolls cut out of raw roll j!1 is never lower than thecorresponding number for roll j; all completely unused raw rolls are left last in this ordering.1048G. Schilling, M.C. Georgiadis / Computers & Operations Researc
68、h 29 (2002) 10411058An alternative would be to order the raw rolls in non-increasing utilization order, i.e.?B?n?*?B?n?,j2,2,J?.However, our practical experience indicates that this is not as e!ective as constraint (12).We also note that the constraints (7) implicitly impose a lower bound on the tot
69、al number ofproduct rolls ?n?cut out of a raw roll j. A stronger bound may sometimes be obtained byconsidering a roll of type t being used at the minimum possible engagement to produce the widestpossible product rolls. This leads to the constraints?B?max?B?y?)?n?,j1,2,J?.(13)3.8. CommentsThe objecti
70、vefunction and all constraints introducedin this section are linear. Since all variablesare integer valued, the formulation presented corresponds to an integer linear programming (ILP)problem. However, constraints (9) ensure that the variables ?will automatically assume integervalues provided variab
71、les n?do so. Therefore, ?may be treated as continuous quantities, whichleaves us with a mixed integer linear programming (MILP) problem. In principle, the latter can besolved using standard MILP solvers.In the special (but quite common) case where only one type of roll is available, constraints (5a)
72、simply imply that y?can be xed to 1 for all j1,2,J?. Both (5a) and (5b) are otherwiseredundant and may be dropped. Furthermore, the lower bound on constraint (7) is directlyincluded in the bounds of the corresponding slack variable, 0; B?!B?, which results in oneless constraint for each roll j.4. Ex
73、ample problemsIn this section, we consider four example problems of increasing complexity in order toinvestigatethe computationalbehaviorof our formulation.Furthermorean industrial case study isalso presented. In all cases, we assume that the maximum raw roll engagement B?is equal to thecorrespondin
74、groll widthB?.The GAMS/CPLEXvs 6.0 solverhas beenused for the solution15and all computations were carried out on a AlphaServer 4100. An integrality gap of 0.1% wasassumed for the solution of all problems.4.1. Example 1Our rst example is based on that given by Harjunkoski 9. Some translation of the v
75、ariouscost coe$cients was necessary to account for slight di!erences in the objective functions used bythe two formulations.Also note that the objective used by those authors is the minimizationof costas opposed to the maximization of prot; therefore, the sign of their objective function is opposite
76、to that of ours.G. Schilling, M.C. Georgiadis / Computers & Operations Research 29 (2002) 104110581049Table 1Raw roll characteristics for Example 1Roll typeWidth B?Max. spill B?!B?Max. cuts N?Cost c?11900 mm200 mm51900Table 2Production data for Example 1Product rolltype iWidth B?(mm)Min. quantityN?M
77、ax. quantityN?Pricep?Discountc?1330810297.00236078324.0033851213346.5044151111373.50?Each vertical bar corresponds to a di!erent roll being cut. The corresponding roll type is shown immediately aboveeach bar. Each bar is divided into a number of segments corresponding to sheets of the indicated type
78、. The dark shadedsegment at the top of the bar is the trim-loss, the percentage width of which is indicated numerically at the bottom of thegure.The problem aims to determine the optimal cutting pattern for producing four di!erent types ofproduct rolls from a single type of raw roll. The characteris
79、tics of the latter are shown in Table 1.The production requirements are summarized in Table 2. The cost for changing the cutting patternis 1, while disposing of the trim incurs no cost.Harjunkoski 9 assumed a maximum of four di!erent cutting patterns, which results ina reduction of the size of the m
80、odel. In our case, the number of such patterns is determined by thesolution. Also from expressions (1) and (2), we determine J?10 and J?8. We therefore xy?1, for j1,2, 8.The solution we obtain is the same as that reported by Harjunkoski 9 involving the productionof the minimum ordered amounts of pro
81、duct rolls plus one extra roll of type 2 and another of type 3.The solution is presented pictorially in Fig. 1? and corresponds to an objective function value of!1622.0; thus, with the given economic data the operation incurs a loss.The optimal solution (within a margin of optimality of 0.1%) is fou
82、nd within less than 1 CPU sat node 49 of the branch-and-bound algorithm using a breadth rst search strategy. It must benoted that the integrality gap of our formulation is comparable to that for one of the formulationspresented by Harjunkoski 9 despite the fact that it does not employ any a priori e
83、numeration ofthe cutting patterns. Our formulation also examines a small number of nodes in order to detect theoptimal point (Table 3).1050G. Schilling, M.C. Georgiadis / Computers & Operations Research 29 (2002) 10411058Fig. 1. Solution of Example 1.Table 3Computational statistics for Example 1Opti
84、malobjectiveFully relaxedobjectiveIntegralitygap (%)Nodesin B&BVariables(Bin/Int/Cont)Constraints(!)1622.0(!)1619.40.184960(13/44/3)1154.2. Example 2The data for this problem are given in Tables 4 and 5. There is no cost for changing the cuttingpattern or for disposing of trim. Using expressions (1)
85、 and (2), it is possible to calculate a priori thatthe number of raw rolls required will be between 11 and 15.Although this problem involves only 9 types of product rolls, there are a total of 3971 di!erentcutting patterns, all of which are feasible with respect to the minimum and maximum allowed to
86、talengagement of the rolls, the maximum number of knives that can be applied to a roll and themaximum quantities of sheets ordered. Thus, any formulation that relies on explicit patternenumeration would have to involve a large number of discrete variables. This is, of course,a well-known problem wit
87、h the classical approach to the cutting stock problem.Our algorithm obtains the exact (0% optimality margin) optimal solution for this problemwithin less than 1 CPU s. This solution is presented in Fig. 2. Computational performancestatistics are given in Table 6.G. Schilling, M.C. Georgiadis / Compu
88、ters & Operations Research 29 (2002) 104110581051Table 4Raw roll characteristics for Example 2Roll typeWidth B?Max. spill B?!B?Max. cuts N?Cost c?11900 mm200 mm51600Table 5Production data for Examples 2 and 3Product rolltype iWidth B?(mm)Min. quantityN?Max. quantityN?Pricep?Discountc?1340810C 340C 0
89、236578C 365C 033851213C 385C 04415111C 415C 0543555C 435C 0626068C 260C 0730044C 300C 0832078C 320C 0933533C 335C 0Fig. 2. Solution of Example 2.1052G. Schilling, M.C. Georgiadis / Computers & Operations Research 29 (2002) 10411058Table 6Computational statistics for Examples 2, 3 and 4FormulationOpt
90、imalFully relaxedIntegralityNodesVariablesConstraintsobjectiveobjectivegap (%)in B&B(Int/Bin/Cont)Example 22590.02630.01.5443173(6/162/5)61Example 33030.03030.00131203(36/162/5)116Example 41240.01279.33.1614,800173(6/162/5)61Table 7Raw roll characteristics for Example 3Roll typeWidth B?Max. spill B?
91、!B?Max. cuts N?Cost c?11900 mm200 mm5C 160022200 mm250 mm6C 18504.3. Example 3Thisexample is similar to Example2, the only di!erencebeing that up to 6 raw rolls of a di!erenttype are now also available to be cut (see Table 7). Since a wider roll is now available, the minimumnumber J? of required rol
92、ls is reduced to 9 (from 11 in Example 2), but the maximum numberJ? of rolls remains the same, namely 15.The exact (0% optimality margin) optimal solution was obtained in less than 1 CPU s. Thesolution is presented in Fig. 3 with the computationalperformance statistics shown in Table 6. Themaximum p
93、ossible number of raw rolls of type 2 is used. It is interesting to mention that, if noupper limit on the number of raw rolls of type 2 is imposed, only rolls of this type are actuallyengaged. This then results in a higher prot of C 3380.4.4. Example 4This example is similar to Example 2, the only d
94、i!erence being that the cost coe$cients forchanging the cutting pattern, c? and for disposing of waste trim, c? are equal to 10 and 1,respectively. The computational performance is shown in Table 6. We observe that a considerablelarger number of nodes in the branch-and-bound tree is required compari
95、ng with Example 2.However, the integrality gap is relatively small.4.5. Example 5One justied concern with our formulation is the way in which the computational cost mayincrease with the number of orders that have to be satised. This is because more orders willG. Schilling, M.C. Georgiadis / Computer
96、s & Operations Research 29 (2002) 104110581053Fig. 3. Solution of Example 3.Table 8Computational statistics for Example 5Example 2OptimalFullyrelaxedNodes inB&BCPU(s)Variablesint/contConstraintsNumber of rollsordersobjectiveobjectiveMin.Max.UsedOriginal2590263043(1178/564111513Twice52605260206(1336/
97、51152130274-times10,52010,5208283623/520843595410-times26,30026,3005610201500/549310614613420-times52,60052,6006250313519/5893248293268generallyimply moreraw rolls having to be consideredfor cutting,(i.e., higher J?). The numberofvariables and constraints in our formulation increases linearly with t
98、he latter.In order to study how the computational performance of the presented formulation varies withthe number of ordered product rolls, we carried out three additional experiments using the originaldata of Example 2 but multiplying the ordered quantities (cf. Table 8) by factors of 2, 4, 10 and 1
99、5,respectively.The results are summarized in Table 8. As expected the bigger the number of ordered productrolls, the larger the resulting mathematical problem and the di$culty of its solution. For instance,the optimal solution of the problem with twice the number of orders makes use of 25 di!erentcu
100、tting patterns which are automatically determined by the algorithm. However, even with the1054G. Schilling, M.C. Georgiadis / Computers & Operations Research 29 (2002) 10411058Table 10Production data for the industrial case studyProduct rolltype iWidth B?(cm)Min. quantityN?Max. quantityN?Pricep?Disc
101、ountc?11331010C 309C 029155C 211C 0385.533C 177C 0410111C 209C 058466C 240C 065044C 143C 073955C 93C 085433C 128C 0Table 9Raw roll characteristics for industrial case studyRoll typeWidth B?Max. spill B?!B?Max. cuts N?Cost c?1360 cm40 cm9C 515largest problem (involving the production of 1340 product
102、sheets from 268 raw rolls), it is stillpossible to determine the optimal solution in less than 1 min of computation on a desktopworkstation. The integrality gap also remains very small in all examples. The same problem wasalso solved for the case where there are two di!erent types of rolls available
103、 (as in Example 3)and the total number of orders exceeds 600 sheets. The solution corresponds to an objectivefunction of C 31550 with zero integrality gap. The total number of sheets produced is 660from 120 raw rolls. The problem involves 1823 integer variables and the solution was obtainedin 43 CPU
104、 s.4.6. Industrial case studyThis is an industrial case study based on a daily trim-loss optimization problem at MacedonianPaper Mills (MEL) S.A. in Northern Greece. MEL is one of the major paper-producing companiesin Greece with an annual production of more than 100,000 tons. A daily order typicall
105、y includes515 di!erent types of product rolls with a total weight of 10100 tons. So far, minimizationof trim-loss has been performed using heuristic-based techniques and human expertise withan average trim-loss of 47% depending on the order. The data for this problem are given inTables 9 and 10 and
106、correspond to approximated values.Assuming no cost for disposing of waste trim and for changing the cutting pattern the solutionis depicted Fig. 4. Note that 9 raw rolls are required to satisfy the production. A total number of1100 nodes were examined in the branch-and-bound tree requiring a computa
107、tional time of lessG. Schilling, M.C. Georgiadis / Computers & Operations Research 29 (2002) 104110581055Fig. 4. Solution of industrial case study without waste disposal and cutting change cost.Fig. 5. Solution of industrial case study with waste disposal and cutting change cost.than 5 CPU s. The op
108、timal value of the objective function which represent the prot is C3105.8and it is equal to the fully relaxed objective. The average trim-loss is 1.126% and representsapproximately a 55% improvement comparing with the current practice based on purely humanexpertise.The same problem was also solved b
109、y assuming that the cost coe$cients for disposing of wasteand for changing the cutting patterns are equal to 0.39 and 58.8, respectively (see Fig. 5). Theoptimal value of the prot is now C2842 while the value of the fully relaxed problem is C3044.Approximately 9000 nodes were considered requiring a
110、computational time of 1 CPU min. It is1056G. Schilling, M.C. Georgiadis / Computers & Operations Research 29 (2002) 10411058interesting to note that, since the cost for changing the cutting pattern is taken into account, onlythree such changes take place while the average trim-loss remains the same
111、with the previous case.However, it should be emphasized that the time savings in cutting, due to simultaneous minimiz-ation of changing the cutting pattern, has signicant impact on the protability of the plant. This isbecause the production rate increases almost proportionally with the reduction of
112、total cuttingtime.5. ConclusionsThis paper has presented a new mathematical formulation for the determination of optimalcutting patterns in one-dimensional problems. Its main advantage over earlier formulations lies inits small integralitygap and its fewer variablesand constraints. This is achievedw
113、ithoutthe needtoresort to a priori generated cutting patterns, and the combinatorial increase in problem size arisingfrom such an approach.The formulation results in MILP problems of modest size that are within the scope of currentlyavailable commercial solvers. The integrality gap of the formulatio
114、n is generally small, althoughthe di$culty of solution increases with problems involving changeover and waste disposal costs.Both the formulation presented here and most of the earlier ones reviewed in this paper areprimarily concerned with ensuring that the various orders are fullled. Only the work
115、 of Wester-lund 13 actually considers the times at which such orders are due. One interesting aspect of thepresented formulation is that it explicitly characterizes the sequence of rolls that have to be cut interms of both the type of each raw roll and the cutting pattern used for it. This opens the
116、 possibilityfor introducing additional variables and constraints characterizing the time at which each roll is tobe cut, thereby determining the optimal cutting schedule.AcknowledgementsThe authors are indebted to Dr. Iiro Harjunkoski for several useful discussions on the problemstudied in this pape
117、r.The authors are also grateful to Mr Sotiris Kiourtsides, Production Manager at MacedonianPaper Mills S.A., for providing the industrial case study and for the valuable discussions on severalpractical aspects of the trim-loss problem.References1 Gilmore PC, Gomory RE. A linear programming approach
118、to the cutting stock problem. Operations Research1961;9:84959.2 Gilmore PC, Gomory RE. A linear programming approach to the cutting stock problem * part II. OperationsResearch 1963;11:86388.3 Hinxman AI. The trim-loss and assortment problems. a survey. European Journal of Operational Research1980;5:
119、818.G. Schilling, M.C. Georgiadis / Computers & Operations Research 29 (2002) 1041105810574 Wascher G. An lp-based approach to cutting stock problems with multiple objectives. European Journal ofOperational Research 1990;44:17584.5 Sweeney PE, Haessler RW. One-dimensional cutting stock decisions for
120、 rolls with multiple quality grades.European Journal of Operational Research 1990;44:22431.6 Ferreira JS, Neves MA, Fonseca e Castro P. A two-phase roll cutting problem. European Journal of OperationalResearch 1990;44:18596.7 Gradisar M, Jesenko J, Resinovic G. Optimization of roll cutting in clothi
121、ng industry. Computers & OperationalResearch 1976;10:S94553.8 Gradisar M, Kljajic M, Resinovic G, Jesenko J. A sequential heuristic procedure for one-dimensional cutting.European Journal of Operational Research 1999;114:55768.9 Harjunkoski I, Westerlund T, Isaksson J, Skrifvars H. Di!erent formulati
122、ons for solving trim loss problems ina paper-converting mill with ilp. Computers and Chemical Engineering 1996;20:S1216.10 Harjunkoski I, Westerlund T, Porn R. Di!erent transformations for solving non-convex trim-loss problems byminlp. European Journal of Operational Research 1998;105:594603.11 West
123、erlund T, Isaksson J, Harjunkoski I. Solving a two-dimensional trim-loss problem with milp. EuropeanJournal of Operational Research 1998;104:57281.12 Westerlund T, Harjunkoski I, Isaksson J. Solving a production optimisation problem in a paper-converting millwith milp. Computers and Chemical Enginee
124、ring 1998;22:56370.13 Westerlund T, Isaksson J. Some e$cient formulations for the simultaneous solution of trim-loss and schedulingproblems in the paper-converting industry. Transactions of the Institution of Chemical Engineering PartA 1998;76:67784.14 Harjunkoski I, Westerlund T, Porn R, Skrifvars
125、H. Numerical and environmental considerations on a complexindustrial mixed integer non-linear programming (minlp) problem. Computers and Chemical Engineering1999;23:154561.15 Brooke A, Kendrick D, Meeraus A, Raman R. GAMS. A Users Guide. GAMS Development Corporation, 1998.Michael C. Georgiadis, Ph.D
126、., is a full time researcher at Chemical Process Engineering Research Institute inThessaloniki, Greece. He earned his Diploma of Chemical Engineering from Aristotle University of Thessaloniki andreceived his M.Sc. and Ph.D. in Process Systems Engineering from Imperial College, London. His research i
127、nterests lie inthe areas of mixed integer and computer-aided optimization techniques for #exible manufacturing in process industries,production scheduling, planning and dynamic modeling and simulation. He is the author of over 15 journal andconference publications.Gordian Schilling, Ph.D., is a proc
128、ess development chemical engineer at Ciba Specialty Chemicals Inc. in Switzerland.He earned his Diploma of Engineering from ETH, Zurich and received his Ph.D. in Process Systems Engineering fromImperial College, London.1058G. Schilling, M.C. Georgiadis / Computers & Operations Research 29 (2002) 10411058
