CG2-150型仿型切割機設計【說明書+CAD】

CG2-150型仿型切割機設計【說明書+CAD】,說明書+CAD,CG2-150型仿型切割機設計【說明書+CAD】,cg2,型仿型,切割機,設計,說明書,仿單,cad *Correspondingauthor.Tel.:#30-31-498-143;fax:#30-31-498-180. E-mail address: georgiadcperi.certh.gr(M.C.Georgiadis). Computersreceivedinrevisedform1September2000;accepted1October2000 Abstract Thispaperpresentsanewmathematicalprogrammingformulationfortheproblemofdeterminingthe optimalmannerinwhichseveralproductrollsofgivensizesaretobecutoutofrawrollsofoneormore standardtypes.Theobjectiveistoperformthistasksoastomaximizetheprottakingaccountofthe revenuefromthesales,thecostsoftheoriginalrolls,thecostsofchangingthecuttingpatternandthecostsof disposalofthetrim.Amixedintegerlinearprogramming(MILP)modelisproposedwhichissolvedto globaloptimalityusingstandardtechniques.Anumberofexampleproblems,includinganindustrialcase study,arepresentedtoillustratethee$ciencyandapplicabilityoftheproposedmodel. Scope and purpose One-dimensional cutting stock (trim loss) problems arise when production items must be physically dividedintopieceswithadiversityofsizesinonedimension(e.g.whenslittingmasterrollsofpaperinto narrower width rolls). Such problems occur when there are no economies of scale associated with the productionofthelargerraw(master)rolls.Ingeneral,theobjectivesinsolvingsuchproblemsareto5: p69 minimizetrimloss; p69 avoidproductionover-runsand/or; p69 avoidunnecessaryslittersetups. Theaboveproblemisparticularlyimportantinthepaperconvertingindustrywhenasetofpaperrollsneed tobecutfromrawpaperrolls.Sincethewidthofaproductisfullyindependentofthewidthoftherawpaper ahighlycombinatorialproblemarises.Ingeneral,thecuttingprocessalwaysproducesinevitabletrim-loss whichhastobeburnedorprocessedinsomewastetreatmentplant.Trim-lossproblemsinthepaperindustry have, in recent years, mainly been solved using heuristic rules. The practical problem formulationhas, therefore,inmostcasesbeenrestrictedbythefactthatthesolutionmethodsoughttobeabletohandlethe entireproblem.Consequently,onlyasuboptimalsolutiontotheoriginalproblemhasbeenobtainedand 0305-0548/02/$-seefrontmatter p7 2002ElsevierScienceLtd.Allrightsreserved. PII: S0305-0548(00)00102-7 veryoftenthisrathersignicanteconomicproblemhasbeenlefttoamanualstage.Thisworkpresents a novel algorithm for e$ciently determining optimal cutting patterns in the paper converting process. Amixed-integerlinearprogrammingmodelisproposedwhichissolvedtoglobaloptimalityusingavailable computertools.Anumberofexampleproblemsincludinganindustrialcasestudyarepresentedtoillustrate theapplicabilityoftheproposedalgorithm. p7 2002ElsevierScienceLtd.Allrightsreserved. Keywords: Integerprogramming;Optimization;Trim-lossproblems;Paperconvertingindustry 1. Introduction Animportantproblemwhichisfrequentlyencounteredinindustriessuchaspaperisrelatedwith themosteconomicmannerinwhichseveralproductrollofgivensizesaretobeproducedby cuttingoneormorewiderrawrollsavailableinoneormorestandardwidths.Thesolutionofthis probleminvolvesseveralinteractingdecisions: p69 Thenumberofproductrollsofeachsizetobeproduced. Thismaybeallowedtovarybetweengivenlowerandupperbounds.Theformernormallyre#ect the rmordersthatarecurrentlyoutstanding,whilethelattercorrespondtothemaximum capacityofthemarket.However,certaindiscountsmayhavetobeo!eredtosellsheetsoverand abovethequantitiesforwhichrmordersareavailable. p69 Thenumberofrawrollsofeachstandardwidthtobecut. Rollsmaybeavailableinoneormorestandardwidths,eachofadi!erentunitprice. p69 Thecuttingpatternforeachrawroll. Cuttingtakesplaceonamachineemployinganumberofknivesoperatinginparallelonarollof standardwidth.Whilethepositionoftheknivesmaybechangedfromonerolltothenext,such changesmayincurcertaincosts.Furthermore,theremaybecertaintechnologicallimitationson theknifepositionsthatmayberealizedbyanygivencuttingmachine. Theoptimalsolutionoftheaboveproblemisoftenassociatedwiththeminimizationofthe trima waste that is generally unavoidable since rolls of standard widths are used. However, trim-lossminimizationdoesnotnecessarilyimplyminimizationofthecostoftherawmaterials (rolls)beingusedespeciallyifseveralstandardrollsizesareavailable.Amoredirecteconomic criterionisthemaximizationoftheprotoftheoperationtakingaccountof: p69 therevenuefromproductrollssales,includingthee!ectsofanybulkdiscounts; p69 thecostoftherollsthatareactuallyused; p69 thecosts,ifany,ofchangingtheknifepositionsonthecuttingmachine; p69 thecostofdisposingoftrimwaste. Theaboveconstitutesahighlycombinatorialproblemanditisnotsurprisingthattraditionally itssolutionhasoftenbeencarriedoutmanuallybasedonhumanexpertise.Thesimpliedversion ofthisproblemissimilartothecuttingstockproblemknownintheoperation-researchliterature, whereanumberoforderedpiecesneedtobecuto!biggerstoredpiecesinthemosteconomic fashion.Inthe1960sandthe1970s,severalscienticarticleswerepublishedontheproblemof 1042 G. Schilling, M.C. Georgiadis/Computers that raw rolls of the type t that permits the smallest minimum 1044 G. Schilling, M.C. Georgiadis/Computers andthateachrawrollwillbeusedtoproduceproductrollsof asingletypeonly.Overall,thisleadstothefollowingupperboundonthenumberofrawrollsthat mayberequired: Jp13p0p24 p39 p9 p71p14p16 Np13p0p24 p71 p87min p82 Bp13p9p14 p82 /B p71 p88 . (1) We can also calculate a lower bound Jp13p9p14 on the minimum number of raw rolls that are necessarytosatisfytheminimumdemandfortheexistingorders.Wedothisbyassumingthatrolls of the type t allowing the maximum possible engagement Bp13p0p24 p82 are used, and that no trim is produced.However,wemustalsotakeaccountofpossiblelimitationsonthenumberofavailable knives. Overall, this leads to the following lower bound on the number of rolls that may berequired: Jp13p9p14max p7 p9p39 p71p14p16 Np13p9p14 p71 B p71 max p82 Bp13p0p24 p82 , p9p39 p71p14p16 Np13p9p14 p71 max p82 Np13p0p24 p82 p8 . (2) 3. Mathematical formulation Theaimofthemathematicalformulationistodeterminethetypetofeachrawrolljtobecut andthenumberofproductrollsofeachtype i tobeproducedfromit. 3.1. Key variables Thefollowingintegervariablesareintroduced: n p71p72 :numberofproductrollsoftype i tobecutoutofrawroll j afii9773 p71 : numberofproductrollsoftype i producedoverandabovetheminimumnumberordered. Wenotethat n p71p72 cannotexceed: p69 themaximumnumber Np13p0p24 p71 ofproductrollsoftype i thatcanbesold; p69 themaximumnumberofproductrollsofwidth B p71 thatcanbeaccommodatedwithinamax- imumengagementBp13p0p24 p82 forarawrolloftype t; p69 themaximumnumber Np13p0p24 p82 ofknivesthatcanbeappliedtoarawrolloftype t. Thisleadstothefollowingboundsfor n p71p72 : 0)n p71p72 )min p1 Np13p0p24 p71 ,max p16p87p82p87p50 Bp13p0p24 p82 B p71 ,max p16p87p82p87p50 Np13p0p24 p82 p2 i1, 2 ,I, j1, 2 ,Jp13p0p24. (3) Also 0)afii9773 p71 )Np13p0p24 p71 !Np13p9p14 p71 , i1, 2 ,I. (4) G. Schilling, M.C. Georgiadis/Computers thissimplyimpliesthatitisnot necessarytocutroll j. Furthermore,thelimitedavailabilityofrawrollsofagiventypetmaybeexpressedintermsof theconstraint p40 p13p0p24 p9 p72p14p16 y p82p72 )JH p82 , t1, 2 ,. (6) 3.3. Cutting constraints Weneedtoensurethat,ifarolljistobecut,thenthelimitationsontheminimumandmaximum engagementareobserved.Thisisachievedviatheconstraints p50 p9 p82p14p16 Bp13p9p14 p82 y p82p72 ) p39 p9 p71p14p16 B p71 n p71p72 ) p50 p9 p82p14p16 Bp13p0p24 p82 y p82p72 , j1, 2 ,Jp13p0p24. (7) Wenotethatthequantityp9p39 p71p14p16 B p71 n p71p72 representsthetotalwidthofallproductrollstobecutoutof rawroll j.Ify p82p72 1forsomerolltype t,thenconstraint(7)ensuresthat Bp13p9p14 p82 ) p39 p9 p71p14p16 B p71 n p71p72 )Bp13p0p24 p82 . 1046 G. Schilling, M.C. Georgiadis/Computers onceagain,atmostoneofthetermsinthissummation canbenon-zero(cf.constraints(5a)and(5b).Thelatterquantityisgivenbyp9p39 p71p14p16 B p71 n p71p72 .Overall, trimdisposalresultsinthefollowingcostterm cp3p9p19p16 p40 p13p0p24 p9 p72p14p16 p1 p50 p9 p82p14p16 Bp18p15p12p12 p82 y p82p72 ! p39 p9 p71p14p16 B p71 n p71p72 p2 . Theabovetermscannowbecollectedinthefollowingobjectivefunction: max p3 p39 p9 p71p14p16 (p p71 Np13p9p14 p71 #afii9773 p71 (p p71 !cp3p9p19p2 p71 )! p40 p13p0p24 p9 p72p14p16 p9 p82p14p16 cp18p15p12p12 p82 y p82p72 !cp2p8p0p14p6p4 p40 p13p0p24 p9 p72p14p17 z p72 !cp3p9p19p16 p40 p13p0p24 p9 p72p14p16 p1 p50 p9 p82p14p16 Bp18p15p12p12 p82 y p82p72 ! p39 p9 p71p14p16 B p71 n p71p72 p2p4 . (11) Notethatthersttermintheaboveobjectivefunction(i.e.p9p39 p71p14p16 p p71 Np13p9p14 p71 )isactuallyaconstantand doesnota!ecttheoptimalsolutionobtained. 3.7. Degeneracy reduction and constraint tightening Ingeneral,thebasicformulationpresentedaboveishighlydegenerate:givenanyfeasiblepoint, onecangeneratemanyotherssimplybyformingallpossibleorderingoftherollsselectedtobecut. Moreover,providedallrawrollsofthesametypearecutconsecutively,allthesefeasiblepointswill correspondtoexactlythesamevalueoftheobjectivefunction. Theabovepropertymayhaveadversee!ectsonthee$ciencyofthesearchprocedure.Therefore, in order to reduce the solution degeneracy without any loss of optimality, we introduce the followingorderingconstraints: p39 p9 p71p14p16 n p71p11p72p92p16 * p39 p9 p71p14p16 n p71p72 , j2, 2 ,Jp13p0p24. (12) Thisensuresthatthetotalnumberofproductrollscutoutofrawrollj!1isneverlowerthanthe correspondingnumberforroll j;allcompletelyunusedrawrollsareleftlastinthisordering. 1048 G. Schilling, M.C. Georgiadis/Computers Bp13p0p24 p82 !Bp13p9p14 p82 ,whichresultsinone lessconstraintforeachroll j. 4. Example problems In this section, we consider four example problems of increasing complexity in order to investigatethecomputationalbehaviorofourformulation.Furthermoreanindustrialcasestudyis alsopresented.Inallcases,weassumethatthemaximumrawrollengagementBp13p0p24 p82 isequaltothe correspondingrollwidthBp18p15p12p12 p82 .TheGAMS/CPLEXvs6.0solverhasbeenusedforthesolution15 andallcomputationswerecarriedoutonaAlphaServer4100.Anintegralitygapof0.1%was assumedforthesolutionofallproblems. 4.1. Example 1 OurrstexampleisbasedonthatgivenbyHarjunkoski9.Sometranslationofthevarious costcoe$cientswasnecessarytoaccountforslightdi!erencesintheobjectivefunctionsusedby thetwoformulations.Alsonotethattheobjectiveusedbythoseauthorsistheminimizationofcost asopposedtothemaximizationofprot;therefore,thesignoftheirobjectivefunctionisopposite tothatofours. G. Schilling, M.C. Georgiadis/Computers thus,withthegiveneconomicdatatheoperationincursaloss. Theoptimalsolution(withinamarginofoptimalityof0.1%)isfoundwithinlessthan1CPUs atnode49ofthebranch-and-boundalgorithmusingabreadthrstsearchstrategy.Itmustbe notedthattheintegralitygapofourformulationiscomparabletothatforoneoftheformulations presentedbyHarjunkoski9despitethefactthatitdoesnotemployanyapriorienumerationof thecuttingpatterns.Ourformulationalsoexaminesasmallnumberofnodesinordertodetectthe optimalpoint(Table3). 1050 G. Schilling, M.C. Georgiadis/Computers 9:84959. 2 GilmorePC,GomoryRE.Alinearprogrammingapproachtothecuttingstockproblem*partII.Operations Research1963;11:86388. 3 Hinxman AI. The trim-loss and assortment problems. a survey. European Journal of Operational Research 1980;5:818. G. Schilling, M.C. Georgiadis/Computers 44:17584. 5 Sweeney PE, Haessler RW. One-dimensional cutting stock decisions for rolls with multiple quality grades. EuropeanJournalofOperationalResearch1990;44:22431. 6 FerreiraJS,NevesMA,FonsecaeCastroP.Atwo-phaserollcuttingproblem.EuropeanJournalofOperational Research1990;44:18596. 7 GradisarM,JesenkoJ,ResinovicG.Optimizationofrollcuttinginclothingindustry.Computers10:S94553. 8 GradisarM,KljajicM,ResinovicG,JesenkoJ.Asequentialheuristicprocedureforone-dimensionalcutting. EuropeanJournalofOperationalResearch1999;114:55768. 9 HarjunkoskiI,WesterlundT,IsakssonJ,SkrifvarsH.Di!erentformulationsforsolvingtrimlossproblemsin apaper-convertingmillwithilp.ComputersandChemicalEngineering1996;20:S1216. 10 HarjunkoskiI,WesterlundT,PornR.Di!erenttransformationsforsolvingnon-convextrim-lossproblemsby minlp.EuropeanJournalofOperationalResearch1998;105:594603. 11 Westerlund T, Isaksson J, Harjunkoski I. Solving a two-dimensional trim-loss problem with milp. European JournalofOperationalResearch1998;104:57281. 12 WesterlundT,HarjunkoskiI,IsakssonJ.Solvingaproductionoptimisationprobleminapaper-convertingmill withmilp.ComputersandChemicalEngineering1998;22:56370. 13 WesterlundT,IsakssonJ.Somee$cientformulationsforthesimultaneoussolutionoftrim-lossandscheduling problems in the paper-converting industry. Transactions of the Institution of Chemical Engineering Part A1998;76:67784. 14 HarjunkoskiI,WesterlundT,PornR,SkrifvarsH.Numericalandenvironmentalconsiderationsonacomplex industrial mixed integer non-linear programming (minlp) problem. Computers and Chemical Engineering 1999;23:154561. 15 BrookeA,KendrickD,MeerausA,RamanR.GAMS.AUsersGuide.GAMSDevelopmentCorporation,1998. Michael C. Georgiadis, Ph.D., is a full time researcher at Chemical Process Engineering Research Institute in Thessaloniki,Greece.HeearnedhisDiplomaofChemicalEngineeringfromAristotleUniversityofThessalonikiand receivedhisM.Sc.andPh.D.inProcessSystemsEngineeringfromImperialCollege,London.Hisresearchinterestsliein theareasofmixedintegerandcomputer-aidedoptimizationtechniquesfor#exiblemanufacturinginprocessindustries, production scheduling, planning and dynamic modeling and simulation. He is the author of over 15 journal and conferencepublications. GordianSchilling,Ph.D.,isaprocessdevelopmentchemicalengineeratCibaSpecialtyChemicalsInc.inSwitzerland. HeearnedhisDiplomaofEngineeringfromETH,ZurichandreceivedhisPh.D.inProcessSystemsEngineeringfrom ImperialCollege,London. 1058 G. Schilling, M.C. Georgiadis/Computers & Operations Research 29 (2002) 10411058