外文翻译用蚁群算法在刀库索引位置的优化配置Word文档格式.docx

外文翻译用蚁群算法在刀库索引位置的优化配置Word文档格式.docx

《外文翻译用蚁群算法在刀库索引位置的优化配置Word文档格式.docx》由会员分享，可在线阅读，更多相关《外文翻译用蚁群算法在刀库索引位置的优化配置Word文档格式.docx（18页珍藏版）》请在冰点文库上搜索。

1Introduction

Intoday’smanufacturingenvironment,severalindustriesareadaptingflexiblemanufacturingsystems（FMS）tomeettheever-changingcompetitivemarketrequirements.CNCmachinesarewidelyusedinFMSduetotheirhighflexibilityinprocessingawiderangeofoperationsofvariouspartsandcompatibilitytobeoperatedunderacomputercontrolledsystem.TheoverallefficiencyofthesystemincreaseswhenCNCmachinesareutilizedtotheirmaximumextent.Sotoimprovetheutilization,thereisaneedtoallocatethepositionsofcuttingtoolsoptimallyonthetoolmagazines.

ThecuttingtoolsonCNCmachinescanbechangedorpositionedautomaticallywhenthecuttingtoolsarecalledwithinthepartprogram.TodothisturretsareusedinCNClathemachinesandautomatictoolchangers（ATC）inCNCmillingmachines.ThepresentmodelcanbeusedeitherfortheATCmagazinesorturretsonCNCmachines.

Theindexingtimeisdefinedasthetimeelapsedinwhichaturretmagazine/ATCmovesbetweenthetwoneighbouringtoolstationsorpockets.Bi-directionalindexingofthetoolmagazineisalwayspreferredoveruni-directionalindexingtoreducethenon-machiningtimeofthemachine.Inthisthemagazinerotatesinbothdirectionstoselectautomaticallythenearerpathbetweenthecurrentstationandtargetstation.Thepresentworkconsidersbi-directionalmovementofthemagazine.Inbidirectionalindexing,thedifferencebetweentheindexnumbersofcurrentstationandtargetstationiscalculatedinsuchawaythatitsvalueissmallerthanorequaltohalfofthemagazinecapacity.

Derelietal.[1]formulatedthepresentproblemasa“travelingsalesmanproblem”（TSP）,whichisNPcomplete.Theyappliedgeneticalgorithms（GA）tosolvetheproblem.Dorigoetal.[2,3]introducedtheantcolonyalgorithm（ACA）forsolvingtheNP-completeproblems.ACAcanfindthesuperiorsolutiontoothermethodssuchasgeneticalgorithms,simulatedannealingandevolutionaryprogrammingforlarge-sizedNP-completeproblemswithminimumcomputationaltime.So,ACAhasbeenextendedtosolvethepresentproblem.

2Methodology

Determinationoftheoptimalsequenceofmanufacturingoperationsisaprerequisiteforthepresentproblem.Thissequenceisusuallydeterminedbasedonminimumtotalset-upcost.Theauthors[4]suggestedanapplicationofACAtofindtheoptimalsequenceofoperations.Oncethesequenceofoperationsisdetermined,thefollowingapproachcanbeusedtogettheoptimalarrangementofthetoolsonthemagazine.

Step1Initiallyasetofcuttingtoolsrequiredtoexecutethefixed（optimal）sequenceofthemanufacturingoperationsisassigned.Eachoperationisassignedasinglecuttingtool.Eachtoolischaracterizedbyacertainnumber.Forexample,letthesequenceofmanufacturingoperations{M1-M4-M3-M2-M6-M8-M9-M5-M7-M10}beassignedtothesetofcuttingtools{T8-T1-T6-T4-T3-T7-T8-T2-T6-T5}.Thesetoftoolscanbedecodedas{8-1-6-4-3-7-8-2-6-5}.HerethemanufacturingoperationM1requirescuttingtool8,M4requires1andsoon.Intotalthereareeightdifferenttoolsandthuseightfactorialwaysoftoolsequencespossibleonthetoolmagazine.

Step2ACAisappliedastheoptimizationtooltofindthebesttoolsequencethatcorrespondstotheminimumtotalindexingtime.Foreverysequencethatisgeneratedbythealgorithmthesamesequenceofindexpositions（numbers）isassigned.Forexample,letthesequenceoftools{4-6-7-8-2-5-3-1}begeneratedandhenceassignedtotheindexingpositions{1-2-3-4-5-6-7-8}inthesequentialorder,i.e.tool4isassignedtothe1stposition,tool6tothe2ndpositionandsoon.

Step3Thedifferencesbetweentheindexnumbersofsubsequentcuttingtoolsarecalculatedandthentotaledtodeterminethetotalnumberofunitrotationsforeachsequenceofcuttingtools.Absolutedifferencesaretobetakenwhilecalculatingthenumberofunitrotationsrequiredfromcurrenttooltotargettool.Thisfollowingsectiondescribesanexampleindetail.

