ORIGINALARTICLEAclustering-basedmodelingschemeofthemanufacturingresourcesforprocessplanningHuan-MinXu&Dong-BoLiReceived:12December2006/Accepted:30April2007/Publishedonline:14June2007#Springer-VerlagLondonLimited2007AbstractProcessplanningdetermineshowaproductistobemanufacturedand,therefore,isoneofthekeyelementsinthemanufacturingprocess.Thebasiccruxofcomputer-aidedprocessplanning(CAPP),however,isthediversityofmanufacturingbackgroundandthecomplexityofprocessplanning.Sincetheprocessplansaregeneratedondemandwiththemanufacturingresourcesonashopfloor,modelingmethodofthemanufacturingresourcesisoneofmostim-portantissuesincomputer-aidedprocessplanning.Hence,themajorobjectiveofthisresearchistocreateaclustering-basedmodelingschemeofthemanufacturingresourcesforprocessplanning.Thismodelingschemecombinesclusteringmethodwithaveragingmethodsoastoreasonablypartitionandclassifythemanufacturingresourcesonashopfloor.Theproposedapproachprovidesoneofsearchstrategiesofmachinetoolsforprocessplanning,especiallyfortheselectionofmachinetools.Finally,anillustrativeexampleisappliedtodescribetheclustering-basedmodelingscheme.KeywordsProcessplanning.Clustering.Similarity.Computer-aidedprocessplanning(CAPP)1IntroductionProcessplanningdetermineshowaproductistobemanufac-tured.Itis,thus,themostimportanttaskinproductionpreparationsandthefoundationofallproductionactivities.Inthepast,theprocessplanningactivityhastraditionallybeenexperience-basedandhasbeenperformedmanuallybyhumanprocessplannerswithoutcomputerinvolvedinit.Manualprocessplanning,however,involvessomeproblems:forinstanceaslackofskilledplanners,inconsistencyofprocessplansduetovariabilityamongtheplannersjudgementandexperience,lowefficiencyinplangeneration,slowresponsetothechangesinpracticalmanufacturingenvironment,andsoon.Toalleviatetheseproblems,acomputer-aidedapproachhasbeentaken.SincetheideaofusingcomputersinprocessplanningactivitywasdiscussedbyNiebel1,notableeffortshavebeenmadetowardthefieldofautomatedprocessplanning.OtherearlyinvestigationsonthefeasibilityofautomatedprocessplanningcanbefoundinSheckandBerra2,3.ToperformprocessplanningautomaticallyonacomputerortointegrateCAD/CAPP/CAM,moreandmoreresearchersandengineershavedevotedtheirattentiontodifferentaspectsofCAPPinthepastfewdecades.Inrecentyears,CAPPhasbeenrecognizedasakeyelementincomputer-integratedmanufacturing(CIM).ThemajorityoftheresearchfocusesonsomeproblemsofCAPP:suchaspartfeaturesrecognitionorextraction415,processknowl-edgerepresentation1621,processreasoningandinfer-ence2226,andthelike.Thisresearchhasenhancedthediversityoftheknowledgerepresentationandinferenceapproachesinprocessplanningandimprovedtheperfor-manceofCAPPsystems,todifferentextents,respectively.Consequently,alltheseresearchhaveacceleratedandfa-cilitatedthedevelopmentofautomaticprocessplanning.Theultimategoaloftheresearchistoenablefullyautomatedprocessplanningsystem,withouthumand.SincetremendousefforthasbeenmadetodevelopCAPPsystems,thebenefitsofCAPPinreal-lifemanufacturingIntJAdvManufTechnol(2008)38:154162DOI10.1007/s00170-007-1075-zH.-M.Xu(*):D.-B.LiSchoolofMechanicalEngineering,NanjingUniversityofScienceandTechnology,Nanjing210094,PeoplesRepublicofChinae-mail:alexandra_D.-B.Lie-mail:db_environmentsareyettobeseen.However,thetotallyautomaticprocessplanningusingcomputersisstillfarfrombeingapracticalindustrialapplication.Besidesthecom-plexityofprocessplanning,oneofthemainreasonsforthisisthelackofsystematicinvestigationoftheprinciplesandmethodologyofmodelingthemanufacturingresourcesinCAPP.SincethebasiccruxofCAPPisthediversityofmanufacturingbackgroundandthecomplexityofprocessplanning,modelingthemanufacturingresourcesisoneoftheprimaryconcernsofCAPP.Moreover,oneofthemajordifficultiesinCAPPinarealmanufacturingenvironmentishowtobuildthemodelofthemanufacturingresources,whichcanproperlyorganizemanufacturingmachines.Therefore,themajorobjectiveofthispaperistocreateaclustering-basedmodelingschemeofthemanufacturingresourcesforprocessplanning.Mostmodelingapproachesofmanufacturingresources,however,havebeenstudiedtocopewithproductionplanningandcontrolproblemsorresourceallocationtounleashtheunder-utilizedresourceflexibility,etc.2731.Therefore,thisstudypresentsamodelingapproachthatcombinesaclusteringmethodwithaveragingmethodsoastoreasonablypartitionandclassifythemanufacturingresourcesonashopfloor,whichlaysthefoundationforthemeta-modelingparadigmofthemanufacturingresourcesusingmathematicallogic32.Intheremainderofthissection,thestructureofthispaperispresented.ThefirstsectionbrieflyintroducestheresearchbackgroundofprocessplanningandCAPPandalsoexplainsthereasonforrequiringfundamentalresearchintoanewmodelingmethodologyofthemanufacturingresources.Thesecondsectionanalyzesprocessplanningandthemanufacturingresources.Thethirdsectionpresentsaclustering-basedmodelingschemeofthemanufacturingresourcesonashopfloor.Thefourthsectiondescribestheclusteringprocessofthemanufacturingresources.Thefifthsectiondetailsanapplicationcasetoillustratetheclusteringprocess.Finally,thesixthsectiondiscussesthegainsachievedbytheclustering-basedmodelingschemeofthemanufacturingresourcesforprocessplanning.2ProcessplanningandthemanufacturingresourcesProcessplanning,asdefinedbyChangetal.,isanactofpreparingdetailedoperationinstructionstotransformanengineeringdesigntoafinalpartorprocessingdocumenta-tionforthemanufactureofapiecepartorassembly33,34.Processplanningmaybeengagedundertwodifferentconditions24:oneisforanewplantorworkshoptobebuilt；theotherforanexistingplantorworkshop.Intheformercase,itispossibletoselectsolelythemostreasonablemachinetools,accordingtothemanufacturingneeds.Inthelattercase,themachinetoolsshouldbeselectedfromtheexistingequipmentavailableintheplantortheworkshopunlessthepurchaseofsomenewequipmentisplanned.Itmeansthataprocessplannermustpossessnecessaryknowledgeaboutavailableequipmentwhenplanningaprocessineithercase.However,themachiningprocessplanning,whichrequiresavarietyofknowledgeofthemanufacturingresources,isactuallyacomplexprocessconsistingofmanydifferenttasks3337.Fromthetechnologicalpointofview,themachiningprocessplanningmayinvolveseveralorallofthefol-lowingtasksoractivities24,33:SelectionoftheblankSelectionofmachiningprocessesSequencingofmachiningoperationsSelectionofmachinetoolsandcuttingtoolsDeterminingsetuprequirementsCalculationsofcuttingparameters,toolpathplanningSelectionofmachiningparametersGenerationofNCorCNCpartprogramsDesignofjigsandfixturesHowevertoperformprocessplanning,theaboveactivitiesareelementaryfunctionsofmakingaprocessplaninaccordancewithavailablemanufacturingresourcesonashopfloor.Alternatively,theseactivitiesaretheprimaryconcernsofandthefundamentalissuesforprocessplanning.Itis,thus,evidentthatthemodelingapproachofthemanufacturingresourcesgreatlyinfluencestheafore-mentionedfunctionsofprocessplanning.Whilealargenumberoftechnicalpapersonthemanufacturingresourceshavebeenpublished,eachcoveringimportantfacetsofthisproblem.Themajorobjectiveofmostofthemistoenhancethefunctionsandtoincreasetheproductivityofcertainexistingmachinetoolstomeettherequirementsoftheplannedprocesses.Fromtheviewpointofprocessplanning,theultimategoalofstudyingthemanufacturingresourcesinthispaperistoprovideamethodologyofmodelingthemanufacturingresources,morespecifically,machinetoolsontheshopfloor.Furthermore,therearevariousmanufacturingprocessesusedforconvertingrawmaterialsintofinishedparts,forinstanceascasting,forging,welding,punching,forming,machining,heat-treatment,plating,coating,etc.Amongtheprocesses,themachiningprocessplaysanimportantroleinthemanufactureofparts.Themachiningprocessofapartmayinvolvesomeorallofthefollowingmachiningmethods:turning,milling,drilling,boring,reaming,grind-ing,broaching,gear-cutting,etc.,dependingontherequiredshape,dimensions,accuracyandsurfacequalityofthepart24.Inordertoensurethequalityofacompletedpart,itisnecessarytoproperlyselectmachiningprocessesandmachinetoolsandcuttingtoolsandtodeterminemachiningIntJAdvManufTechnol(2008)38:154162155parameters.Anappropriatemodelingapproachofthemanufacturingresources,therefore,facilitatestheafore-mentionedactivitiesofprocessplanning.Aclustering-basedmodelingschemeofthemanufacturingresourcesonashopfloorispresentedinthefollowingsection.3Aclustering-basedmodelingschemeofthemanufacturingresourcesonashopfloor3.1ThemodelingarchitectureofthemanufacturingresourcesThemodelingscenario(Fig.1)assumesthatasetOofNobjects,whichrepresentallthemanufacturingresourcesonarealshopfloor.EachobjectinthesetOisdenotedbyobject1,object2,.,andobjectN,respectively,whileeachobjectinthesetOhasonepredominantmachiningfunctionatleast.Forexample,thepredominantfunctionofthedrillingmachineisdrilling.Oobject1；object2；C1C1C1；objectNfg1Themodelingarchitectureofthemanufacturingresourcesconsistsofthreesteps,suchasclassifying,extractingandclustering,whichareshowninFig.1.TheprocessincludingthreestepsinFig.1abovearedescribedasfollows.3.2ClassifyingbymachiningmethodsThefirststepisthattheseobjectsinthesetOareclas-sifiedaccordingtotheaforementionedmachiningmethods,suchasturning,milling,drilling,boring,reaming,grinding,broaching,gear-cutting,etc.Thatmeanspartitioningtheseobjectsintoasetofclasses,whichdenotebyOK,K=1,2,S(seeFig.1).Theclassesresultingfromclassifyingarerepresentedasfollows:O1O11；O12；C1C1C1；O1aC8C9O2O21；O22；C1C1C1；O2bC8C9C1C1C1C1C1C1C1C1C1C1C1C1C1C1C1C1C1C1OKOK1；OK2；C1C1C1；OKcC8C9C1C1C1C1C1C1C1C1C1C1C1C1C1C1C1OSOS1；OS2；C1C1C1；OSdC8C9wherea+b+c+d=Nwiththenaturalnumbersofa,b,c,dbeingdifferentorthesamevaluessincedifferentshopfloorswithspecificmanufacturingresources.3.3ExtractingtheattributesofeachclassThesecondstepisextractingthecommonattributesofeachclass(asshowninFig.1).Sinceobjectsareclassifiedintothedifferentclassesbythemachiningmethods,objectsinthesameclasshavesomecommonspecificattributes.Forexample,themaximumdrillingdiameterofaholeisoneofcommonimportantattributesofalldrillingmachines.Moreover,eachextractedattributeshouldsatisfythefollowingrequirements:StandingforprocesscapabilityBeingoneofkeyspecificationsHavingthespecificanddefinitevalueorthedomainofvalueHowever,thevalueofthisattributevaryindifferentobjects,forinstanceasdifferentdrillingmachinewithdifferentmaximumdrillingdiameterofahole.TheO(Object1,Object2,ObjectN)ClassifyingbyMachiningmethodsExtractingtheattributesofeachsubset,respectivelyA1.Clusteringbytheattributes,respectivelyClusters:C11,C12,.SubsetO1SubsetOSSubsetO2.CLASSIFYINGEXTRACTINGTHEATTRIBUTESCLUSTERINGASA2Clusters:C21,C22,Clusters:CS1,CS2,Fig.1Aclustering-basedmodelingschemeofthemanufacturingresources156IntJAdvManufTechnol(2008)38:154162aforementionedattributesofclassOK,K=1,2,S,arerepresentedbythecorrespondingsetofAK,K=1,2,S.Theattributesofeachclassaredenotedby:A1A11；A12；C1C1C1；A1pnoA2A21；A22；C1C1C1；A2qnoC1C1C1C1C1C1C1C1C1C1C1C1C1C1C1AKAK1；AK2；C1C1C1；AKrC8C9C1C1C1C1C1C1C1C1C1C1C1C1C1C1C1ASAS1；AS2；C1C1C1；AStC8C9Althoughdifferentmanufacturingresourcescontaindifferentattributes,themethodologyremainsthesameregardlessofspecificobjectsandattributes.Toclarifytheclusteringprocess,apartialexampleOKwillbeappliedinthefollowingpart.ThesetOKofobjects,whichconsistsofasetAKofattributesAK1；AK2；C1C1C1；AKr,aretobeclustered.AnobjectOKiinthesetOKcanbelogicallyrepresentedasaconjunctionofattribute-valuepairsAKi1VKi1C2C3AKi2VKi2C2C3C1C1C1AKijVKijhiC1C1C1AKirVKirC2C3,whereiandjarepositiveintegerswith1icand1jr.Withoutambiguity,werepresentOKiasavectorVKi1；VKi2；.VKirC2C3.EachvalueofattributesofeachobjectOKiinthesetOKisdenotedbyitscorrespondingelementinthefollowingmatrixVK:VKVOK；AKC0C1OK1OK2.OKcAK1AK2C1C1C1AKrVK11VK12C1C1C1VK1rVK21VK22C1C1C1VK2r.VKc1VKc2C1C1C1VKcr0BBBBBBBB1CCCCCCCCA2whereKisapositiveintegerwith1KS.3.4TheclusteringprocessThethirdstepisclusteringontheobjectsineachclassOK,dependingontheattributesinthesetofAK,whereKisanintegerfor1KS.TheclusteringresultdenotesbytheclusterssuchasC11；C12；C1C1C1C21；C21；C1C1C1.The