流水车间成组作业调度的研究

上海交通大学硕士学位论文流水车间成组作业调度的研究姓名：邹先军申请学位级别：硕士专业：机械制造及其自动化指导教师：金烨2006010111GTGTGTGT22/////3RESEARCHONFLOWSHOPGROUPSCHEDULINGABSTRACTTheproblemofschedulinggroupjobsonmulti-machinesflowshopcomesfromthepracticalworkshopsandisanurgentproblemneedtoberesolved.Inthisdissertation,thepropertiesandmethodsforthetotalflowtimeandearliness/tardinesspenaltiesforschedulinggroupjobsonflowshopwithsetupsareinvestigated.Themainpurposeistofindeffectiveapproachesforpracticallargescaleschedulingproblems,Byanalyzingthecharactersinpracticalworkshops,wefindthattheproblemsareNP-hardproblemsandareverycomplicated.Uptonowthereisnopublishedliteraturesinwhicheffectivemethodcanbefoundtodealwiththem.Itshowsthatoptimalsolutionisindireneeds.Atfirst,thegeneralintroductionfortheproblemisrecommended,thenthemathematicalmodelsarepresented.Furthersomegeneticalgorithmaredesigned.Thesimulationexperimentshavevalidatedtheefficienciesofthealgorithms.Atlast,anoverallconclusionisdrawnandthedirectionsforfutureresearchareputforward.Insummary,thefollowingworksarereportedinthisdissertation:Forthemulti-machineflowshopgroupschedulingwiththeoptimalobjectiveofminimizationofthesumflowtime,firstly,thispaperpresent4amathematicsmodeling,thentheproblemisclassifiedintotwotypes.TotheproblemwithGTassumptionthisthesisdesignedtwomethodstosolvethiskindofproblem,ageneticalgorithmisdesignedbasedonthemathematicsmodeling.Toidentifiedthesolution,itwasappliedtoworkoutapracticalexampleofpipefactory.Andcomparedatastothepreviouspracticalresult,whichdemonstratetheefficiencyoftheproposedsolution.Inaddition,anotherhybridalgorithmwasgivenbasedontheheuristicmethodandgeneticalgorithm.Certainlyitisappliedtosolveapracticalexample.TotheproblemwithoutGTassumption,akindofgeneticalgorithmwiththecodemethodbasedonthesequenceofworkpiecesisdesigned.Fortheearliness/tardinesspenaltiesschedulinggroupjobsonflowshop,itwasdividedintothreetypesaccordingtothecharacteristicoftheduedate.Fortheknowncommonduedateproblem,Ifirstlycreateamathematicsmodelingwithoptimalobjectiveearliness/tardiness,thendesignedageneticalgorithmsuitedtothistypeofproblemwhichincludethegroupinformationwithsub-code,astheduedateisknownbutdifferent,wepresentthemathematicsmodelingwiththegoaltogottheoptimalduedatewhentheE/Tindicatorislowest.Whentheduedateofdifferentgroupsisdifferent,effectivecodinganddecodingmethodindesigningthecorrespondinggeneticalgorithmisgiven.Inrefertothelastproblem,infact,Itisproblemwithtwogoals,asequenceofjobsanddue5dates(maybecommonduedate)shouldacquireintheconditiontheE/Tindicatorisminimization.Finallyasolutionispresented.Inthispartallgeneticalgorithmsareappliedtosolvepracticalexamples,thedataworkedoutarecollectedandcomparedtothedataoftheproduction,thedesignedsolutionshaveahighlevelimprovement,whichshowsthesolutionsareeffectivetosolvethistypeofproblem.Undoubtedly,asamodernnovelresearchfield,itisexpectedthefurtherstudyonthetheoryofoptimizingproductionschedulingwithgroupingjobonmulti-machineflowshopinbothdepthandscope.Keywords:productionscheduling,groupscheduling,flowshop,flowtime,E/T200502151200602152006021511.1.[1]20901.2.21,,,,,,21,WTO,,,;,863/CIMS,(ContemporaryIntegratedManufacturingSystems,CIMS)[2]CIMS,Wild:[3][4]CIMCIMCIMSCIMS[3]21.2.1..CIMS(MRP)(MRPII)(PERT),CIMS.:(1);(2),,()1.2.2.CIMS.CIMS,CIMSCIMS.CIMSCIMSCIMS3CIMS1.3.scheduling[5]FMS”PlanningFlow-shopFMS[3]CIMSNCCNCNP-41.3.1.openshopclosedshopflow-shopjob-shop1.3.1.11.3.1.2?61.3.1.3Flowshop.nm:M1M2……Mm(nm)0n1.3.1.4Jobshop5Job-shopJob-shopnm)flow-shopjob-shopJob-shop:1);2);3):4);5)1.3.2.α/β/γA/B/C/D,A1B1CFDn/3/F/Fmaxn3α/β/γ,αβγ[6]1.3.2.1αα1α2α2α2α2kα2=0α1{O,P,Q,R,PMPM,QMPM,G,X,O,J,F},Oα1Oαα2α1{O,P,Q,R,PMPM,QMPM}α1¾α1O,¾α1{P,Q,R},{M1,M2,…Mm}α1PidenticalparallelmachinesMjpij=pi;α1=Q(uniformparallelmachines)pij=pi/sj,sjMjα1=R(unrelatedparallelmachines)pij=pi/sij,sijMj¾α1PMPMQMPM6¾α1{G,X,O,J,F},µijOijµij⊆{M1,M2,…,Mm}generalshopα1=GJobshopα1JOi1→Oi2→…→iinO,i=1,…,n,1niiT=∑≠,1ijµ+j=1,…,ni-1ijµ≠,1ijµ+Jobshop(Jobshoprepetition)Jobshop4β2in≤,Flowshop,1αFJobShopi=1,2,…,ni=1,2,…,mni=m,ijµ∈{Mj}FlowshoppermutationFlowshopFlowshopOpenshop,1αOFlowshopJobshopMixedShop,1αX1.3.2.2Jinioperation{Oi,1…,Oi,n1.},OijPijni1JiOi,1PiJi1setuptimeirOi,jµij⊆{M1,M2,…,Mm}Oijijµijµdedicatedmachine,parallelmachinemulti-processortaskschedulingJitJi()iftduedateidweightiwfeasibleoptimal123456{,,,,,}βββββββ=7¾1βpreemptionNon-preemption1βpmtn,β1β¾2βprecedencerelationG=(V,A)V={1,2,…,n}(,)ikA∈,JiJkG2βprecGtree2βtreeGchain2βchainGseries-parallel2βsp-graphβ2β¾3β0ir≠3βir;ir0β3β¾4β4βip=1(ijp=1)114β¾5β5βidβ5β¾6β6βp-batch6βs-batchβ6βP/prec;pi=1/Cmax801.3.3.1.3.3.1n-1!/2n-1!/21n201929PNPNPnTSPT(n)S(n)()p(n),O(p(n))()(())ATnOpn=p(n)nA1.3.3.2P,NP,NP-C,NP-hardPPNPNP123g(x)HAISId(S)g(d(I))d(I)ISIg(d(I))ANPNP9P⊂NP4A1A2A1A2g(x)A1I1g(d(I1))A2I2g(d(I1))I1I2d1I1d1I25A1A2A1A2g1(x)g2(x)A1IA2g1(d(I)),A2H2,A1H1H1H21221(())(((())))HHfdIgfgdI≤A2A1A1A2A2H2A11A1I1,g1(d(I1))A22H2I2211((()))HfgdINP-hardNP-CA∈NP-C(NP-Complete),A∈NPNPA,ANP-hard,NP-C⊂NP-hardNP-CNP111.4.10WilbrechtPrescott,Flunnkrajewski1.4.1.GTGroupTechnology501.4.1