基于改进粒子群算法的制造单元设施布局问题研究

15120122IndustrialEngineeringJournalVol．15No．1February20122011-03-1510ZR14317001965-、、．201804、、。。。TH165A1007-7375201201-0125-06LayoutDesigninCellularManufacturingBasedonImprovedParticleSwarmOptimizationZhangYong-qianDingKui-xueSchoolofMechanicalEngineeringTongjiUniversityShanghai201804ChinaAbstractTraditionallytheintra-cellandinter-celllayoutproblemsinlayoutdesignofcellularmanufac-turingsystemsaresolvedseparatelywhichmayresultinalocaloptimalsolution．Inordertoavoidthelo-caloptimalsolutionthesetwoproblemsaresolvedconcurrentlyinthispaper．Thisproblemisformulatedasanintegerprogrammingwithmultipleobjectives．Inthemodeltheorientationofthefacilitiesthein-tra-cellandinter-celllayoutaredescribedsimultaneously．Duetothecomplexityofthemodelanim-provedparticleswarmoptimizationPSOalgorithmisproposed．ToimproveitsperformancethePSOal-gorithmismodifiedbyadoptingthecrossoveroperatorusedingeneticalgorithm．Asimulationexperimentverifiesthevalidityoftheproposedmethod．KeywordscellularmanufacturingfacilitylayoutparticleswarmoptimizationPSOmulti-objectiveoptimization、Job-shopFlow-shop1。123。Yin2Kaebernick34。。Attahiru5Wang6UShahram7Shahram。。1518-9。。。2pp=12…Pijij=12…Mxiyiili、wiicc=12…C。2．1、∑Mi=1∑Mj=1∑Pp=1npijceilVp/Hp·dij。1npijpijVppHppceildijij。。dij=|xi－xj|+|yi－yj|。22．2max∑ni=1Si/S。3SiiS。minS。S=maxxjt－minxib·maxyjt－minyibij=12…m。4xib、yibix、yxjt、yjtjx、y。2．3。Paretocompromise。10。ημη=1/∑Mi=1∑Mj=1∑Pp=1npijceilVp/Hpli5μ=1/∑ni=1Si6minz=αη∑Mi=1∑Mj=1∑Pp=1npijceilVp/Hpdij+βμS。7αβα+β=1。2．42．4．1hi、viihi=livi=wihi=wivi=lidij1。1Fig．1Parametersofintra-celllayout|xi－xj|≥hi+hj/2+dij8yi=yj。98ij9。2．4．2d2。2Fig．2Theextentedstructureofmanufacturingcell6211Scr。Scr=1cr0{∑Rr=1Scr=1c=12…C10∑Cc=1Scr≤Cr=12…R11xcb－xc'b+Lc'b·xcb+Lcb－xc'b≥0Scr=Sc'r12ycb－yc'b+Wc'b·ycb+Wcb－yc'b≥0Scr≠Sc'r13xcb+Lc≤maxx14ycb+Wc≤maxy。15101112cc'x13cc'y14、15c。33．1PSO。pbestgbest。16～18。vk+1i=ωvki+l1r1pbest－xki+l2r2gbest－xki16xk+1i=xki+vki+1。17l1l2r1r201xkiikpbestigbestωωω=ωmax－ωmax－ωmink/T18ωmax、ωminTk。3．2PSOGA。GAPSO。1011。10、11。Pab2xk+1a=!xk+1a+1－!xkb19xk+1b=!xk+1b+1－!xka20vk+1a=!vk+1a+1－!vkb21vk+1b=!vk+1b+1－!vka。22!0～1。3．3/21PSO2、、。PSO。13。1Tab．1Exampleoftheencodingofaparticle10．52．123．21．3711．613．630．348．2153．5191．610/。1。C72115。。2。M。3。M。7ij=12…7c1=145c2=36c3=27。10.53.211.62－1－32.11.313.60.38.23.51.66－3|5－1－4|7－22734151910－－－－－－。3．4PSOPSO。1gbestn=0。23。3gbestN4。416～18。5pbest。pbestpbest。6gbest。gbestgbest。719～222。4、、23。20m×18m。2Tab．2Theprocesspathsoftheparts110010m3－m8－m4－m11－m15－m6－m72906m1－m2－m9－m13－m5315015m14－m7－m12418020m1－m2－m5－m9－m13514010m3－m11－m8－m10－m4－m15－m6616010m12－m14－m15－m73Tab．3Theareaofthefacilitiesm2××12．8×1．893．2×2．423．6×1．6102．0×1．633．0×1．6113．6×2．043．0×1．8123．0×2．254．8×2．4132．4×2．063．2×2．8142．2×1．872．6×1．6154．2×2．282．8×1．8c1=m1m2m5m9m13c2=m3m4m7m8m15c3=m6m10m11m12m14。1.2m3.0m。6。gen=1000psosize=40gbestN=200l1=l2=2wmax=0.9wmin=0.40100101000.7、0.3。4P=0.4!0～1。6、330104。82114Tab．4Theresultofcellularlayout/m/m26123c3c2c16141211100000015743810000125913010012093．0302．8PSO123c2c3c17154831000012146101101100125913000002143．8256．0123c1c3c21259130000010111214600000834715001002114．0231．16。5。NPPSO。PSO、。。。1AhkioonSBulgakAABektasT．Integratedcellularman-ufacturingsystemsdesignwithproductionplanninganddy-namicsystemreconfigurationJ．EuropeanJournalofOper-ationalResearch20091922414-428．2YinYongYasudaK．Manufacturingcells’designincon-siderationofvariousproductionfactorsJ．InternationalJournalofProductionResearch2002404885-906．3KaebernickHBazargan-LariM．AnintegratedapproachtothedesignofcellularmanufacturingJ．CIRPAnnalsManufacturingTechnology1996451421-425．4．J．20062610850-854．WangAi-minDingGuo-zhiNingRu-xin．RapiddesigntechnologyformanufactruingcellsJ．TransactionsofBei-jingInstituteofTechnology20062610850-854．5AttahiruSAMingyuanCSundereshS．Integratingthegroupingandlayoutproblemsincellularmanufacturingsys-temsJ．ComputersandIndustrialEngineering199223455-58．6WangTai-yueLinHer-changWuKudi-bin．AnimprovedsimulatedannealingforfacilitylayoutproblemsincellularmanufacturingsystemsJ．ComputersandIndustrialEngi-neering1998342309-319．7ShahramANapsiahI．Animprovedalgorithmforlayoutde-signincellularmanufacturingsystemsJ．JournalofManu-facturingSystems2009284132-139．8RussellDKai-yinG．ThefacilitylayoutproblemRecentandemergingtrendsandperspectivesJ．JournalofManu-facturingSystems1996155351-363．9．J．200713101941-1951．SuoXiao-hongLiuZhan-qiang．ModelingandsolutionforfacilitylayoutofmanufacturingsystemsJ．ComputerInte-gratedManufacturingSystems200713101941-1951．10．J．200616110-13．WangDing-yiWangLi-ya．ThefacilitylayoutstudybasedoncellularmanufacturingJ．IndustrialEngineeringandManagement200616110-13．11．J．2007133541-552．ZengYiZhuChang-an．DiscreteoptimizationproblemofmachinelayoutbasedonswarmintelligencealgorithmJ．ComputerIntegratedManufacturingSystems2007133541-552．12KennedyJEberhartR．ParticleSwarmOptimizationC．ProceedingsofIEEEInternationalConferenceonNeural92115NetworksAustraliaPerth19951942-1948．13．J．200930174074-4076．JinYan-xiaHa