搜索
20108284JournalofNorthwesternPolytechnicalUniversityAug.Vo.l282010No.4:20090613:(1972-),,李俊亭,王润孝,杨云涛(,710072):关键链项目进度管理既考虑了CPM/PERT技术,又考虑了资源受限下项目调度问题,但把两者结合起来,研究项目进度优化和理论上完整的项目网络表示,目前还存在研究不足文章以资源受限下项目调度方法的平行法,加入资源强度优先调度原则,首先提出了关键链项目资源多任务调度算法;其次在项目网络中引入开始开始搭接关系来表示资源冲突引起的活动时间滞后,形成完整的关键链项目网络表示,并给出了基于此表示的关键链识别算法;最后以一个实例验证了该解决方案的有效性,表明了该算法对2种约束限制下具有2种搭接关系关键链项目网络表示的合理性:CCPM,进度优化,RCPSP,关键链项目网络:C935:A:10002758(2010)04054706(CriticalChainProjectManagemen,tCCPM)CPM/PERT[1]CCPM,(),[2,4,5],CCPMCPM/PERT(ResourceconstraintProjectSchedulingProblem,RCPSP),RCPSP,NPHard[5]RCPSPCCPM[6]RCPSP,,,;RSPSP,CPM/PERT2CCPM,[7],,1,RCPSP,,,,RCPSP(),,(),,,,1,,,,,,minTp(1)s..tSSTj-SSTidii,j!Ap;i=1,∀,N-1;j=2,∀,N(2)Rt#k=t∃j!AtR%jk=t∃j!AtRjk/dj=∃j!AtRjk&Rt#Kk!R,t∋0(3)28,(1),(2);(3)tk,,,i,j;SSTii;N;djj;Rjkjk;Rt#ktk,Rt#k=t∃j!AtR%jk;R%jkjk;Rt#Kt;Att2,RK(X),K(,,),Rk(X),k=1,∀,Kk,,21,,12(),cegk,t,,At={c,e,g},kRk(X),ceg:1(1),1m,(Pmm),,,[8]:,,,,3,m&3,,2,,,,2:(;)()2,,2(2)(,,),(),2Rk(X)∋max{Rx(x1),∀,Rk(xm)},m,1Rk(x1),(RemainingResource)RRk(x)=Rk(X)-Rk(x1),,2,Rk(x2)&RRk(x),2;Rk(x2)RRk(x),EF(1)(),EF(j)(j=2,∀,m)EF(1)(),,,(2),,,,,,,∗548∗4:1:,:step1:initES+Min{ES(i),ES(j),∀ES(m)};step21initES(i);step32mfor(m=2;m&M;m++){t=initES(i);while(t&)ifRk(xm)RRk(xk)thent=t+1;elseES(m)=t;break;}step4ES(m);,(),CPM/PERT,23,22,2:(1);(2),,(),;,,,,2,,,,;,,,2:,:step1:initES+Min{ES(i),ES(j),∀ES(m)};initEF+Max{ES(i),ES(j),∀ES(m)};fmax(R)=fi(R);t=initES;//f(R)step2while(t&initEF){for(m=2;m&M;m++){if(fm(R),0)thenf(R)=f(R)+fm(R);if(fmax(R)&f(R))thenfmax(R)=f(R);}t=t+1;}step3fmax(R);2,Rk(X),R=fmax(R)Rk(X)(4),0&R&1,;R1,;R,,,,:(1),[7],3abc,abR1,b2R1R2,cR2,b,(2),,,,,,,,,,(23),∗549∗28,,,,23,2,FSSS,FS(FS==0);SS,2:(,0;),0[8,9]rcf,rcf=0,,2,,,3:G=(A,E);A={ai|ai!StructObject};E={(ai,aj)|ai,aj!A};:Bstep1:G;ES[0∀Gn-1];step2TopOderStack(q),0,Fori=0toiGnES[k]+Max{ES[j]+djk};step3,:While(iGnandtag=0orrepeat=1)//tag=0;//repeat=1Forj=1toj=K{aij;j};ai,QueueR(r);While(!Empty-QueueR(r)){,;(FS)E,SS;ES[k];//,,QueueA(a)While(!Empty-QueueA(a)){,;(FS)E,SS;ES[k];};Repeat=1;Break;}step4While(!Empty-TopOderStack(q)){LS[k]+Min{LS[j]-dkj};IfSSkm,0thenLS[K]+Min{LS[m]+SSkm,LS[K]};}step5Fori=0toiGnIfPai∀next,NULLandrcfi=0thenPrint(ai);//ai32,6,R1(X1)=40,R4(X4)=20R5(X5)=20,R2,R3R6,R1(x)1,47,R4(x)R5(x)5,68,2,,;,;,1R1(x)∗550∗4:,2R4(x)R5(x)1NoESLSrcfSS1000SS14=40203030304040440400SS14=27/SS47=05406020660600760903087090209707001011011003,(FS),SS,,0,,0156910(120),32()NoESLSrcfSS1000SS14=402030303040404405010SS14=40/SS47=20540400SS56=30670700SS56=30/SS68=1076010040SS47=2088010020SS68=10980800101201200,RCPSP,,;34,,,,,;,,,,∗551∗28:[1]GoldrattEM.CriticalChain.GreatBarrington,Mass,USA:TheNorthRiverPressPublishingCorporation,1997[2]GrahamK.Rand.CriticalChain:theTheoryofConstraintsAppliedtoProjectManagement.InternationalJournalofProjectManagement,2000,18:173~177[3]BlazewiczJ,LenstraJK,RinnooyKanAHG.SchedulingSubjecttoResourceConstraints:ClassificationandComplexity.DiscreteAppliedMathematics,1983,5:11~24[4]HerroelenWS,LeusR.OntheMeritsandPitfallsofCriticalChainScheduling.JournalofOperationManagement,200119(5):559~577[5]ZwikaelO,CohenY,SadehA.NonDaySchedulingasaManagerialApproachforManagingProjects.InternationalJournalProjectManagement,2006,24(4):330~336[6]HaroldKerzner.ProjectManagement:ASystemsApproachtoPlanningScheduling,andControlling.WileyPublishing,Inc,2005[7],,..:,2007,4MaGuofeng,YouJianxin,DuXueme.iProjectSchedulingManagementBasedonTOC.Beijing,TsinghuaUniversityPress,2007,4(inChinese)[8]BowersJA.CriticalityinResourceConstrainedNetworks.JournaloftheOperationalResearchSociety,1995,46:80~91[9]..:,2006,10LiuShixin.ProjectSchedulingtheoryandMethods.Beijing:ChinaMachinePress,2006,10(inChinese)ANewCCPM(CriticalChainProjectManagement)SchedulingAlgorithmBasedonResourceConflictSolutionLiJunting,WangRunxiao,YangYuntao(NorthwesternPolytechnicalUniversity,Xi%an710072,China)Abstract:CCPMschedulingnotonlyappliesCPM/PERTtechnology,butalsotakesRCPSP(resourceconstraintprojectschedulingproblem)intoaccoun.tButhowtointegratebothtechnologiesandoptimizeprojectschedulingandtheoreticallypresentprojectnetworkrepresentation,theresearchisnotenoughatpresen.tSections1and2ofthefullpaperexplainournewalgorithm.Subsection21explainsournewschedulingalgorithmforthecaseofsingleresourceandmultiactivities;subsection22explainsournewschedulingalgorithmforthecaseofmultiresourcesandmultiactivities.Subsection23putsforwardacriticalchainpathidentifyingalgorithm;itscoreisthatweproposeawholecriticalchainprojectrepresentationwhichaddsrelationshipsofStarttoStart(SS).Section3givesanexampletoillustratethesolvingprocessesofourapproach.TheresultsoftheexampleandtheiranalysisindicatethatthenewcriticalchainprojectnetworkwithtwoactivityrelationshipsofFS(FinishtoStart)andSSundertwoconstraintsisreasonable.Keywords:scheduling,CCPM(criticalchainprojectmanagement),schedulingoptimization,RCPSP(resourceconstraintprojectschedulingproblem),criticalchainprojectnetwork∗552∗