外文翻译运用紧凑相邻法则对非规则零件图样进行大规模编排.doc

Large-scalenestingofirregularpatternsusingcompactneighborhoodalgorithmS.K.Cheng,K.P.Rao*Thetypicalnestingtechniquethatiswidelyusedisthegeometricaltiltingofasinglepatternorselectedclusterstepbystepfromtheoriginalpositiontoanorientationof1808,i.e.orthogonalpacking.However,thisisablindsearchofbeststocklayoutand,geometrically,itbecomesinef®cientwhenseveralpatternentitiesareinvolved.Also,itisnothighlysuitableforhandlingpatternswitharangeoforientationconstraints.Inthispaper,analgorithmisproposedwhichcombinesthecompactneighborhoodalgorithm(CNA)withthegeneticalgorithm(GA)tooptimizelarge-scalenestingprocesseswiththeconsiderationofmultipleorientationconstraints.#2000ElsevierScienceS.A.Allrightsreserved.Keywords:Cuttingstockproblem；Nesting；Compactneighborhoodalgorithm；Geneticalgorithm；Orientationconstraints1.IntroductionThecuttingstockproblemisofinteresttomanyindustrieslikegarment,paper,shipbuilding,andsheetmetalindus-tries.GilmoreandGomory7haveinitiatedtheresearchworktosolvetherectangularcuttingstockproblembyusinglinearprogramming.Fortheirregularcase,Adamowicz1attemptedtouseaheuristicapproachwhichdividestheproblemintotwosub-problems,calledclusteringandnest-ing.Clusteringistospecifyacollectionofpatternsthat®twelltogetherbeforenestingontoagivenstock.Nestingofpatternsorclusterscanbebroadlydividedintotwobroadcategories,namely,small-scaleandlarge-scale.Thediffer-encebetweenthemisthelevelofduplicationoftheclusteronthegivenstock.Forsmall-scalenesting,weonlyneedto®ndtheinter-orientationrelationshipbetweentheselectedclusterandthegivenstock4.However,theproblembecomesmorecomplicatedforlarge-scalenestingsincetheinter-spacerelationshipbetweentheduplicatedclustersshouldalsobeconsidered.Traditionally,twobasictechni-quesarepopularlyusedforgeneratingthistypeofnesting:hexagonalapproximationandorthogonalnesting.Atypicalpattern,showninFig.1a,withbothconcaveandconvexfeatures,isselectedtoexplainthesetechniques.The*Correspondingauthor.Tel.:852-2788-8409；fax:852-2788-8423.E-mailaddress:mekpraocityu.edu.hk(K.P.Rao)patterncontourisplottedwiththehelpofadigitizer,asshowninFig.1b,andhasanarea(Ap)of74.44sq.units.InthehexagonalapproximationsuggestedbyDoriandBen-Bassat5,thepatternis®rstapproximatedusingaconvexpolygonwhichisfurtherapproximatedbyanotherconvexpolygonwithfewernumberofentitiesuntilanhexagonalenclosureisobtained,asshowninFig.1c.Thehexagonisthenpavedonagivenstockwithnooverlappingoftheformer6.TheresultantlayoutgeneratedbyuseofthistechniqueisgiveninFig.1e.Itisreadilyevidentthatthetechniqueisnothighlyef®cientduetothepoorapprox-imationperformance,especiallyinthecaseofhighlyirre-gularpatterns.Anotherproblemisthatthepatternorclustercanassumetwopositionsonly(0or1808),withnoexploita-tionorconsiderationofotherpermissiblerangeoforienta-tions.Inthesecondtechnique,usedbyNee9,thenestingprocessisachievedbyapproximatingasinglepattern/clusterbyarectangleasshowninFig.1d.Thisrectangleisthenduplicatedinanorthogonalway,resultinginthelayoutshowninFig.1f.Thistechniquecanbeeasilyappliedwhenthereareno-orpartial-orientationconstraints,i.e.thesinglepatternorclustercanrotatewithinacertainrangewhile®ttingitonthestock.Likethehexagonalapproximation,themaindisadvantageofthisapproachisthatthealgorithmsperformanceishighlydependentontheshapeofpatterns.Moreover,inthecaseofmultipleorientationconstraints,the0924-0136/00/$±seefrontmatter#2000ElsevierScienceS.A.Allrightsreserved.PII:S0924-0136(00)00402-7136S.K.Cheng,K.P.Rao/JournalofMaterialsProcessingTechnology103(2000)135±140Fig.1.(a)Thechosen¯atpatternfordemonstratingtheworkingprincipleofCNAalgorithm；(b)patterncontourobtainedbydigitizer；(c)hexagonalapproximation；(d)orthogonalapproximation；(e)layoutgeneratedbyusinghexagonalapproximationyieldingastockutilizationof60.05%；(f)layoutgeneratedbyusingorthogonalapproximationyieldingastockutilizationof67.14%；and(g)layoutgeneratedbyusingCNAyieldingastockutilizationof74.10%.timetakentoestimateasuitablerotationangleforthepatternsisalwaysmuchlonger.Inordertoincreasetheaccuracyandspeedofnesting,ChengandRao4proposedacompactneighborhoodalgorithm(CNA)thatconsiderstherelationshipbetweenthenumberofneighborsandthesharingspacebetweenthem.Fig.1gshowsatypicallayoutgeneratedusingCNAwhichnormallyyieldshigherpackingdensitywhencom-paredwiththeorthogonalandhexagonalapproximations.However,CNA,initspresentform,hasbeenmainlydesig-natedfornestingofpatternswiththeconsiderationoffullorientationconstraints,andisnotidealforsituationswheremorefreedomisavailableintheorientationofpatterns.Thisstudyisaimedatimprovingthe¯exibilityofCNAbyincorporatingtheavailablefreedomintheorientationofpatternsandageneticalgorithm(GA)thatfollowsnaturalrulestooptimizethegeneratedlayouts.ThenewtechniqueistranslatedintoacomputerprogramwritteninCobject-orientedlanguage.Thenewalgorithmcanhandletheproblemofnestingtwo-dimensional¯atpatternsofanyshapecontaininglinesegmentsandarcs.Withthehelpofatypicalexample,theenhancedcapabilitiesofCNAandtheassociatedcomputerprogramwillbedemonstratedinthispaper.2.Descriptionofcompactneighborhoodalgorithm(CNA)ACNA4tracksthecharacteristicsoftheevolvingneighborhoodswhenthepatternsaremovedtoformdifferentarrangements,assummarizedschematicallyinFig.2a±c.Asthesheardisplacementincreases,theupperandlowerneighborstendtocollapseduetothechangeincrystallizationdirections.Finally,amostcompactstructureandanumericalvalueformaterialyield,calleduniversalcompactutilization(UCU),canbeobtained.NomatterFig.2.TypicalneighborhoodstructuresforcircularpatternsÐ(a)formationoforthogonalpackingunitcellwithNn8andApu16r2；(b)shearingoflayersleadingtoshearedorthogonalpacking；and(c)bestcompactstructurewithhexagonalpackingunitcellwithNn6andAu63r2,whereAuistheareaofaunitcell,rtheradiusofcircularpatternandNnisthenumberofneighborstoconstructtheunitcell.S.K.Cheng,K.P.Rao/JournalofMaterialsProcessingTechnology103(2000)135±140137Fig.3.(a)Stepsinvolvedinthegenerationofself-slidingpathtocreateaneighborhood；and(b)optimalneighborhoodstructurewithhexagonalpackingunitcellwithaUCUof83.07%.whetherthepatterncanberotatedornot,UCUindicatestheupperlimitofyieldthatmaybepossiblewithanychosenstockandhencecanberegardedasanindexforstoppingcriteriainthenestingprocess.Themainstepsinvolvedin®ndingthecompactneighbor-hoodare:(1)generatingaself-slidingpathorano-®t-polygon(NFP)1,asshowninFig.3a,whichguidestherelativemovementbetweentwopatternswiththeconsidera-tionofnooverlapping；and(2)de®ningthecrystallizationdirections,asshowninFig.3b,thatprovideessentialdataforbuildingthewholeneighborhoodby®llingthegivenstockduringlarge-scalenesting.3.Proposedalgorithmforlarge-scalenestingTheproposedtechniquesofenhancingthecapabilitiesofCNAbytakingadvantageofageneticalgorithmaredealtinthissection.A¯atpatterncanbedividedintoentitiesoflinesegmentsandarcs.Polygonalrepresentationmethods2expandthisstructureto®lltheentirestock.Fornestingofpatternswithfullorientationconstraint,itisonlynecessarytodecideanestingvectorCDnthatde®neswheretheneighborhoodshouldbetranslatedaroundthegivenstock.However,inthecaseofnestingofpatternswithlimitedornoorientationlimitations,theproblembecomesmorecompli-catedduetoanincreaseinthepossiblecombinationsthatweneedtoconsider.Inthiscase,the®rststepÐwhichisglobalwithorwithoutorientationlimitationsÐistotranslatetheneighborhoodtoanarbitrarypositioninsidethegivenstock,i.e.de®ningavectorCDn.Afterward,anestingangleynistobedeterminedsothatagoodorientationisselectedfortheneighborhoodtogrow.Alltherequiredgeometricalopera-tionsaresummarizedinFig.4.ItiscriticaltooptimizeCDnandynwhichcan®nallyleadtoamostcompactneighborhoodstructure.Itisbelievedthattherearenouniquemathematicalstepstocalculatetheseparametersforanytypeofstock.Inaddition,wecannotacceptanexhaustivesearchbecauseoftheconstraintsposedoncomputationtime,especiallyinthecaseofnestingofpatternswithtoolongacomputationtime,especiallywhilenestingpatternswithmanyentitiesandconcavefeatures.Hence,inthisstudy,arecentpopularoptimizationtechni-que,calledGA,isapplied.Themainprincipleisprovidedinthefollowingsection.3.2.GAforoptimizinglayoutsGA8maintainsapopulationofcandidateproblemsolutions.Basedontheirperformance,the®ttestofthesesolutionsnotonlysurvive,and,analogoustosexualrepro-duction,exchangeinformationwithothercandidatestoformanewgeneration.Beforestartinganygeneticoperation,oneneedstode®nethe®tnessfunctionandthecodingmethod.Asmentionedearlier,thegoalinnestingofpatternsistoreducethescrapby®ttingtheclusterstogethersothattheyoccupyaminimumarea.Torepresentthecompactnessofaparticularlayout,onecanbecon®dentthatthemostdirectwayistorelateitwiththestockyieldfxYypy(1)canbeusedtorepresentbothconcaveandconvexarcsassetsofstraightlines.Theactualnumberoflinesisdependentontherequiredaccuracylevel.Also,clearanceoroffsetgen-erationisanessentialstepthatcontributestowardsthesuccessofCAD/CAMtechnology.Analgorithmtogeneratetherequiredoffset,calledthreepointislandtracing(TPIT)technique2,isincorporatedinthepresentnestingsystem.3.1.CNAforlarge-scalenestingIntheprevioussection,wehavealreadymentionedthebasicstepsinvolvedinobtainingthebestcompactneighbor-hood,asshowninFig.3b.Ournextconcernisthedetermi-nationofthebestpositiontoplacethe®rstpatternandxwherexistheareaofthegivenstockandythetotalareaofthepatternsthatcouldbecutoutfromthegivenstock.Codingcandirectlyandindirectlyin¯uencetheoptimi-zationprocess.Thisisbecauseourmainconcernishowto®xthetranslationposition(i.e.nestingvectorCDn)andthedegreeofrotation(i.e.nestingangleyn).Theyarethusselectedasthecodingparametersthatguidetheproperties(i.e.correspondingtonaturalchromosomes)forexchangeinthegeneticoperatorsofcross-overandmutation.3.3.ThegeneticoperatorsAsproposedbyHollandetal.8,theGAaimsatoptimizingthesolutionbymimickingnaturesevolutionary138S.K.Cheng,K.P.Rao/JournalofMaterialsProcessingTechnology103(2000)135±140Fig.4.Translationoftheneighborhoodtoapre-de®nedpositionwithnestingvectorCDnandsubsequentrotationinvolvinganestingangleyn.process.LikehumanbeingsatypicalGAcontainsthefollowinggeneticoperators.3.3.1.InitializationAtthebeginning,apopulationofigeneticsolutions(i.e.layouts)aregeneratedbyrandomlyselectingvaluesforalltheparameters(i.e.nestingangleynandnestingvectorCDn).Inrealindustrialapplications,thereareusuallysituationsthatlimittherotationofpatternsfreely.Forexample,inthedesignofprogressivedies,therearemanyrestrictedorientationregionsasaresultofthecostofsettingcorrespondingpilots,limitationsofbendingangleforsub-sequentsheetmetaloperations,andthelike.Fig.5showstwotypicalpatternswithdifferentrestrictedandunrestrictedorientationregions.Asaresult,thepositionsthatthesepatternscouldassumearelimitedtotwolimitedrangesinthepresentcases,asshowninthesame®gure.Hence,aftertherandomgenerationofanestingangleyn,thefollowinginequalitycheckhastobesatis®ed:ypjYklynypjYkuwithjYkPIY1jNand1kCpj(2)whereNandCpjarethenumberofpatternstobenested(i.e.p1,p2,FFFFFF,pN)andthenumberofrestrictedorientationregionsofpatternpj,respectively.Fig.5.Rotationconstraintswithrespecttothelowerboundofthe®rstunrestrictedregionÐ(a)stationarypattern(p1):yp1,1l08,yp1,1u308,yp1,2l1708,yp1,2u1908；and(b)movablepattern(p2):yp2,1l08,yp2,1u608,yp2,2l2008,yp2,2u2308.