外文翻譯--計算機與運籌學研究一種最佳切割方式的確定算法 英文版

*Correspondingauthor.Tel.:#30-31-498-143；fax:#30-31-498-180.E-mail address: georgiadcperi.certh.gr(M.C.Georgiadis).Computers&OperationsResearch29(2002)10411058AnalgorithmforthedeterminationofoptimalcuttingpatternsGordianSchillingp0,MichaelC.Georgiadisp1p11*p0Ciba Specialty Chemicals Inc., CH-1870 Monthey, Switzerlandp1Centre for Research and Technology - Hellas, Chemical Process Engineering Research Institute, P.O. Box 361,Thermi 57001, Thessaloniki, GreeceReceived1June2000；receivedinrevisedform1September2000；accepted1October2000AbstractThispaperpresentsanewmathematicalprogrammingformulationfortheproblemofdeterminingtheoptimalmannerinwhichseveralproductrollsofgivensizesaretobecutoutofrawrollsofoneormorestandardtypes.Theobjectiveistoperformthistasksoastomaximizetheprottakingaccountoftherevenuefromthesales,thecostsoftheoriginalrolls,thecostsofchangingthecuttingpatternandthecostsofdisposalofthetrim.Amixedintegerlinearprogramming(MILP)modelisproposedwhichissolvedtoglobaloptimalityusingstandardtechniques.Anumberofexampleproblems,includinganindustrialcasestudy,arepresentedtoillustratethee$ciencyandapplicabilityoftheproposedmodel.Scope and purposeOne-dimensional cutting stock (trim loss) problems arise when production items must be physicallydividedintopieceswithadiversityofsizesinonedimension(e.g.whenslittingmasterrollsofpaperintonarrower width rolls). Such problems occur when there are no economies of scale associated with theproductionofthelargerraw(master)rolls.Ingeneral,theobjectivesinsolvingsuchproblemsareto5:p69 minimizetrimloss；p69 avoidproductionover-runsand/or；p69 avoidunnecessaryslittersetups.Theaboveproblemisparticularlyimportantinthepaperconvertingindustrywhenasetofpaperrollsneedtobecutfromrawpaperrolls.Sincethewidthofaproductisfullyindependentofthewidthoftherawpaperahighlycombinatorialproblemarises.Ingeneral,thecuttingprocessalwaysproducesinevitabletrim-losswhichhastobeburnedorprocessedinsomewastetreatmentplant.Trim-lossproblemsinthepaperindustryhave, in recent years, mainly been solved using heuristic rules. The practical problem formulationhas,therefore,inmostcasesbeenrestrictedbythefactthatthesolutionmethodsoughttobeabletohandletheentireproblem.Consequently,onlyasuboptimalsolutiontotheoriginalproblemhasbeenobtainedand0305-0548/02/$-seefrontmatter p7 2002ElsevierScienceLtd.Allrightsreserved.PII: S0305-0548(00)00102-7veryoftenthisrathersignicanteconomicproblemhasbeenlefttoamanualstage.Thisworkpresentsa novel algorithm for e$ciently determining optimal cutting patterns in the paper converting process.Amixed-integerlinearprogrammingmodelisproposedwhichissolvedtoglobaloptimalityusingavailablecomputertools.Anumberofexampleproblemsincludinganindustrialcasestudyarepresentedtoillustratetheapplicabilityoftheproposedalgorithm. p7 2002ElsevierScienceLtd.Allrightsreserved.Keywords: Integerprogramming；Optimization；Trim-lossproblems；Paperconvertingindustry1. IntroductionAnimportantproblemwhichisfrequentlyencounteredinindustriessuchaspaperisrelatedwiththemosteconomicmannerinwhichseveralproductrollofgivensizesaretobeproducedbycuttingoneormorewiderrawrollsavailableinoneormorestandardwidths.Thesolutionofthisprobleminvolvesseveralinteractingdecisions:p69 Thenumberofproductrollsofeachsizetobeproduced.Thismaybeallowedtovarybetweengivenlowerandupperbounds.Theformernormallyre#ectthe rmordersthatarecurrentlyoutstanding,whilethelattercorrespondtothemaximumcapacityofthemarket.However,certaindiscountsmayhavetobeo!eredtosellsheetsoverandabovethequantitiesforwhichrmordersareavailable.p69 Thenumberofrawrollsofeachstandardwidthtobecut.Rollsmaybeavailableinoneormorestandardwidths,eachofadi!erentunitprice.p69 Thecuttingpatternforeachrawroll.Cuttingtakesplaceonamachineemployinganumberofknivesoperatinginparallelonarollofstandardwidth.Whilethepositionoftheknivesmaybechangedfromonerolltothenext,suchchangesmayincurcertaincosts.Furthermore,theremaybecertaintechnologicallimitationsontheknifepositionsthatmayberealizedbyanygivencuttingmachine.Theoptimalsolutionoftheaboveproblemisoftenassociatedwiththeminimizationofthetrima waste that is generally unavoidable since rolls of standard widths are used. However,trim-lossminimizationdoesnotnecessarilyimplyminimizationofthecostoftherawmaterials(rolls)beingusedespeciallyifseveralstandardrollsizesareavailable.Amoredirecteconomiccriterionisthemaximizationoftheprotoftheoperationtakingaccountof:p69 therevenuefromproductrollssales,includingthee!ectsofanybulkdiscounts；p69 thecostoftherollsthatareactuallyused；p69 thecosts,ifany,ofchangingtheknifepositionsonthecuttingmachine；p69 thecostofdisposingoftrimwaste.Theaboveconstitutesahighlycombinatorialproblemanditisnotsurprisingthattraditionallyitssolutionhasoftenbeencarriedoutmanuallybasedonhumanexpertise.Thesimpliedversionofthisproblemissimilartothecuttingstockproblemknownintheoperation-researchliterature,whereanumberoforderedpiecesneedtobecuto!biggerstoredpiecesinthemosteconomicfashion.Inthe1960sandthe1970s,severalscienticarticleswerepublishedontheproblemof1042 G. Schilling, M.C. Georgiadis/Computers & Operations Research 29 (2002) 10411058minimizingtrimloss,e.g.1,2.Hinxman3presentsagoodoverviewoftheavailablesolutionmethodsfortrim-lossandassortmentproblems.GilmoreandGomory1presentedabasiclinearprogrammingapproachtothecuttingstockproblemwhilerelaxingsomeinteger-charactersof theproblem.GilmoreandGomory2de-scribed an iterative solution method that is suitable for very large number of orders and iscomputationalcheap,buttheresultingvaluesforthenumberofcuttingpatternstobeusedarenon-integeranditisnotpossibletoprovetheoptimalityorindicatethemarginofoptimalityofthese cutting patterns. Thus, the rounding values obtained by the algorithm of Gilmore andGomory2mayveryprobablyresultinpooreconomicperformance.Wascher4presentedalinearprogrammingapproachtocuttingstockproblemstakingintoaccountmultipleobjectivessuchascostoftherawmaterials,costoftheoverproductionstorage,trim-lossremovalcosts,etc.Sweeny5proposedaheuristicprocedureforsolvingone-dimensionalcuttingstockproblemswithmultiplequalitygrades.Ferreiraetal.6consideredthetwo-phaserollcuttingproblemsbased on a heuristic approach. Gradisar et al. 7 presented an e$cient sequential heuristicprocedureand a softwaretool for optimizationof roll cutting in theclothing industry.Later,Gradisaretal.8developedanimprovedsolutionstrategybasedonacombinationofapproxima-tionsandheuristicsleadingtoalmostoptimalsolutionsfortheone-dimensionalstockcuttingproblems.Asoftwaretoolwasalsodeveloped.Inrecentyears,integerprogrammingtechniqueshavebeenusedforthesolutionofthetrim-lossand production optimization problem in the paper industry. The work of Westerlund andcoworkersatAp15 boAkademiUniversityinFinlandisakeycontributioninthisarea.Harjunkoski9consideredamathematicalprogrammingapproachtothetrim-lossproblemandpresentedtwodi!erenttypesofformulation.Intherstone,boththecuttingpatternsthatneedtobeusedandthenumberofrollsthathavetobecutaccordingtoeachsuchpatternaretreatedasunknowns.Thisresultsinanintegernonlinearmathematicalproblem(INLP)involvingbilinearproblemsofthevariablescharacterizingeachcuttingpatternandthecorrespondingnumberofrollscutinthisway.Twodi!erentwaysoflinearizingtheINLPtoobtainamixedintegerlinearprogramming(MILP)modewerepresented.However,theselinearizationsoftenresultinasignicantincreaseinthenumberofvariablesandconstraints,aswellasalargeintegralitygap.ThesecondtypeofformulationpresentedbyHarjunkoski9isbasedonusingaxedsetofcuttingpatternsthatisdecidedapriori.ThisresultsinaMILPthathasamuchsmallerintegralitygapthantheoneresultingfromthelinearizationoftheINLPformulationmentionedabove.However,thesolutionobtainedisguaranteedtobeoptimalonlyifallnon-inferiorcuttingpatternsareidentiedandtaken into consideration. The number of such patterns may be quite substantial for realisticindustrialproblems.Extendingtheabovework,Harjunkoski10presentedlinearandconvexformulationsforsolvingthenon-convextrim-lossproblems.Westerlund11consideredthetwo-dimensionaltrim-lossprobleminpaperconverting.Anon-convexoptimizationmodelwasproposedwhereboththewidthsandthelengthsoftherawpaperwereconsideredasvariables.Atwo-stepsolutionprocedurewasusedwhereallfeasiblecuttingpatternswere rst generated and then a MILP problem was solved.In a similar fashion,theproductionoptimizationprobleminthepaperconvertingindustrywasaddressedbyWesterlund12.Schedulingaspectsofthecuttingmachinesinpaperconvertingweresimultaneouslycon-sideredwiththetrim-lossproblembyWesterlund13.Recently,Harjunkoski14incorporatedenvironmentalimpactconsiderationsintoageneralframeworkfortrim-lossminimization.G. Schilling, M.C. Georgiadis/Computers & Operations Research 29 (2002) 10411058 1043ThispaperpresentsanalternativemathematicalprogrammingformulationthatresultsdirectlyinaMILPofsmallintegralitygap.Thesalientfeatureofthismodelisthatitdoesnotrequireapriorienumerationofallpossiblecuttingpatterns.Thenextsectionpresentsaformalstatementoftheproblemunderconsiderationandthenotationused.Section3considersthemathematicalformulationoftheobjectivefunctionandtheoperationalconstraints.Thisisfollowedbysomeexampleproblemsincludinganindustrialcasestudyillustratingtheapplicabilityandcomputa-tionalbehavioroftheproposedformulation.2. Problem statement and dataThetaskbeingconsideredhereistoproduceproductrollsofIdi!erenttypes,thewidthoftypeibeingdenotedbyBp71,i1,2,Ifromoneormorestandardrolls.Thelengthsofallrawrollsandoftheproductrollsresultingfromthemareassumedtobeidenticalandxed.Itisbeyondthescopeofthisworktoconsiderthetwo-dimensionalproblemwhereboththewidthsandthelengthsofrawpaperrollsandthecuttingpatternsareconsideredvariables.Productrollsaremostlyproducedtoorder.Theminimumorderedquantityforproductrollsofwidth i is denoted by Np13p9p14p71and is given, and so is the correspondingunit price pp71. However,customersmaybewillingtobuyadditionalrollsoftypeiuptoamaximumquantityNp13p0p24p71subjecttoadiscountofcp3p9p19p2p71foreachproductrolloverandabovetheminimumnumberNp13p9p14p71.Ingeneral,thenumberofadditionalrollssoldinthismannertendstoberathersmallsincethemainincentiveofsuchdiscountingfromthe pointofviewofthe manufacturerismerelyto decreasethe lossthroughtrim.Theproductrollsaretobecutfromrawrollsofdi!erentstandardtypes.Theunitpriceforarawrolloftypetisdenotedbycp18p15p12p12p82anditsnominalwidthbyBp18p15p12p12p82.However,theusefulwidthofa roll of type t is determined by the cutting machine used. In particular, each raw roll typet1,2,ischaracterizedbyamaximumpossibletotalengagementBp13p0p24p82denotingthemaximumtotalwidthofallproductrollsthatcanbecutfromarawrollofthistype.Theremayalsobeaminimumrequiredtotalengagement Bp13p9p14p82forthistypeofroll.IngeneralBp13p9p14p82)Bp13p0p24p82)Bp82, t1,2,.Themaximumnumber Np13p0p24p82ofproductrollsthatcanbecutoutofarawrolloftype t willgenerally be determined by the knives and other characteristics of the available machine.Moreover,insomecases,theremaybelimitationsintheavailablenumberJHp82ofrawrollsofagiventype t.Thecuttingpatternforeachraw rollis determinedby the positionof theknives.Frequentchangesinthesepositionsaregenerallyundesirable.Eachsuchchangemaythereforebeassociatedwithanon-zerocost cp2p8p0p14p6p4.Theproductionoftherequiredproductrollsfromtheavailablerawrollsmayresultintrimwastewhichmayneedtobedisposedof.Thecostofsuchdisposalperunitwidthoftrimisdenotedby cp3p9p19p16.Basedonthegivendata,werstderiveanupperboundJonthenumberofrawrollsthatmayneedtobecut.ThisisobtainedbyassumingthatthemaximumnumberNp13p0p24p71ofproductrollsofeach type i will be produced； that raw rolls of the type t that permits the smallest minimum1044 G. Schilling, M.C. Georgiadis/Computers & Operations Research 29 (2002) 10411058engagement Bp13p9p14p82willbeused；andthateachrawrollwillbeusedtoproduceproductrollsofasingletypeonly.Overall,thisleadstothefollowingupperboundonthenumberofrawrollsthatmayberequired:Jp13p0p24p39p9p71p14p16Np13p0p24p71p87minp82Bp13p9p14p82/Bp71p88. (1)We can also calculate a lower bound Jp13p9p14 on the minimum number of raw rolls that arenecessarytosatisfytheminimumdemandfortheexistingorders.Wedothisbyassumingthatrollsof the type t allowing the maximum possible engagement Bp13p0p24p82are used, and that no trim isproduced.However,wemustalsotakeaccountofpossiblelimitationsonthenumberofavailableknives. Overall, this leads to the following lower bound on the number of rolls that mayberequired:Jp13p9p14maxp7p9p39p71p14p16Np13p9p14p71Bp71maxp82Bp13p0p24p82,p9p39p71p14p16Np13p9p14p71maxp82Np13p0p24p82p8. (2)3. Mathematical formulationTheaimofthemathematicalformulationistodeterminethetypetofeachrawrolljtobecutandthenumberofproductrollsofeachtype i tobeproducedfromit.3.1. Key variablesThefollowingintegervariablesareintroduced:np71p72:numberofproductrollsoftype i tobecutoutofrawroll jafii9773p71: numberofproductrollsoftype i producedoverandabovetheminimumnumberordered.Wenotethat np71p72cannotexceed:p69 themaximumnumber Np13p0p24p71ofproductrollsoftype i thatcanbesold；p69 themaximumnumberofproductrollsofwidth Bp71thatcanbeaccommodatedwithinamax-imumengagementBp13p0p24p82forarawrolloftype t；p69 themaximumnumber Np13p0p24p82ofknivesthatcanbeappliedtoarawrolloftype t.Thisleadstothefollowingboundsfor np71p72:0)np71p72)minp1Np13p0p24p71,maxp16p87p82p87p50Bp13p0p24p82Bp71,maxp16p87p82p87p50Np13p0p24p82p2i1,2,I, j1,2,Jp13p0p24. (3)Also0)afii9773p71)Np13p0p24p71!Np13p9p14p71, i1,2,I. (4)G. Schilling, M.C. Georgiadis/Computers & Operations Research 29 (2002) 10411058 1045Wenotethat afii9773p71needtobeincludedinthemodelonlyif Np13p0p24p71Np13p9p14p71.Wealsointroducethefollowingbinaryvariables:yp82p72p71 ifthe jthrolltobecutisoftype t,0 otherwise.zp72p71 ifthecuttingpatternforpaperroll j isdifferenttothatforroll j!1,0 otherwise.Wenotethat,ingeneral,theindexjwillbeintherange1,2,Jp13p0p24.However,theformulationtobepresentedwillassignatypet onlytotherawrollsjthatareactuallyused.Hence,thetotalnumberofrollstobecutwillalsobedeterminedbythesolutionoftheoptimizationproblem.Thiswillbecomeclearerinthenextsubsection.3.2. Roll type determination constraintsEachrawroll j tobecutmustbeofauniquetype t.Thisresultsinthefollowingconstraints:p50p9p82p14p16yp82p721, j1,2,Jp13p9p14, (5a)p50p9p82p14p16yp82p72)1, jJp13p9p14#1,2,Jp13p0p24. (5b)Notethatfor jJp13p9p14,itispossiblethat yp82p720for all types t；thissimplyimpliesthatitisnotnecessarytocutroll j.Furthermore,thelimitedavailabilityofrawrollsofagiventypetmaybeexpressedintermsoftheconstraintp40p13p0p24p9p72p14p16yp82p72)JHp82, t1,2,. (6)3.3. Cutting constraintsWeneedtoensurethat,ifarolljistobecut,thenthelimitationsontheminimumandmaximumengagementareobserved.Thisisachievedviatheconstraintsp50p9p82p14p16Bp13p9p14p82yp82p72)p39p9p71p14p16Bp71np71p72)p50p9p82p14p16Bp13p0p24p82yp82p72, j1,2,Jp13p0p24. (7)Wenotethatthequantityp9p39p71p14p16Bp71np71p72representsthetotalwidthofallproductrollstobecutoutofrawroll j.Ifyp82p721forsomerolltype t,thenconstraint(7)ensuresthatBp13p9p14p82)p39p9p71p14p16Bp71np71p72)Bp13p0p24p82.1046 G. Schilling, M.C. Georgiadis/Computers & Operations Research 29 (2002) 10411058Ontheotherhand,ifyp82p720forall t,thenconstraint(7)e!ectivelyforcesnp71p720foralli1,2,I.Thisexpressestheobviousfactthatifrolljisnotactuallycut,thennoproductrollsofanytypecanbeproducedfromit.Wealsoneedtoensurethatthenumberofproductrollscutoutofanyrolljoftypetdoesnotexceedthenumberofknivesthatcanbedeployedonrollsofthistype.Thisiswrittenas0)p39p9p71p14p16np71p72)p50p9p82p14p16Np13p0p24p82yp82p72, j1,2,Jp13p0p24. (8)3.4. Production constraintsThetotalnumberofproductrollsofeachtype i thatareproducedcomprisestheminimumorderedquantity Np13p9p14p71forthistypeplusthesurplusproductionafii9773p71:p40p13p0p24p9p72p14p16np71p72Np13p9p14p71#afii9773p71, i1,2,I. (9)Theseconstraints,togetherwiththeboundsonafii9773p71,ensurethatthequantityofproductrollsoftypei producedliesbetweentheminimumandmaximumbounds Np13p9p14p71and Np13p0p24p71,respectively.3.5. Changeover constraintsIfchangingthecuttingpatternincursanon-zerocost cp2p8p0p14p6p40,weneedtodeterminewhensuchchangeswilltakeplace.Tothisend,weincludethefollowingconstraint:!Mp71zp72)np71p72!np71p11p72p92p16)Mp71zp72, i1,2,I, j2,2,Jp13p0p24. (10)Notethatthiswillallowzp72tobezeroonlyifnp71p72np71p11p72p92p16forallproductrollsi,i.e.ifrollsjandj!1arecutinexactlythesameway.Here,theconstantMp71isanupperboundonnp71p72(seeSection3.1).3.6. Objective functionTheobjectiveoftheoptimizationistomaximizethetotalprotoftheoperationtakingaccountof:p69 Theincomefromthesalesofproductrollsofeachtype i.Thiscomprisestheincomefromsellingtheminimumorderedquantities Np13p9p14p71atthefullunitprice pp71,plus theincomeof sellingtheadditionalquantities afii9773p71atthe discountedunitpricepp71!cp3p9p19p2p71:p39p9p71p14p16(pp71Np13p9p14p71#afii9773p71(pp71!cp3p9p19p2p71).p69 Thecostsoftherollstobecut.Generally,thecostofeachrolldependsonitstype.Thetotalcostcanbewrittenasp40p13p0p24p9p72p14p16p9p82p14p16cp18p15p12p12p82yp82p72.G. Schilling, M.C. Georgiadis/Computers & Operations Research 29 (2002) 10411058 1047Wenotethat,foreachrollj,atmostonetermoftheinnersummationisnon-zero(cf.constraints(5a)and(5b).p69 Thecostsofchangingthepositionsoftheknives.Ingeneral,theknifepositionshavetobechangedifthecuttingpatternusedforagivenrolljisdi!erenttothatforthepreviousone.Thisisdeterminedbythevariableszp72andresultsinthecosttermcp2p8p0p14p6p4p40p13p0p24p9p72p14p17zp72,wherethesummationisequaltothetotalnumberofchangesthatarenecessary.p69 Thecostofdisposingofanytrimproduced.Thewidthoftrimproducedoutofrawrolljisgivenbythedi!erencebetweentherollwidthandthetotalwidthofallproductrollscutfromit.Theformerquantitydependsonthetypeoftherollandcanbeexpressedasp9p50p82p14p16Bp18p15p12p12p82yp82p72；onceagain,atmostoneofthetermsinthissummationcanbenon-zero(cf.constraints(5a)and(5b).Thelatterquantityisgivenbyp9p39p71p14p16Bp71np71p72.Overall,trimdisposalresultsinthefollowingcosttermcp3p9p19p16p40p13p0p24p9p72p14p16p1p50p9p82p14p16Bp18p15p12p12p82yp82p72!p39p9p71p14p16Bp71np71p72p2.Theabovetermscannowbecollectedinthefollowingobjectivefunction:maxp3p39p9p71p14p16(pp71Np13p9p14p71#afii9773p71(pp71!cp3p9p19p2p71)!p40p13p0p24p9p72p14p16p9p82p14p16cp18p15p12p12p82yp82p72!cp2p8p0p14p6p4p40p13p0p24p9p72p14p17zp72!cp3p9p19p16p40p13p0p24p9p72p14p16p1p50p9p82p14p16Bp18p15p12p12p82yp82p72!p39p9p71p14p16Bp71np71p72p2p4. (11)Notethatthersttermintheaboveobjectivefunction(i.e.p9p39p71p14p16pp71Np13p9p14p71)isactuallyaconstantanddoesnota!ecttheoptimalsolutionobtained.3.7. Degeneracy reduction and constraint tighteningIngeneral,thebasicformulationpresentedaboveishighlydegenerate:givenanyfeasiblepoint,onecangeneratemanyotherssimplybyformingallpossibleorderingoftherollsselectedtobecut.Moreover,providedallrawrollsofthesametypearecutconsecutively,allthesefeasiblepointswillcorrespondtoexactlythesamevalueoftheobjectivefunction.Theabovepropertymayhaveadversee!ectsonthee$ciencyofthesearchprocedure.Therefore,in order to reduce the solution degeneracy without any loss of optimality, we introduce thefollowingorderingconstraints:p39p9p71p14p16np71p11p72p92p16*p39p9p71p14p16np71p72, j2,2,Jp13p0p24. (12)Thisensuresthatthetotalnumberofproductrollscutoutofrawrollj!1isneverlowerthanthecorrespondingnumberforroll j；allcompletelyunusedrawrollsareleftlastinthisordering.1048 G. Schilling, M.C. Georgiadis/Computers & Operations Research 29 (2002) 10411058Analternativewouldbetoordertherawrollsinnon-increasingutilizationorder,i.e.p39p9p71p14p16Bp71np71p11p72p92p16*p39p9p71p14p16Bp71np71p72, j2,2,Jp13p0p24.However,ourpracticalexperienceindicatesthatthisisnotase!ectiveasconstraint(12).Wealsonotethattheconstraints(7)implicitlyimposealowerboundonthetotalnumberofproductrollsp9p39p71p14p16np71p72cutoutofarawroll j.Astrongerboundmaysometimesbeobtainedbyconsideringarolloftypetbeingusedattheminimumpossibleengagementtoproducethewidestpossibleproductrolls.Thisleadstotheconstraintsp50p9p82p14p16Bp13p9p14p82maxp71Bp71yp82p72)p39p9p71p14p16np71p72, j1,2,Jp13p0p24. (13)3.8. CommentsTheobjectivefunctionandallconstraintsintroducedinthissectionarelinear.Sinceallvariablesareintegervalued,theformulationpresentedcorrespondstoanintegerlinearprogramming(ILP)problem.However,constraints(9)ensurethatthevariablesafii9773p71willautomaticallyassumeintegervaluesprovidedvariablesnp71p72doso.Therefore,afii9773p71maybetreatedascontinuousquantities,whichleavesuswithamixedintegerlinearprogramming(MILP)problem.Inprinciple,thelattercanbesolvedusingstandardMILPsolvers.Inthespecial(butquitecommon)casewhereonlyonetypeofrollisavailable,constraints(5a)simplyimplythat yp82p72canbe xed to1 forall j1,2,Jp13p9p14. Both(5a)and (5b)are otherwiseredundant and may be dropped. Furthermore, the lower bound on constraint (7) is directlyincludedintheboundsofthecorrespondingslackvariable,0； Bp13p0p24p82!Bp13p9p14p82,whichresultsinonelessconstraintforeachroll j.4. Example problemsIn this section, we consider four example problems of increasing complexity in order toinvestigatethecomputationalbehaviorofourformulation.Furthermoreanindustrialcasestudyisalsopresented.Inallcases,weassumethatthemaximumrawrollengagementBp13p0p24p82isequaltothecorrespondingrollwidthBp18p15p12p12p82.TheGAMS/CPLEXvs6.0solverhasbeenusedforthesolution15andallcomputationswerecarriedoutonaAlphaServer4100.Anintegralitygapof0.1%wasassumedforthesolutionofallproblems.4.1. Example 1OurrstexampleisbasedonthatgivenbyHarjunkoski9.Sometranslationofthevariouscostcoe$cientswasnecessarytoaccountforslightdi!erencesintheobjectivefunctionsusedbythetwoformulations.Alsonotethattheobjectiveusedbythoseauthorsistheminimizationofcostasopposedtothemaximizationofprot；therefore,thesignoftheirobjectivefunctionisoppositetothatofours.G. Schilling, M.C. Georgiadis/Computers & Operations Research 29 (2002) 10411058 1049Table1RawrollcharacteristicsforExample1Rolltype Width Bp18p15p12p12p82Max.spill Bp13p0p24p82!Bp13p9p14p82Max.cuts Np13p0p24p82Cost cp18p15p12p12p821 1900mm 200mm 5 1900Table2ProductiondataforExample1Productrolltype iWidth Bp71(mm)Min.quantityNp13p9p14p71Max.quantityNp13p0p24p71Pricepp71Discountcp3p9p19p2p711 30810297.0 02 360 7 8 324.0 03 385 12 13 346.5 04 415 11 11 373.5 0p16Eachverticalbarcorrespondstoadi!erentrollbeingcut.Thecorrespondingrolltypeisshownimmediatelyaboveeachbar.Eachbarisdividedintoanumberofsegmentscorrespondingtosheetsoftheindicatedtype.Thedarkshadedsegmentatthetopofthebaristhetrim-loss,thepercentagewidthofwhichisindicatednumericallyatthebottomofthegure.Theproblemaimstodeterminetheoptimalcuttingpatternforproducingfourdi!erenttypesofproductrollsfromasingletypeofrawroll.ThecharacteristicsofthelatterareshowninTable1.TheproductionrequirementsaresummarizedinTable2.Thecostforchangingthecuttingpatternis 1,whiledisposingofthetrimincursnocost.Harjunkoski 9 assumed a maximum of four di!erent cutting patterns, which results inareductionofthesizeofthemodel.Inourcase,thenumberofsuchpatternsisdeterminedbythesolution.Alsofromexpressions(1)and(2),wedetermineJp13p0p2410andJp13p9p148.Wethereforexyp16p721,for j1,2,8.ThesolutionweobtainisthesameasthatreportedbyHarjunkoski9involvingtheproductionoftheminimumorderedamountsofproductrollsplusoneextrarolloftype2andanotheroftype3.ThesolutionispresentedpictoriallyinFig.1p16 andcorrespondstoanobjectivefunctionvalueof!1622.0；thus,withthegiveneconomicdatatheoperationincursaloss.Theoptimalsolution(withinamarginofoptimalityof0.1%)isfoundwithinlessthan1CPUsatnode49ofthebranch-and-boundalgorithmusingabreadthrstsearchstrategy.ItmustbenotedthattheintegralitygapofourformulationiscomparabletothatforoneoftheformulationspresentedbyHarjunkoski9despitethefactthatitdoesnotemployanyapriorienumerationofthecuttingpatterns.Ourformulationalsoexaminesasmallnumberofnodesinordertodetecttheoptimalpoint(Table3).1050 G. Schilling, M.C. Georgiadis/Computers & Operations Research 29 (2002) 10411058Fig.1. SolutionofExample1.Table3ComputationalstatisticsforExample1OptimalobjectiveFullyrelaxedobjectiveIntegralitygap(%)NodesinB&BVariables(Bin/Int/Cont)Constraints(!)1622.0 (!)1619.4 0.18 49 60(13/44/3) 1154.2. Example 2ThedataforthisproblemaregiveninTables4and5.Thereisnocostforchangingthecuttingpatternorfordisposingoftrim.Usingexpressions(1)and(2),itispossibletocalculateapriorithatthenumberofrawrollsrequiredwillbebetween11and15.Althoughthisprobleminvolvesonly9typesofproductrolls,thereareatotalof3971di!erentcuttingpatterns,allofwhicharefeasiblewithrespecttotheminimumandmaximumallowedtotalengagementoftherolls,themaximumnumberofknivesthatcanbeappliedtoarollandthemaximum 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,awell-knownproblemwiththeclassicalapproachtothecuttingstockproblem.Our algorithm obtains the exact (0% optimality margin) optimal solution for this problemwithin less than 1CPUs. This solution is presented in Fig. 2. Computational performancestatisticsaregiveninTable6.G. Schilling, M.C. Georgiadis/Computers & Operations Research 29 (2002) 10411058 1051Table4RawrollcharacteristicsforExample2Rolltype Width Bp13p0p24p82Max.spill Bp13p0p24p82!Bp13p9p14p82Max.cuts Np13p0p24p82Cost cp18p15p12p12p821 1900mm 200mm 5 1600Table5ProductiondataforExamples2and3Productrolltype iWidth Bp71(mm)Min.quantityNp13p9p14p71Max.quantityNp13p0p24p71Pricepp71Discountcp3p9p19p2p711 340 8 10 C340 C02 365 7 8 C365 C03 385 12 13 C385 C04 415 1 11 C415 C05 435 5 5 C435 C06 260 6 8 C260 C07 300 4 4 C300 C08 320 7 8 C320 C09 335 3 3 C335 C0Fig.2. SolutionofExample2.1052 G. Schilling, M.C. Georgiadis/Computers & Operations Research 29 (2002) 10411058Table6ComputationalstatisticsforExamples2,3and4Formulation Optimal Fullyrelaxed Integrality Nodes Variables Constraintsobjective objective gap(%) inB&B (Int/Bin/Cont)Example2 2590.0 2630.0 1.54 43 173(6/162/5) 61Example3 3030.0 3030.0 0 131 203(36/162/5) 116Example4 1240.0 1279.3 3.16 14,800 173(6/162/5) 61Table7RawrollcharacteristicsforExample3Rolltype Width Bp13p0p24p82Max.spill Bp13p0p24p82!Bp13p9p14p82Max.cuts Np13p0p24p82Cost cp18p15p12p12p821 1900mm 200mm 5 C16002 2200mm 250mm 6 C18504.3. Example 3ThisexampleissimilartoExample2,theonlydi!erencebeingthatupto6rawrollsofadi!erenttypearenowalsoavailabletobecut(seeTable7).Sinceawiderrollisnowavailable,theminimumnumber Jp13p9p14 ofrequiredrollsisreducedto9(from11inExample2),butthemaximumnumberJp13p0p24 ofrollsremainsthesame,namely15.Theexact(0%optimalitymargin)optimalsolutionwasobtainedinlessthan1CPUs.ThesolutionispresentedinFig.3withthecomputationalperformancestatisticsshowninTable6.Themaximumpossiblenumberofrawrollsoftype2isused.Itisinterestingtomentionthat,ifnoupperlimitonthenumberofrawrollsoftype2isimposed,onlyrollsofthistypeareactuallyengaged.ThisthenresultsinahigherprotofC3380.4.4. Example 4ThisexampleissimilartoExample2,theonlydi!erencebeingthatthecostcoe$cientsforchangingthecuttingpattern, cp2p8p0p14p6p4 andfordisposingofwastetrim, cp3p9p19p16 areequalto10and1,respectively.ThecomputationalperformanceisshowninTable6.Weobservethataconsiderablelargernumberof nodesin the branch-and-boundtreeis required comparingwithExample2.However,theintegralitygapisrelativelysmall.4.5. Example 5Onejustiedconcernwithourformulationisthewayinwhichthecomputationalcostmayincreasewiththe numberof ordersthathave tobesatised.ThisisbecausemoreorderswillG. Schilling, M.C. Georgiadis/Computers & Operations Research 29 (2002) 10411058 1053Fig.3. SolutionofExample3.Table8ComputationalstatisticsforExample5Example2 Optimal FullyrelaxedNodesinB&BCPU(s)Variablesint/contConstraints Numberofrollsorders objectiveobjective Min. Max. UsedOriginal 2590 2630 43 (1 178/5 64 11 15 13Twice 5260 5260 206 (1 336/5 115 21 30 274-times 10,520 10,520 828 3 623/5 208 43 59 5410-times 26,300 26,300 5610 20 1500/5 493 106 146 13420-times 52,600 52,600 6250 31 3519/5 893 248 293 268generallyimplymorerawrollshavingtobeconsideredforcutting,(i.e.,higherJp13p0p24).Thenumberofvariablesandconstraintsinourformulationincreaseslinearlywiththelatter.Inordertostudyhowthecomputationalperformanceofthepresentedformulationvarieswiththenumberoforderedproductrolls,wecarriedoutthreeadditionalexperimentsusingtheoriginaldataofExample2butmultiplyingtheorderedquantities(cf.Table8)byfactorsof2,4,10and15,respectively.TheresultsaresummarizedinTable8.Asexpectedthebiggerthenumberoforderedproductrolls,thelargertheresultingmathematicalproblemandthedi$cultyofitssolution.Forinstance,theoptimalsolutionoftheproblemwithtwicethenumberofordersmakesuseof25di!erentcuttingpatternswhichareautomaticallydeterminedbythealgorithm.However,evenwiththe1054 G. Schilling, M.C. Georgiadis/Computers & Operations Research 29 (2002) 10411058Table10ProductiondatafortheindustrialcasestudyProductrolltype iWidth Bp71(cm) Min.quantityNp13p9p14p71Max.quantityNp13p0p24p71Pricepp71Discountcp3p9p19p2p711 133 10 10 C309 C029155C211 C03 85.5 3 3 C177 C04 101 1 1 C209 C058466C240 C065044C143 C073955C93 C085433C128 C0Table9RawrollcharacteristicsforindustrialcasestudyRolltype Width Bp13p0p24p82Max.spill Bp13p0p24p82!Bp13p9p14p82Max.cuts Np13p0p24p82Cost cp18p15p12p12p821 360cm 40cm 9 C515largestproblem(involvingtheproductionof1340productsheetsfrom268rawrolls),itisstillpossible to determine the optimal solution in less than 1 min of computation on a desktopworkstation.Theintegralitygapalsoremainsverysmallinallexamples.Thesameproblemwasalsosolvedforthecasewheretherearetwodi!erenttypesofrollsavailable(asinExample3)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 660from120rawrolls.Theprobleminvolves1823integervariablesandthesolutionwasobtainedin43CPUs.4.6. Industrial case studyThisisanindustrialcasestudybasedonadailytrim-lossoptimizationproblematMacedonianPaperMills(MEL)S.A.inNorthernGreece.MELisoneofthemajorpaper-producingcompaniesinGreecewithanannualproductionofmorethan100,000tons.Adailyordertypicallyincludes515 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 withanaveragetrim-lossof47%dependingontheorder.ThedataforthisproblemaregiveninTables9and10andcorrespondtoapproximatedvalues.AssumingnocostfordisposingofwastetrimandforchangingthecuttingpatternthesolutionisdepictedFig.4.Notethat9rawrollsarerequiredtosatisfytheproduction.Atotalnumberof1100nodeswereexaminedinthebranch-and-boundtreerequiringacomputationaltimeoflessG. Schilling, M.C. Georgiadis/Computers & Operations Research 29 (2002) 10411058 1055Fig.4. Solutionofindustrialcasestudywithoutwastedisposalandcuttingchangecost.Fig.5. Solutionofindustrialcasestudywithwastedisposalandcuttingchangecost.than5CPUs.TheoptimalvalueoftheobjectivefunctionwhichrepresenttheprotisC3105.8and it is equal to the fully relaxed objective. The average trim-loss is 1.126% and representsapproximatelya55%improvementcomparingwiththecurrentpracticebasedonpurelyhumanexpertise.Thesameproblemwasalsosolvedbyassumingthatthecostcoe$cientsfordisposingofwasteandforchangingthecuttingpatternsareequalto0.39and58.8,respectively(seeFig.5).TheoptimalvalueoftheprotisnowC2842whilethevalueofthefullyrelaxedproblemis C3044.Approximately9000nodeswereconsideredrequiringacomputationaltimeof1CPUmin.Itis1056 G. Schilling, M.C. Georgiadis/Computers & Operations Research 29 (2002) 10411058interestingtonotethat,sincethecostforchangingthecuttingpatternistakenintoaccount,onlythreesuchchangestakeplacewhiletheaveragetrim-lossremainsthesamewiththepreviouscase.However,itshouldbeemphasizedthatthetimesavingsincutting,duetosimultaneousminimiz-ationofchangingthecuttingpattern,hassignicantimpactontheprotabilityoftheplant.Thisisbecausetheproductionrateincreasesalmostproportionallywiththereductionoftotalcuttingtime.5. ConclusionsThispaperhaspresentedanewmathematicalformulationfor thedeterminationofoptimalcuttingpatternsinone-dimensionalproblems.Itsmainadvantageoverearlierformulationsliesinitssmallintegralitygapanditsfewervariablesandconstraints.Thisisachievedwithouttheneedtoresorttoapriorigeneratedcuttingpatterns,andthecombinatorialincreaseinproblemsizearisingfromsuchanapproach.TheformulationresultsinMILPproblemsofmodestsizethatarewithinthescopeofcurrentlyavailablecommercialsolvers.Theintegralitygapoftheformulationisgenerallysmall,althoughthedi$cultyofsolutionincreaseswithproblemsinvolvingchangeoverandwastedisposalcosts.Boththeformulationpresentedhereandmostoftheearlieronesreviewedinthispaperareprimarilyconcernedwithensuringthatthevariousordersarefullled.OnlytheworkofWester-lund13actuallyconsidersthetimesatwhichsuchordersaredue.Oneinterestingaspectofthepresentedformulationisthatitexplicitlycharacterizesthesequenceofrollsthathavetobecutin