搜索
:100124098(2007)0920091207X,,(,710049):,,(),,,:,3:;;;:TP18:A1,nmim(oi1,oi2,,oim)oik(ik)Mik,pik,oi1,oi2,,oim,,ini(oi1,oi2,,oini)oik,Aikoikjpikj0(flexiblejobshopschedulingprob2lem,fJSP)oikM(oik)Aik,sik.:(CM)(WM),:,,,(jobshopschedulingproblem,JSP),fJSP,,fJSPJSPJSPNP[1],fJSPNP,fJSPJSP,:[2-5]Jurisch[6]HurinkChambers[7,8]MastrolilliGambardella,[9],Yang[10]KacemBorne,ZhangGen[11,12]XiaWu(PSO)(SA)[13][14,15]fJSP,,2259(165)Vol.25,No.920079SystemsEngineeringSept.,2007X:2007204230:(70433003);836(2003AA2413033):(19742),,,:,,;(19782),,,:,;(19552),,,:,,2.1,:,:(v1);(v2)1:2o1,2,v1(2)o1,21Gen,i(v2)ni,,2:o2,1:o4,1:o3,1:o1,1:o4,2:o1,2:o4,3:o3,2:o2,2:o1,3:o3,3:o1,4:o2,3:o4,4:o3,4:o2,4.2Gen,2.2,,,,,,,,sik,cikoikoikoi(k-1)j[tSj,tEj](tSjtEj),oik:sik=max{tSj,ci(k-1)},tSj,k2k=1(1)oiktEjoik,[tSj,tEj]oik,max{tSj,ci(k-1)}+pikjtEj,tSj+pikjtEj,k2k=1(2),joik,oik,oik,oik2.3,,3,Gen,2,434292007,,,:(PMX),Gen,,2.4,,,,,3[16],,,:,3.1,,,,,,[17-19]:G=(N,A,E),N,AE.G,(A),(E)44,55fJSPTheSchedule={(o1,1,M4:0216),(o1,2,M3:21233),(o1,3,M3:33251),(o1,4,M1:51269),(o2,1,M2:0216),(o2,2,M4:942112),(o2,3,M1:1122136),(o2,4,M4:1362148),(o3,1,M3:0221),(o3,2,M1:21245),(o3,3,M2:45268),(o3,4,M1:692105),(o4,1,M2:16232),(o4,2,M4:32262),(o4,3,M4:62294),(o4,4,M3:942118)}5,ST,fJSP,5,PJ(r)r,rPM(r)r,rrv,vr,SJ(r),rv,vr,SM(r)r,r,,(,):399,:,:,,,,,,,fJSP,,,[20],:,;(),();,,,,66,oikjAik3.2,,:fJSP,,,,,:,3.3N(i)i:N2(i)i,:N2(i)=jN(i)N(j),,,,,,,,,,,,4,[13](nm)Kacem[11],ZhangGen[12],XiaWu[13],Pentium4CPU3.0GHz512MB,WindowXP,Delphi1115003000.50.34.188,8,8,27[13]20,20,749200716.4,1788(cM=14,wM=12,wT=77)2ALAL+CGAKacem[11],PSO+SAXiaWu[13]288hGAGAALAL+CGAPSO+SAhGAcM16161516151614wM121312wT777579757573774.21010,1010,30[13]2020,826.50,15381010(cM=7,wM=5,wT=43)31010hGAGAAL+CGAPSO+SAhGAcM7777wM7565wT534544434.315101015,56[13]20,20,,599,:9497.75591510(cM=11,wM=11,wT=91)41510AL+CGAPSO+SAhGAcM23241211wM11111111wT959191915151095à97.7589.40106.1017.855,,,,,fJSP,,,,,,,:[1]GareyMR,JohmsonDS,SethiR.Thecomplexityofflowshopandjobshopscheduling[J].Mathemat2icsofOperationalResearch,1976,1:117129.[2]SteckeKS.Formulationandsolutionofnonlinearintegerproductionplanningproblemsforflexiblemanufacturingsystems[J].ManagementScience,1983,29:273288.[3]AkellaR,ChoongY.Performanceofahierarchicalproductionschedulingpolicy[J].IEEETransactionsonComponents,HybridsandManufacturingTech2nology,1984,7(3):225248.[4]BonaB,BrandimarteP.Hybridhierarchicalschedul2ingandcontrolsystemsinmanufacturing[J].IEEETransactionsonRoboticsandAutomation,1990,6(6):673686.[5]BrandimarteP.Routingandschedulinginaflexiblejobshopbytabusearch[J].AnnalsofOperationsResearch,1993,22:158183.[6]JurischB.Schedulingjobsinshopswithmulti2purposemachines[D].FachbereichMathematiköInformatik,UniversitatOsnabruck,1992.[7]HurinkE,JurischB,TholeM.Tabusearchforthejobshopschedulingproblemwithmulti2purposemachine[J].OperationsResearchSpektrum,1994,69200715:205215.[8]ChambersJB.Classicalandflexiblejobshopschedulingbytabusearch[D].UniversityofTexasatAustin,1996.[9]MastrolilliM,GambardellaLM.Effectiveneighbor2hoodfunctionsfortheflexiblejobshopproblem[J].JournalofScheduling,2000,3:320.[10]YangJB.GA2baseddiscretedynamicprogrammingapproachforschedulinginFMSenvironments[J].IEEETransactionsonSystems,Man,andCyber2netics-PartB,2001,31(5):824835.[11]KacemI,HammadiS,BorneP.Approachbylocal2izationandmultiobjectiveevolutionaryoptimizationforflexiblejob2shopschedulingproblems[J].IEEETransactionSystems,Man,andCybernetics-PartC,2002,32(1):113.[12]ZhangHP,GenM.Multistage2basedgeneticalgo2rithmforflexiblejob2shopschedulingproblem[J].JournalofComplexityInternational,2005,11:223232.[13]XiaW,WuZ.Aneffectivehybridoptimizationapproachformuti2objectiveflexiblejob2shopschedulingproblem[J].Computers&IndustrialEngineering,2005,48:409425.[14],,.[J].,2004,4:3234.[15],,,.[J].,2007,(2):161165.[16]MoscatoP,Norman,M.Amemeticapproachforthetravelingsalesmanproblem:implementationofacomputationalecologyforcombinatorialoptimiza2tiononmessage2passingsystems[P].ProceedingsoftheInternationalConferenceonParallelComput2ingandTransputerApplications,Amsterdam,1992.[17]AdamsJ,BalasE,ZawackD.Theshiftingbottle2neckprocedureforjobshopscheduling[J].Manage2mentScience,1988,34(3):391401.[18]BalasE,VazacopoulosA.Guidedlocalsearchwithshiftingbottleneckforjobshopscheduling[J].ManagementScience,1998,44(2):262275.[19]GoncalvesJF,MendesJJM,ResendeMGC.Ahybridgeneticalgorithmforthejobshopschedulingproblem[J].EuropeanJournalofOperationalRe2search,2005,167:7795.[20]NowickiE,SmutnickiC.Afasttaboosearchalgo2rithmforthejob2shopproblem[J].ManagementScience,1996,42(6):797813.AHybridofGeneticAlgorithmandBottleneckShiftingforFlexibleJobShopSchedulingProblemsCHENGang,GAOJie,SUNLin2yan(SchoolofManagement,XianJiaotongUniversity,Xian710049,China)Abstract:Flexiblejobshopschedulingproblem(fJSP)isanextensionoftheclassicaljobshopschedulingproblem,whichprovidesacloserapproximationtorealschedulingproblems.Wedevelopanewgeneticalgorithmhybridizedwithaninnova2tivelocalsearchprocedure(bottleneckshifting)forthefJSP.Thegeneticalgorithmusestwovecto