工序间存在零等待约束的复杂产品调度研究

357Vol.35,No.720097ACTAAUTOMATICASINICAJuly,20091112,.,,,.,,.,,,,TP278StudyonComplexProductSchedulingProblemwithNo-waitConstraintbetweenOperationsXIEZhi-Qiang1LIZhi-Min1HAOShu-Zhen1TANGuang-Yu2AbstractForthecomplexproductschedulingproblemwithno-waitconstraintbetweenoperationsinpracticalassem-blingmanufacture,amethodtochangeoperationswithno-waitconstraintintoavirtualoperationisproposed.Basedontheconceptsofcomplexproduct,standardoperation,virtualoperation,no-waitandtheexpansionprocessingtreede¯nedinthispaper,thestandardoperationsareprocessedbyalliedcriticalpathmethod(ACPM)andbest¯tschedul-ingmethod(BFSM),andthevirtualoperationsareprocessedrespectivelyoncorrespondingmachinewithmovementandexchangealgorithminordertotranslateschedulingproblemwithno-waitoperationsintothegeneralschedulingproblemwithvirtualoperations.Theresultoftheexamplesshowsthattheschedulingalgorithmproposedisane®ectivesolutiontothecomplexproductschedulingproblemwithno-waitconstraintbetweenoperationsandcanbeeasilyrealized.KeywordsNo-waitconstraint,standardoperation,virtualoperation,movementandexchangealgorithm,complexproductschedulingNP-Hard[1],[2].,.,.,.,[3]2008-07-182009-01-07ReceivedJuly18,2008;inrevisedformJanuary7,2009(50575062,60873019),(F200608),(1152hq08)SupportedbyNationalNaturalScienceFoundationofChina(50575062,60873019),NaturalScienceFoundationofHei-longjiangProvince(F200608),andtheKeyProjectofScienti¯cResearchSubsidyofAbroadScholarsofHeilongjiangProvincialEducationDepartmentofChina(1152hq08)1.1500802.1500801.SchoolofComputerScienceandTechnology,HarbinUni-versityofScienceandTechnology,Harbin1500802.SchoolofMechanicalPowerEngineering,HarbinUniversityofScienceandTechnology,Harbin150080DOI:10.3724/SP.J.1004.2009.00983[4][5][6][7¡8].,,,.,,.,,[9],,,.,,[10¡13],.,[14](Alliedcriticalpathmethod,ACPM)(Best¯tschedulingmethod,BFSM),.984351,[9]:K,Jl,l=1;2;¢¢¢,K,N=Pkl=1Jl.M,;;,,;,;,;,;,.,,T=minfmaxftij1+tij2ggs:t:min(tij1);ti(j+1)1¸tij1+tij2i=1;2;¢¢¢;M;j=1;2;¢¢¢;Ntxy1¸max(tij1+tij2),ijxy.,tij1ij,tij2ij.,,[15],[16].,,,[17],,.,,,,.,,,,.,[18];,,,,,[19].,,.,,,,.,,:1().,,..2()..3().,,,,,.4().,,.5().,,.,,.A1=3=4,A13,4.,,..6().,,,,..,.,.[14],,,.,,.7:9852.,.,(ACPM)(BFSM);..1.pknn+1,p,(tk(n+1)1¡(tkn1+tkn2))¸tkp2,p,2;pkp,7.2.pqjnn+1,q,(tj(n+1)1¡(tjn1+tjn2))¸tjq2,kn+1tjs1!tj(s+1)1,q,3;qjq,6.3.ptkp1+tkp2qtjq1,8;4.4.ptkp1+tkp2qtjq1,kpp1tkp11qtjq1,P(,),Tqtjq1Ptkp1+tkp2,T=tjq1¡(tkp1+tkp2),8;5.5.ptkp1+tkp2qtjq1,:1)kPp1tkp11qtjq1;2)p1txy1,tkp11txy1;3)p,p12),Tqtjq1Ptkp1+tkp2,T=tjq1¡(tkp1+tkp2),8;,:1):AB.DE,C,DB,ABDE,,DB,DB,,DE.1.2):AB,CD,A,ABCD,CA,,CD.2.3):CAB,AC,A,,AB,AC.3.1AB,DEFig.1No-waitconstraintbetweenoperationsAandB,DandE2AB,CDFig.2No-waitconstraintbetweenoperationsAandB,CandD3ACFig.3No-waitconstraintbetweenoperationsAandC986356.1)qjnn+1,q,0(tj(n+1)1¡(tjn1+tjn2))tjq2;2)tj(n+1)1txy1,tj(n+1)1txy1;3)tj(n+1)12),tjq2¡(tj(n+1)1¡(tjn1+tjn2));4)jnn+1q,jn+1tjs1!tj(s+1)1,q,3.7.pkp,pk,2.8.qp,p1;¢¢¢;pm,pn;¢¢¢;pk,p1;¢¢¢;pm,pn;¢¢¢;pkp,11;9.9.qp,p1;¢¢¢;pm,pn;¢¢¢;pk,p1;¢¢¢;pmp,pn;¢¢¢;pkp,p,Tpn;¢¢¢;pkp,,,11;10.10.qp,p1;¢¢¢;pm,pn;¢¢¢;pk,p1;¢¢¢;pm,pn;¢¢¢;pkp,p,Tp,p1;¢¢¢;pm,pn;¢¢¢;pkp,,,11.11.qd,pq(pq2p),d(2q),2,.4.:n,m.n=2,n=4.1).n=4m,n=(4m),(n=(4m))£(n=m).n2=(4m).2),n2=(4m).3),,2,n=4,,(n=4)£2£(n=m)=n2=(2m).,n2=m,1·m¿n,,O(n2).O(n2)[14],O(n2).4Fig.4Flowchartofmovementandexchangealgorithm3AB,A5,B6.,A,,A2A6,A5A7,5AFig.5ProcessingtreeofproductA7:987B,,B1B3,B4B5,A,B.,AB,A7,B8.AB56,6BFig.6ProcessingtreeofproductB7AFig.7ExpansionprocessingtreeofproductA8BFig.8ExpansionprocessingtreeofproductBACPMBFSM[14]((ACPM)(BFSM).,,,,),9,44.AB78,ACPMBFSM,,10(),46.9,[14].10,,,,,,9ABFig.9GanttchartofproductsAandB9883510ABFig.10GanttchartofproductsAandBwithno-waitconstraint,,.,,.41),,.2),ACPMBFSM,.3),.References1GareyMR,JohnosonDS.ComputerandIntractability:AGuidetotheTheoryofNP-Completeness.SanFrancisco:Freeman,19792ZengLi-Ping,HuangWen-Qi.Alocalsearchmethodwithhybridneighborhoodforthejobshopschedulingproblem.ComputerScience,2005,32(5):177¡181(,..,2005,32(5):177¡181)3JinZhi-Yong,ZhouZu-De,HuYe-Fa.Studyonjob-shopschedulingsystembasedonmulti-agentsystem.MechanicalEngineeringandAutomation,2006,139(6):34¡36(,,..,2006,139(6):34¡36)4WuZhi-Jun,NingRu-Xin,WanChun-Hui,WangGuo-Xin.Researchandrealizationofdynamicjobshopschedulingproblembasedonhuman-computercollaborative.ComputerSystemsandApplications,2006,15(4):21¡24(,,,..,2006,15(4):21¡24)5LiuLin,GuHan-Yu,XiYu-Geng.Reschedulingalgorithmbasedonrollinghorizondecompositionforadynamicjobshopwithuncertainarrivingtime.ChineseJournalofMe-chanicalEngineering,2008,44(5):68¡75(,,..,2008,44(5):68¡75)6MascisA,PacciarelliD.Job-shopschedulingwithblockingandno-waitconstraints.EuropeanJournalofOperationalResearch,2002,143(3):498¡5177LiuB,WangL,JinYH.Ane®ectivehybridparticleswarmoptimizationforno-wait°owshopscheduling.TheInter-nationalJournalofAdvancedManufacturingTechnology,2007,31(9-10):1001¡10118PanQK,WangL,ZhaoBH.Animprovediteratedgreedyalgorithmfortheno-wait°owshopschedulingproblemwithmakespancriterion.TheInternationalJournalofAdvancedManufacturingTechnology,2008,38(7