ThefirsttwooperationsM1andM4inthepre-assumedfixedsequenceofoperationsrequirethecuttingtools8and1,respectively.Thetoolsequencegeneratedbythealgorithmis{4-6-7-8-2-5-3-1}.Inthissequencetools8and1areplacedinthe4thand8thindexingpositionsoftheturret/ATC.Hencethetotalnumberofunitrotationsrequiredtoreachfromcurrenttool8totargettool1is|4-8|=4.Similarlythetotalnumberofunitrotationsrequiredfortheentiresequenceis|4-8|+|8-2|+|2-1|+|1-7|+|7-3|+|3-4|+|4-5|+|5-2|+|2-6|=30.

Step4Minimizationoftotalindexingtimeistakenastheobjectivefunction.Thevalueoftheobjectivefunctioniscalculatedbymultiplyingthetotalnumberofunitrotationswiththecataloguevalueofturret/ATCindextime.Ifanindextimeof4sisassumedthenthetotalindextimerequiredforthetoolsequencebecomes120s.

Step5AsthenumberofiterationsincreasesACAconvergestotheoptimalsolution.

3Allocationpolicy

Thefollowingarethethreecaseswherethetotalnumberofavailablepositionscanberelatedwiththetotalnumberofcuttingtoolsemployed.

Case1Thenumberofindexpositionsisequaltothenumberofcuttingtools

Case2Thenumberofindexpositionsisgreaterthanthenumberofcuttingtools（a）withoutduplicationoftools,（b）withduplicationtools

Case3Thenumberofindexpositionsissmallerthanthenumberofcuttingtools

Iftheproblemfallsintocase1,duplicationofcuttingtoolsinthetoolingsetisnotrequiredasthesecondset-upalwaysincreasesthenon-machiningtimeofthemachine.

Table1Listoffeaturesandtheirabbreviations

Incase2,theeffectofduplicationofcuttingtoolsshouldbetestedcarefully.Mostofthetimestheduplicationoftoolingistooexpensive.Case3leadstofindingthecuttingtoolstobeusedinthesecondset-up.However,othersubphasesarepossibleincases2（b）and3.TheduplicatedtoolsmaybeusedinsuchawaythatnounloadedindexisleftonATCorsomeindexingpositionsareleftunloaded.

Table2Operationsassignedtothefeatures

4Antcolonyalgorithm

Theantcolonyalgorithm（ACA）isapopulation-basedoptimizationapproachthathasbeenappliedsuccessfullytosolvedifferentcombinatorialproblemsliketravelingsalesmanproblems[2,3],quadraticassignmentproblems[5,6],andjobshopschedulingproblems[7].Thisalgorithmisinspiredbytheforagingbehaviourofreallifeantcoloniesinwhichindividualantsdepositasubstancecalledpheromoneonthepathwhilemovingfromonepointtoanother.Thepathswithhigherpheromonewouldbemorelikelytobeselectedbytheotherantsresultinginfurtheramplificationofcurrentpheromonetrails.Becauseofthisnature,aftersometimeantswillselecttheshortestpath.Thealgorithmasapplicabletothepresentproblemisdescribedinthefollowingsection.

Itisassumedthatthereis‘k’numberofantsandeachantcorrespondstoaparticularnode.Thenumberofantsistakenasequaltothenumberofnodesrequiredtoexecutethefixedsetofmanufacturingoperations.Thetaskofeachantistogenerateafeasiblesolutionbyaddinganewcutting\toolatatimetothecurrentone,tillalloperationsarecompleted.Anant‘k’situatedinstate‘r’movestostate‘s’usingthefollowingstatetransitionrule:

Table3Cuttingtoolsassignedtooptimalsequenceofoperations

Whereτ（r,s）iscalledapheromonelevel.τ（r,s）’sarechangedatruntimeandareintendedtoindicatehowusefulitistomakemove‘s’wheninstate‘r’.η（r,s）isaheuristicfunction,whichevaluatestheutility

ofmove‘s’whenat‘r’.Inthepresentwork,itistheinverseofthenumberofunitrotationsrequiredtomovefrom‘r’to‘s’.

Parameter‘β’weighstherelativeimportanceoftheheuristicfunction.‘q’isavaluechosenrandomlywithuniformprobabilityin[0,1],and‘q0’e0q01Tisaparameter.Thesmallerthe‘q0’,thehighertheprobabilitytomakearandomchoice.Inshort‘q0’determinestherelativeimportanceofexploitationversusexplorationinEq.1.

Jk（r）representsthenumberofstatesstilltobevisitedbythe‘k’antwhenat‘r’.Sisarandomvariableselectedaccordingtothedistribution

givenbyEq.2,whichgivestheprobabilitywithwhichanantinoperation‘r’chooses‘s’tomoveto.

Thisstatetransitionrulewillfavourtransitionstowardsnodesconnectedbyshortedgeswithhighamountoftrail.

4.1Localupdatingrule

Whilebuildingasolution,antschangetheirtrailsbyapplyingthefollowinglocalupdatingrule:

Whereτ0representstheinitialpheromonevalue.

4.2Globalupdatingrule

Globaltrailupdatingprovidesahigheramountoftrailtoshortersolutions.Inasensethisissimilartoareinforcementlearningschemeinwhichbettersolutionsgetahigherreinforcement.

Onceallantshavecompletedtheirsolutions,edges（r,s）belongingtotheshortestsolutionmadebyananthavetheirtrailchangedbyapplyingthefo