具有無等待、阻塞或可搶占約束的調(diào)度優(yōu)化方法.pdf

1、東南大學(xué)博士學(xué)位論文具有無等待、阻塞或可搶占約束的調(diào)度優(yōu)化方法姓名：朱潔申請學(xué)位級別：博士專業(yè)：計算機應(yīng)用技術(shù)指導(dǎo)教師：李小平20110919AbstractAbstractResourceconstrainedProjectSchedulingisacombinationaloptimizationproblemwithbotllprocessingroutineaJldresourcesconstraints，wllichiswid

2、espreadinrealindustrialapplicationsa11d“isNP也ardi11strongsenseMacllineSchedulillgproblemisaspecificprojectschedulingpmblemwithoutresourceconstraintsh1t11ethesis，mal(espaIlisIIliIliIIlizedfor似omacllinescheduIingproblemsaI

3、ldaspecificprojectschedulingoneAgeneralframeworkisadoptedfortheconsideredproblemsbydecomposingeachoft11鋤into附osubprobl鋤s：(1)Sequencillg，whichsearchesanoptimalschedulethegiVenpmblem，aIld(2)tiIIletabling，wtlichfindsfeasibl

4、estantimesofmejobsfortheobtainedschedulewitllmakespanmillimizationThem萄orcontributionsoft11isthesisareshownbelow(1)Af瓠t鏟eedysearchisdeVelopedfortlle細’omachiIleno—waitjobshopproblemPropertiesoftheproblemareanalyzedAdiVide

5、andconquermemodisintroducedfortIletimetablingproblemAschedulecanbeobtainedinpolynomialtime，wllichcanbeimpmvedbymewell一knownGilmore&GomoUtoobtainabetterschedule(2)TwocompletelocalsearchalgorithmswithlimitedmemoDrareemploy

6、edfornowaitjobshopproblemswithmakespanIIlillimizatjon—CLLMaIldMCLMMCLMis孤e11llancedVersionofCLLMAslliRtimdablingmemodisdeVelopediIlCLLMh1MCLM，mepropeniesoftheproblemareanalyzedaccordingto“schaLracteristicsTheproblemisrer

7、nodeledbasedontheintroducedtimedi腩renceandashiRpenal妙basedtimetablingmethodisintroducediIlMCUⅥBothalgoritllmsapplythecompletelocalsearchalgorithmswithlimitedmemoryforthesequencingproblemTheexperimentalresultsshowtllatane

8、fl’ectivetimetablingmethodisex仃emelyirllponantfortheperfonnanceofthewholealgorithm(3)Alocalsearchisintroducedformeblockingjobshopprobl哪Accordingtomecharacteristicsoftheconsideredproblem，aconflictresolVings仃ategyispresent

9、edandusedbymeproposedtimetablingmethodtogenerateafeasibleschemlleThecompIetelocalsearchwithlimitedmemo巧isadoptedbytllesequencingsub—problem(4)GeneticalgoritlmlsaredesignedforthepreemptiVeresourceconsnailledprojectSchedul

10、ingproblemCaseswimnonint咖ptio瑪oneinterrup60n妣dlinlitedmmlberofiIltemlptionsarecollsideredFormenon血efruptioncase，acompletelocalsearchisdeVelopedFortheotller觚ocaSes，觚ogeneticalgorithmsarereSpectiVelypresentedSimulatiIlgexp