会员注册 | 登录 | 微信快捷登录 支付宝快捷登录 QQ登录 微博登录 | 帮助中心 人人文库renrendoc.com美如初恋!
站内搜索 百度文库

热门搜索: 直缝焊接机 矿井提升机 循环球式转向器图纸 机器人手爪发展史 管道机器人dwg 动平衡试验台设计

   首页 人人文库网 > 资源分类 > DOC文档下载

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

  • 资源星级:
  • 资源大小:1.97MB   全文页数:17页
  • 资源格式: DOC        下载权限:注册会员/VIP会员
您还没有登陆,请先登录。登陆后即可下载此文档。
  合作网站登录: 微信快捷登录 支付宝快捷登录   QQ登录   微博登录
友情提示
2:本站资源不支持迅雷下载,请使用浏览器直接下载(不支持QQ浏览器)
3:本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰   

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

LargescalenestingofirregularpatternsusingcompactneighborhoodalgorithmS.K.Cheng,K.P.RaoThetypicalnestingtechniquethatiswidelyusedisthegeometricaltiltingofasinglepatternorselectedclusterstepbystepfromtheoriginalpositiontoanorientationof1808,i.e.orthogonalpacking.However,thisisablindsearchofbeststocklayoutand,geometrically,itbecomesinef®cientwhenseveralpatternentitiesareinvolved.Also,itisnothighlysuitableforhandlingpatternswitharangeoforientationconstraints.Inthispaper,analgorithmisproposedwhichcombinesthecompactneighborhoodalgorithmCNAwiththegeneticalgorithmGAtooptimizelargescalenestingprocesseswiththeconsiderationofmultipleorientationconstraints.2000ElsevierScienceS.A.Allrightsreserved.KeywordsCuttingstockproblemNestingCompactneighborhoodalgorithmGeneticalgorithmOrientationconstraints1.IntroductionThecuttingstockproblemisofinteresttomanyindustrieslikegarment,paper,shipbuilding,andsheetmetalindustries.GilmoreandGomory7haveinitiatedtheresearchworktosolvetherectangularcuttingstockproblembyusinglinearprogramming.Fortheirregularcase,Adamowicz1attemptedtouseaheuristicapproachwhichdividestheproblemintotwosubproblems,calledclusteringandnesting.Clusteringistospecifyacollectionofpatternsthat®twelltogetherbeforenestingontoagivenstock.Nestingofpatternsorclusterscanbebroadlydividedintotwobroadcategories,namely,smallscaleandlargescale.Thedifferencebetweenthemisthelevelofduplicationoftheclusteronthegivenstock.Forsmallscalenesting,weonlyneedto®ndtheinterorientationrelationshipbetweentheselectedclusterandthegivenstock4.However,theproblembecomesmorecomplicatedforlargescalenestingsincetheinterspacerelationshipbetweentheduplicatedclustersshouldalsobeconsidered.Traditionally,twobasictechniquesarepopularlyusedforgeneratingthistypeofnestinghexagonalapproximationandorthogonalnesting.Atypicalpattern,showninFig.1a,withbothconcaveandconvexfeatures,isselectedtoexplainthesetechniques.TheCorrespondingauthor.Tel.85227888409fax85227888423.Emailaddressmekpraocityu.edu.hkK.P.Raopatterncontourisplottedwiththehelpofadigitizer,asshowninFig.1b,andhasanareaApof74.44sq.units.InthehexagonalapproximationsuggestedbyDoriandBenBassat5,thepatternis®rstapproximatedusingaconvexpolygonwhichisfurtherapproximatedbyanotherconvexpolygonwithfewernumberofentitiesuntilanhexagonalenclosureisobtained,asshowninFig.1c.Thehexagonisthenpavedonagivenstockwithnooverlappingoftheformer6.TheresultantlayoutgeneratedbyuseofthistechniqueisgiveninFig.1e.Itisreadilyevidentthatthetechniqueisnothighlyef®cientduetothepoorapproximationperformance,especiallyinthecaseofhighlyirregularpatterns.Anotherproblemisthatthepatternorclustercanassumetwopositionsonly0or1808,withnoexploitationorconsiderationofotherpermissiblerangeoforientations.Inthesecondtechnique,usedbyNee9,thenestingprocessisachievedbyapproximatingasinglepattern/clusterbyarectangleasshowninFig.1d.Thisrectangleisthenduplicatedinanorthogonalway,resultinginthelayoutshowninFig.1f.Thistechniquecanbeeasilyappliedwhentherearenoorpartialorientationconstraints,i.e.thesinglepatternorclustercanrotatewithinacertainrangewhile®ttingitonthestock.Likethehexagonalapproximation,themaindisadvantageofthisapproachisthatthealgorithmsperformanceishighlydependentontheshapeofpatterns.Moreover,inthecaseofmultipleorientationconstraints,the09240136/00/±seefrontmatter2000ElsevierScienceS.A.Allrightsreserved.PIIS0924013600004027136S.K.Cheng,K.P.Rao/JournalofMaterialsProcessingTechnology1032000135±140Fig.1.aThechosen¯atpatternfordemonstratingtheworkingprincipleofCNAalgorithmbpatterncontourobtainedbydigitizerchexagonalapproximationdorthogonalapproximationelayoutgeneratedbyusinghexagonalapproximationyieldingastockutilizationof60.05flayoutgeneratedbyusingorthogonalapproximationyieldingastockutilizationof67.14andglayoutgeneratedbyusingCNAyieldingastockutilizationof74.10.timetakentoestimateasuitablerotationangleforthepatternsisalwaysmuchlonger.Inordertoincreasetheaccuracyandspeedofnesting,ChengandRao4proposedacompactneighborhoodalgorithmCNAthatconsiderstherelationshipbetweenthenumberofneighborsandthesharingspacebetweenthem.Fig.1gshowsatypicallayoutgeneratedusingCNAwhichnormallyyieldshigherpackingdensitywhencomparedwiththeorthogonalandhexagonalapproximations.However,CNA,initspresentform,hasbeenmainlydesignatedfornestingofpatternswiththeconsiderationoffullorientationconstraints,andisnotidealforsituationswheremorefreedomisavailableintheorientationofpatterns.Thisstudyisaimedatimprovingthe¯exibilityofCNAbyincorporatingtheavailablefreedomintheorientationofpatternsandageneticalgorithmGAthatfollowsnaturalrulestooptimizethegeneratedlayouts.ThenewtechniqueistranslatedintoacomputerprogramwritteninCobjectorientedlanguage.Thenewalgorithmcanhandletheproblemofnestingtwodimensional¯atpatternsofanyshapecontaininglinesegmentsandarcs.Withthehelpofatypicalexample,theenhancedcapabilitiesofCNAandtheassociatedcomputerprogramwillbedemonstratedinthispaper.2.DescriptionofcompactneighborhoodalgorithmCNAACNA4tracksthecharacteristicsoftheevolvingneighborhoodswhenthepatternsaremovedtoformdifferentarrangements,assummarizedschematicallyinFig.2a±c.Asthesheardisplacementincreases,theupperandlowerneighborstendtocollapseduetothechangeincrystallizationdirections.Finally,amostcompactstructureandanumericalvalueformaterialyield,calleduniversalcompactutilizationUCU,canbeobtained.NomatterFig.2.TypicalneighborhoodstructuresforcircularpatternsÐaformationoforthogonalpackingunitcellwithNn8andApu16r2bshearingoflayersleadingtoshearedorthogonalpackingandcbestcompactstructurewithhexagonalpackingunitcellwithNn6andAu63r2,whereAuistheareaofaunitcell,rtheradiusofcircularpatternandNnisthenumberofneighborstoconstructtheunitcell.S.K.Cheng,K.P.Rao/JournalofMaterialsProcessingTechnology1032000135±140137Fig.3.aStepsinvolvedinthegenerationofselfslidingpathtocreateaneighborhoodandboptimalneighborhoodstructurewithhexagonalpackingunitcellwithaUCUof83.07.whetherthepatterncanberotatedornot,UCUindicatestheupperlimitofyieldthatmaybepossiblewithanychosenstockandhencecanberegardedasanindexforstoppingcriteriainthenestingprocess.Themainstepsinvolvedin®ndingthecompactneighborhoodare1generatingaselfslidingpathorano®tpolygonNFP1,asshowninFig.3a,whichguidestherelativemovementbetweentwopatternswiththeconsiderationofnooverlappingand2de®ningthecrystallizationdirections,asshowninFig.3b,thatprovideessentialdataforbuildingthewholeneighborhoodby®llingthegivenstockduringlargescalenesting.3.ProposedalgorithmforlargescalenestingTheproposedtechniquesofenhancingthecapabilitiesofCNAbytakingadvantageofageneticalgorithmaredealtinthissection.A¯atpatterncanbedividedintoentitiesoflinesegmentsandarcs.Polygonalrepresentationmethods2expandthisstructureto®lltheentirestock.Fornestingofpatternswithfullorientationconstraint,itisonlynecessarytodecideanestingvectorCDnthatde®neswheretheneighborhoodshouldbetranslatedaroundthegivenstock.However,inthecaseofnestingofpatternswithlimitedornoorientationlimitations,theproblembecomesmorecomplicatedduetoanincreaseinthepossiblecombinationsthatweneedtoconsider.Inthiscase,the®rststepÐwhichisglobalwithorwithoutorientationlimitationsÐistotranslatetheneighborhoodtoanarbitrarypositioninsidethegivenstock,i.e.de®ningavectorCDn.Afterward,anestingangleynistobedeterminedsothatagoodorientationisselectedfortheneighborhoodtogrow.AlltherequiredgeometricaloperationsaresummarizedinFig.4.ItiscriticaltooptimizeCDnandynwhichcan®nallyleadtoamostcompactneighborhoodstructure.Itisbelievedthattherearenouniquemathematicalstepstocalculatetheseparametersforanytypeofstock.Inaddition,wecannotacceptanexhaustivesearchbecauseoftheconstraintsposedoncomputationtime,especiallyinthecaseofnestingofpatternswithtoolongacomputationtime,especiallywhilenestingpatternswithmanyentitiesandconcavefeatures.Hence,inthisstudy,arecentpopularoptimizationtechnique,calledGA,isapplied.Themainprincipleisprovidedinthefollowingsection.3.2.GAforoptimizinglayoutsGA8maintainsapopulationofcandidateproblemsolutions.Basedontheirperformance,the®ttestofthesesolutionsnotonlysurvive,and,analogoustosexualreproduction,exchangeinformationwithothercandidatestoformanewgeneration.Beforestartinganygeneticoperation,oneneedstode®nethe®tnessfunctionandthecodingmethod.Asmentionedearlier,thegoalinnestingofpatternsistoreducethescrapby®ttingtheclusterstogethersothattheyoccupyaminimumarea.Torepresentthecompactnessofaparticularlayout,onecanbecon®dentthatthemostdirectwayistorelateitwiththestockyieldfxYypy1canbeusedtorepresentbothconcaveandconvexarcsassetsofstraightlines.Theactualnumberoflinesisdependentontherequiredaccuracylevel.Also,clearanceoroffsetgenerationisanessentialstepthatcontributestowardsthesuccessofCAD/CAMtechnology.Analgorithmtogeneratetherequiredoffset,calledthreepointislandtracingTPITtechnique2,isincorporatedinthepresentnestingsystem.3.1.CNAforlargescalenestingIntheprevioussection,wehavealreadymentionedthebasicstepsinvolvedinobtainingthebestcompactneighborhood,asshowninFig.3b.Ournextconcernisthedeterminationofthebestpositiontoplacethe®rstpatternandxwherexistheareaofthegivenstockandythetotalareaofthepatternsthatcouldbecutoutfromthegivenstock.Codingcandirectlyandindirectlyin¯uencetheoptimizationprocess.Thisisbecauseourmainconcernishowto®xthetranslationpositioni.e.nestingvectorCDnandthedegreeofrotationi.e.nestingangleyn.Theyarethusselectedasthecodingparametersthatguidethepropertiesi.e.correspondingtonaturalchromosomesforexchangeinthegeneticoperatorsofcrossoverandmutation.3.3.ThegeneticoperatorsAsproposedbyHollandetal.8,theGAaimsatoptimizingthesolutionbymimickingnaturesevolutionary138S.K.Cheng,K.P.Rao/JournalofMaterialsProcessingTechnology1032000135±140Fig.4.Translationoftheneighborhoodtoaprede®nedpositionwithnestingvectorCDnandsubsequentrotationinvolvinganestingangleyn.process.LikehumanbeingsatypicalGAcontainsthefollowinggeneticoperators.3.3.1.InitializationAtthebeginning,apopulationofigeneticsolutionsi.e.layoutsaregeneratedbyrandomlyselectingvaluesforalltheparametersi.e.nestingangleynandnestingvectorCDn.Inrealindustrialapplications,thereareusuallysituationsthatlimittherotationofpatternsfreely.Forexample,inthedesignofprogressivedies,therearemanyrestrictedorientationregionsasaresultofthecostofsettingcorrespondingpilots,limitationsofbendingangleforsubsequentsheetmetaloperations,andthelike.Fig.5showstwotypicalpatternswithdifferentrestrictedandunrestrictedorientationregions.Asaresult,thepositionsthatthesepatternscouldassumearelimitedtotwolimitedrangesinthepresentcases,asshowninthesame®gure.Hence,aftertherandomgenerationofanestingangleyn,thefollowinginequalitycheckhastobesatis®edypjYklynypjYkuwithjYkPIY1jNand1kCpj2whereNandCpjarethenumberofpatternstobenestedi.e.p1,p2,FFFFFF,pNandthenumberofrestrictedorientationregionsofpatternpj,respectively.Fig.5.Rotationconstraintswithrespecttothelowerboundofthe®rstunrestrictedregionÐastationarypatternp1yp1,1l08,yp1,1u308,yp1,2l1708,yp1,2u1908andbmovablepatternp2yp2,1l08,yp2,1u608,yp2,2l2008,yp2,2u2308.

注意事项

本文(外文翻译运用紧凑相邻法则对非规则零件图样进行大规模编排.doc)为本站会员(淘宝运营)主动上传,人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知人人文库网([email protected]),我们立即给予删除!

温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。

copyright@ 2015-2017 人人文库网网站版权所有
苏ICP备12009002号-5