一种求解工程调度中资源水平问题的遗传算法

200144:100026788(2001)0420024203,(,110006):,LL,RLPL:;;;:O224:AaAGeneticAlgorithmforResourceLevelingProbleminProjectSchedulingLIUShi2xin,WANGMeng2guang(SchoolofInformationScienceandEngineering,NortheasternUniversity,Shenyang110006,China)AbstractWedevelopageneticalgorithmforresourcelevellingprobleminprojectschedulingbasedontheproblemcharacteristicsanddescribethecodescheme,geneticoperatorandalgorithmstructure.Bycomputationalstudyforastandardsetofprojectinstanceswhichhasbeenwidelyused,weshowthatthegeneticalgorithmiseffectiveforresourcelevelingproblem.Keywordsprojectscheduling;resourcelevelling;GA1(RLP),LRLPL,,[1-3][4,5]L,[6]RCPSP[7],[8],,L,L2(RLP):,JL,,ji,iPj(Pjj)L,,L1,J,(0),LTv,jkrjk,djLkck,Rk,k=1,,KLjSj,At[t-1,t)a:1999209206©1995-2004TsinghuaTongfangOpticalDiscCo.,Ltd.Allrightsreserved.,RLP:min6Kk=1ckRmaxk(1)s.t.Sj-SiEdi,iPj(2)SJFTv(3)6jAtrjkFRkt=0,1,,Tv;k=1,2,,K(4)(1),,Rmaxk=maxt=0,1,,Tv-16jAtrjkk;(2);(3);(4),L(1)-(4),AtL,LL3RLP311PopSizePOP0,POP0,PopSize,POP0,2PopSizeL,PopSzieLGEN,:RLP:PopSizePmGEN;POP0;k=0;WHILEkGENDOPOPk,POPk;POPk,POPk;POPkPOPk;POPkPOPkPopSizePOPk+1;k=k+1;ENDWHILE;POPGEN;312{jI1,jI2,,jIJ},{jI1,jI2,,jIJ}={1,2,,J}PjiIA{j1I,j2I,,ji-1I}L[9]LTv,(),LC,M,:f(s)=6Kk=1ckRmaxk+Mmax{0,C-Tv}SRD[9]L:,MF,p1,p2,1p1p2J,MFp1,p2DSLD,p1M,524©1995-2004TsinghuaTongfangOpticalDiscCo.,Ltd.Allrightsreserved.jDi:=jMi,i=1,2,,p1i=p1+1,,p2F,F,jDi:=jFk,i=p1+1,,p2,k=min{kûjFk|{jD1,,jDi-1},k=1,2,,J}i=p2+1,,JM,M,jDi:=jMk,i=p2+1,,J;k=min{kûjMk|{jD1,,jDi-1},k=1,2,,J}SD,,jSi:=jFi,i=1,2,,p1jSi:=jMk,i=p1+1,,p2,k=min{kûjMk|{jS1,,jSi-1},k=1,2,,J}jSi:=jFk,i=p2+1,,J,k=min{kûjFk|{jS1,,jSi-1},k=1,2,,J}Hartmann[10]LPm,:i=2,3,,J-1,PmjIijIi+1,,L43Java,Windows98Pentium133ö32MIBML:PopSize=40,50,60Pm=0.05PopSize,GEN=50,40,35LKolisch[11]ProGen,[12]InternetPSPLIB(http:öö)L,PSPLIB3060()480,4,[1,10]LTv1.5L,PopSizeGENL1,2,3,4,5L1:J=32CPU()40502.2%97%7.950404.0%100%8.160354.7%99%8.82:J=62CPU()40503.5%95%10.850404.6%99%11.460355.7%98%12.612,PopSizeGEN6,PopSize=50GEN=40,13L5RLP,,L,RLPL:1),;2)RLP;3),RLPL(105)6220014©1995-2004TsinghuaTongfangOpticalDiscCo.,Ltd.Allrightsreserved.,,,,,Z,Z:[1],.[J].:,1997.[2],.[J].:.1997.[3],,,.[J]..1998,18(3):47-51.[5].[M].:,1997.(26):[1]MohringRH.Minimizingcostsofresourcerequirementsinprojectnetworkssubjecttoafixedcompletiontime[J].OperationsResearch,1984,32:89-120.[2]BandelloniM,TucciM,RinaldiR.Optimalresourcelevellingusingnon2serialdynamicprogramming[J].EuropeanJournalofOperationalResearch,1994,78:162-177.[3]YounisMA,SaadB.Optimalresourcelevellingofmulti2resourceprojects[J].ComputersandIndustrialEngineering,1996,31:1-4.[4]LeachmanRC.Multipleresourcelevellinginconstructionsystemsthroughvariationofactivityintensities[J].NavalResearchLogisticsQuarterly,1983,30:187-198.[5]SeibertJE,EvansGW.Time2constrainedresourcelevelling[J].JournalofConstructionEngineeringandManagement,1991,117:503-520.[6]DemeulemeesterE.Minimizingresourceavailabilitycostsintime2limitedprojectnetworks[J].ManagementScience,1995,41(10):1590-1598.[7]DemeulemeesterE,HerroelenW.Abranch2and2boundprocedureforthemultipleresource2constrainedprojectschedulingproblem[J].ManagementScience,1992,38(12):1803-1818.[8]NeumannK,ZimmermannJ.Resourcelevellingforprojectswithschedule2dependenttimewindows[J].EuropeanJournalofOperationalResearch,1999,117:591-605.[9]KolischR.Serialandparallelresource2constrainedprojectschedulingmethodsrevisited:theoryandcomputation[J].EuropeanJournalofOperationalResearch,1996,90:320-333.[10]HartmannS.Acompetitivegeneticalgorithmforresource2constrainedprojectscheduling[J].NavalResearchLogistics,1998,45:733-750.[11]KolischR,SprecherA,DrexlA.Characterizationandgenerationofageneralclassofresource2constrainedprojectschedulingproblem[J].ManagementScience,1995,41(10):1693-1703.[12]KolischR,SprecherA.PSPLIBAprojectschedulingproblemlibrary[J].EuropeanJournaloftheOperationalResearch,1996,96:205-216.5014©1995-2004TsinghuaTongfangOpticalDiscCo.,Ltd.Allrightsreserved.