搜索
上海交通大学硕士学位论文基于遗传算法的作业车间优化调度方法及其应用姓名：卞长松申请学位级别：硕士专业：工业工程指导教师：范菲雅;钟宝生20080401INPMESJGAPIIAGENETICALGORITHMAPPLIEDTOJOBSHOPSCHEDULINGPROBLEMABSTRACTJobShopSchedulingproblemisatypicalNP-HardProblem,anditisaimportantissuesinCIMSarea.Itisimpossibletofindtheglobaloptimuminpolynomialcomplexity.GoodalgorithmsforJSPproblemcanpromoteporductivityofenterprises.Sothisthesiscanprovidegoodresultsforboththeoryandpractice.Inthisthesis,aSimpleGeneticAlgorithm(SGA)isproposedforJSP.ByusingtheJGAPjavasoftwarepackage,theSimpleGeneticAlgorithm(SGA)canbeeasilyusedtoapplyevolutionprinciplesforJSPproblem.Besides,adecimalencodingmethodforchromosomebasedonprocessingroutesispresentedwhichcanavoiddeadlockandswitchsolutionstochromosomesandviceversaeasily.ExperimentalresultsofsometestdatashowthatSGAcanefficientlysolvetheJSPforourcompany.KEYWORDS:JobShopscheduling,Geneticalgorithm,JGAPIIIDNC(DirectNumericalControl),SEMIJGAPJava11.120901958501015200520062007[1](SEMI)(SEMS,SemiconductorEquipmentMarketStatistics)2007427.720066%SEMS1222007106.5200646%93.173.565.526%29.2200711%/15%21%2%[2]1.2ERP(MES)1.ERP(EnterpriseResourcesPlanning)3ERPMRPERP(SCM)ERPERP2.ERP3.MES(ManufacturingExecutionSystem)MESMES[4]4.MES5.MES,1.2.3.50%ERPERP4ERP[5]1.2.3.4.5.ERPMES90MES(IntegratedMES),MES5(I-MES)MES(MESII)MES863,MES,MESMESMESMESMESMESMES863MES:ERP(DNC)/DNC(DirectNumericalControl)//(FMS)DNCDNCERPDNC:[3]1.ERP,MES2.3.61.320021.2.3.,2004SFCMESMES1.2.3.4.71.4MES1.IE,2.()3.4.,5.:1.5:MESMES8JGAP1Fig.1Flowchartofthethesis1.69::NP2.12.1.11973.(ComputerIntegratedManufacturing,CIM)207080CIMCIMS1986863/CIMSCIMSCIMSCIMCIMSCIMSCIMCMIS:102CIMSFig.2CIMSStructureModelCIMSCIMS[6]2.1.2(ProductionPlanning)11/(ProductionScheduling)/[7]CIMSMES:12DNCERPMES3NP1.2.3.()124./::[8]:[9]1.2.3.:1.(O)2.(F)3.(J)2.1.3(JobShopSchedulingProblem,JSP)13(FSP)JSPJSP()()()[10]:n()N={1,,n}mM={1,,m}Oikqikq1.SikqTikq2.iSikiqTikiq3.iridi;4.Pi[OikpOikq]OikpOikq;5.RqqOikq:MinJ=Max(Siem+Tiem)iN:s.t.SilqSikp=Tikp[OikpOikq]Pi,k,l{1,,mi}iN:SilqSikp=Tikp[OikpOikq]Rqi,jN,qM:ri=Sijq=di-TikpiN,qM,j{1,,ni}:1.2.nm(n!)m3.142.22.2.1:1.DNC(FANUC)PLC2.SFCMES3.IEPDMMESERP4.ERP5.OralceBIERP,MES:1.(ERP,PDM,CRM,RFQ,MES)2.()3.BIERPTiptopERPMESSFCDNCMESMESERPMES152.2.2[11]:[12]1.2.3.4.5.()6.7.8.2.2.3MESERPDNCERP:1.MESPLCBarcode2.3.162.32.3.1[13]:[14](EC)(GA)(EP)(ES)(GP)2.3.2.(ShiftingBottleneckHeuristic)17:[15](1)(2)(3):1.2.3.2.3.3[16][17]2.3.4(SGA)G,lN||G|G|=||nSGA[18](SGA)0111182.419(JSP)NP(GeneticAlgorithm,GA)J.Holland19753.1:[19]3Fig.3GeneticAlgorithm(Population)()20:(Coding)(Decode)p(t)tp(t)Np(t)x1(t),x2(t)(Parent)(Offspring)P(t)(t):1.(Mutation)2.(Crossover)C(t)[20]1.2.3.4.[20]1.2.213.21.2.3.4.5.(Selection)(Crossover)(Mutation)6.3.3Holland(SimpleGeneticAlgorithms,SGA)[21]1:k=0,NP(0)2:P(k)(FitnessValue)3:4:m=0.5:P(k)6:pc[0,1]7:pmP(k+1)m=m+28:mN,5k=k+12.3.4:(OperationSequence)(PrecedenceConstraints)[21]22:[22]1.2.n,m(n!)m3.4.JSP33JSP:[29]1230456107894JSPFig.4SampleFigureofJSP:minf(S1,S2,,Sn)=min{max{ci}},i=1,2,,n,ciimxnJSPn1m3.523:5GAJSPFig.5FrameofGAforJSP5:1.2.3.4.5.3.5.1:1.JSPJSPGAGA242.(Infeasibility)(Illegality)[20]:(Operation-BasedRepresentation)(Job-BasedRepresentation)(PreferenceList-BasedRepresentation)(PriorityRule-BasedRepresentation)(CompletionTime-BasedRepresentation)(Machine-BasedRepresentation)(RandomKeyRepresentation)Gen-Tsujimura-KubotanmnXmm:JSPJSPLamarkian1.Lamarkian25Lamarkian[22]2.13.nxmGA3.5.2:1.12.3.5.3(FitnessFunction):1.Fit[f(x)]=f(x)2.Fit[f(x)]=1/f(x)261.2.(DeceptiveProblem)[22]:3.:(1).(2).(3).()3.5.4:(1).(RandomSearch)(2).(LocalSearch),271.(Selection)(Reproduction):(1).(FitnessProportionalModel)(Rank-BasedModel)(2).(RouletteWheelSelection)(TournamentSelectionModel)(,)(+)(ElitistModel)Holland():6Fig.6FigureofRouletteWheelMethod2.(Crossover)(Recombination)1238765428:(1).(Single-pointCrossover)(2).(Two-pointCrossover)3.(Mutation),:(InversionMutation)(InsertionMutation)Pm3.5.561.N2.C3.MGA4.GSGAG=100%5.W6.S:(PureSelection)S=P(ElitistStrategy)S=E2963.5.613.630(SGA)MESJGAPJavaJGAPMatlabJGAPMES[23]4.1JGAP(JavaGeneticAlgorithmsPackage)NeilRotstan2000JavaJGAP3.3.2200838JAGP3.3.2JGAP:1.2.(GeneticProgramming,GP)3.4.2IEERPnm()PDM314.2.1:1.12.3.4.5.6.4.2.21.PP={p1,p2,,pn},pii(i=1,2,,n)1.Pgaa_fileColumn_NameTable_NamePN(PK)Gaa01CharVer(PK)Gaa01aCharPNameGaa02CharPSpecGaa03CharGCodeGaa04CharABCABCCodeGaa05CharSCodeGaa06CharUnitGaa07Char2.MM={m1,m2,,mm},mjj(j=1,2,,m)+2.Mgab_fileColumn_NameTable_NameProcedureClass(PK)Gab01charIDMachineID(PK)Gab02charMachineNameGab03charWorkStationGab04charWorkSectionGab05charLeadTimeGab06timeStdTimeGab07time32DelivTimeGab08timeMachineStatusGab09charMachineFlagGab10char3.g_mijg_mij=1g_mij=03.g_mgac_fileColumn_NameTable_NamePN(PK)Gac01charVer(PK)Gac02charProcedureSerial(PK)Gac03charProcedureNameGac04charProcedureClass(PK)Gac05charIDMachineID(PK)Gac06charCapabilityGac07char4.g_mM1()M2M3M4M5M61000010110000001100000014.OPOP={op1,op2,,opn},opi={opi1,opi2,,opik}pi5.OPop11op12op1kop21op22op2kopi1opi2opik6OPgad_filegaa_fileColumn_NameTable_NamePN(PK)Gad01charVer(PK)Gad01acharProcedur