84 19 MPSP. zationconflictresolutionmulti-atributedecisionmaking 0 Keywords:resource-constrainedmulti-projectschedulingproblemmulti-objectiveoptimizat

Size: px

Start display at page:

Download "84 19 MPSP. zationconflictresolutionmulti-atributedecisionmaking 0 Keywords:resource-constrainedmulti-projectschedulingproblemmulti-objectiveoptimizat"

既卫
5 years ago
Views:

1 19 1 计算机集成制造系统 Vol.19No ComputerIntegrated ManufacturingSystems Jan.2013 : (2013) ( ) : : :TH166 :A Decompositionalgorithmforresource-constrainedmulti-projectschedulingproblem WANG Jun-qiang 12 ZHANG Song-fei 12 CHEN Jian 12 ZHANG Ying-feng 12 SUN Shu-dong 12 (1.InstituteofSystemIntegrated & Engineering Management NorthwesternPolytechnicalUniversityXi an710072china 2.KeyLaboratoryofContemporaryDesignandIntegrated ManufacturingTechnology MinistryofEducationNorthwesternPolytechnicalUniversityXi an710072china) Abstract:Inordertoaddressthemulti-objectiveoptimizationofresource-constrainedmulti-projectschedulingprob- lem (RCMPSP)atwo-stagedecompositionalgorithmbasedonhierarchicaldecomposingstrategywasproposedto orderlytackletheirprecedenceconstraintsandresourceconstraintsinanintegratedframework.furthermorethe solvingprocedureofrcmpspwaspresentedstructuredbytwostages.inthefirststageofprecedenceconstraints satisfactoryoptimizationstagearevisedantcolonyoptimization(aco)waspresentedtoobtainthefeasibleactivity sequence.inordertoacceleratetheconvergenceeficiencyandqualityarevisedpheromoneincrementupdatingop- eratorofaco withcombinationofparalelschedulegenerationscheme(psgs)wereused.duringtheprocesscon- structingfeasibleprecedenceactivitysequenceasequencingindicatorwaspresentedtosolvetheconstraintconflict resolutionproblem whensomeparalelactivitiescompetedsomeresourcessimultaneously.specificalythetopsis basedonentropyweightandmulti-atributedecisionmakingbasedonorderedweightedaveraging(owa)operator wasusedtoobtaintheintegratedimportancemeasureofactivityastheindicator.atthesecondstageofresource- constraintssatisfactoryoptimizationstagetheobtainedoptimum precedenceactivitysequence wastakenasthe stage sinputandtheresourcecapacitywasexaminedandadjustedonebyoneuntiltheoptimalschedulingsolution wasobtained.theresultsilustratedtheefectivenessoftheproposedtwo-stagedecompositionalgorithmforrc- : : Received16July2012accepted17Nov : ( ) (JC ) Foundationitems:Project supportedbythe NationalNaturalScienceFoundationChina(No )andtheBasicResearch Foundationof NorthwesternPolytechnicalUniversityChina(No.JC ).

2 84 19 MPSP. zationconflictresolutionmulti-atributedecisionmaking 0 Keywords:resource-constrainedmulti-projectschedulingproblemmulti-objectiveoptimizationantcolonyoptimi- (Resource-Con- strained Multi-projectSchedulingProblemRCMP- SP) [12] RCMPSP [13] NP-hard [1-3] [4] RCMPSP [5-7] [8-12] [11] / / RCMPSP (1) RCMPSP (3) PSPLIB [5-6] [7] [14] [8] (ConstraintProgrammingCP) [15] RCMPSP PSPLIB J30 30 (Ge- neticalgorithmga) [16] (2) X-pass [9] [17] 9 RCMPSP [10] Browning Yassine(2010) [18] 20

3 1 : 85 1 [19] [4] RCMPSP : Pareto [20] (AntColony OptimizationACO) [21] (Filter-and-FanF&F) (Iterated LocalSearchILS) / RCPSP :1 2 RCMPSP : (1) 单目标转换法 (Multi-ObjectiveResource-Constrained Multi-Pro- jectscheduling ProblemMORCMPSP) [410] : I K (2)Pareto 求解法 max Pareto (e ik max{d i -c i 0}- i=1 k=1 w ik max{c i -d i 0}) (1) n min FT iji (2) i=1 ρ s.t. [3-4] i At r ijkρ R k j At t=12 C iji k =12 K (3) ST ij RCMPSP Pareto max(ft iv )i=12 I jv =12 J i (iv) PRE (ij) (4) ST RCPSP ij 0i=12 Ij=12 J i (5) :i I j J RCMPSP i i k K t C iji i RCMP- SP e ik i k w ik i k (TheoryofCon- ρ r ijk (ij) k A t straintstoc) t A t = {j j = 1 JST ij t ST ρ ij+pij i=12 I}R k k ST ij (ij) FT ij (ij) FT ij =ST ij +pij pij (ij) FT iji i PRE(i

4 86 19 j) (ij) (1) (2) (3) (4) (5) i k (R ik ) ( 2 I K max i=1 k=1 n max{c i -d i 0}) min FT iji i=1 RCMPSP Pareto e ik w ik ) 1 1 ξ ik = Rik K i Ik K R ik k=1 ξ ik i k k K 2 ERM i = e ikξ ik(i k=1 Ik K) LRM i = K w ikξ ik(i Ik K) k=1 [216] i L i L i (ij- 1) PRE(ij) (ij-1) L i (ij) L i (TechniqueforOrderPreferencebySimilaritytoI- dealsolutiontopsis) OWA (Multi-AtributeDecision MakingMADM) RCMPSP 蚁群算法设计 (e ik max{d i -c i 0}-w ik RCMPSP

5 1 : 87 RCMPSP 1 1 ( ) ( ) i j (ij) (1) 蚁群移动规则 pij k ( t) : 烄 p k ij ( t)= [τij ( t)] α [ η ij ( t)] β [τij ( t)] α [ η ( j alowed k ij t)] β j alowed k 烅烆 0 (ij) η ( ij t) (ij) i j (6) :p ij k ( t) t i k j alowed k k alowed k = {01 n -1}-tabu k k tabu k tabu k k α(α>0) (ij) β ( β >0) (ij) τij ( t) t (ij) τij ( 0)

6 88 19 : η ( jk)= max π D(j) LFπ -LFk +1 (7) PSGS [101623] :LF π π D(j) SSGS j PSGS SSGS (2) 信息素更新规则 PSGS SSGS PSGS PSGS J τij ( t+1) : g t g :1 (completeset) C g τij ( t+1)=ρτij ( t)+δτij ( t) ρ ( 01) m ( Δτij t)= Δτ ij t) (8) (decisionset) D g PSGS k=1 [410] : ρ (ij) : 1-ρ Δτ ij k ( t) 1 k t (ij) t=0 Δτij 0)= 0Δτij 2 t) (ij) Δτij ( t) [22] ρ πr αi β kg 2 i φ i PSGS : 2 (activeset) A g 3 :g =1t g =0D g ={11}ST11 =0A11 ={11} Q Δτ ij k ( 烄 (ij) π* C ρ g = πrkg =Rk ρ r ρ R ρ t)= 烅 φ i (9) WHILE A g C g <JDOStageg 烆 0 /***Step1***/ :Q t g =min{stij+pij (ij) An-1} π * A g =A g-1\{(ij) (ij) A g-1 STij+pij=tn} φ i i φ i = w i+ (1- C g =C g-1\{(ij) (ij) A g-1 STij+pij=tn} COMPUTE D g w) ζi i i i = LRMi t i ζ i /***Step2***/ DO i ζ i = ERMi w t /***accordingtosomepriorityrules***/ i select (i 0 w 1 * j * )from D g STi w * j * =tn A g=a g {(i * j * )} w UpdateπRkg ρ r ρ Rk ρ andd g 并联进度生成机制 WHILE D g g =g+1 (Schedule Generation SchemeSGS) [1016] END SGS (SerialScheduleGenera 资源冲突消解 tionschemessgs) (Paralel ScheduleGenerationSchemePSGS) PSGS

7 1 : 89 Z + 烄 = max (fij ) j j * 烅 min(fij 烆 ) j j Z - 烄 = min (fij ) j j * 烅 max(fij 烆 ) j j j=12 n j * j (8) m Si + = (fij -f +) 2 j j=12 n 槡 i=1 : m Si - = (fij -f -) 2 j j=12 n 槡 i=1 : :f + f - S i + S i - 1 TOPSIS [24] pri(pi) (9) C i=s i - /(S i + +S i - )i=12 m 0 C i 1 : (10) (1) A pri(p1 a 11 a 12 烄 a 1n 烌 p2 pm) a 21 a 22 a 2n A = 2 OWA [25] pri(a j ) a m1 a m2 烆 amn 烎 m =12 Mn =12 N : (2) A (1) a 11 a 12 烄 a 1n n 烌 a 21 a 22 a MADMOWA w 2n (α1α2 αn)= ωjb j A = j=1 ω OWA ωj [ 0 a m1 a m2 烆 a m a ij =a / ij a 槡 ij i=1 (3) 2 mn 烎 (2) pri(a 1 a 2 a n ) 3 (4) u j ( ) E j =- lnm 1 m ( ) a ij lna ij j N i=1 a ij =0 a ij lna ij =0 (5) n 1]j N ωj =1b j (α1α2 αn) j j=1 Multi Pri(x ij ) Multi Pri(x ij )=pri(pi) pri(a j ) n ω = (ω1ω2 ωn)ωj =1-E / i=12 m j=12 n j (1-E k ) k=1 0 pri(pi) 10 pri(a j (6) 时序约束优化算法伪代码 F = (fij ) m n = (ωj a ij ) m n i Mj N (7) : : NC max m

8 90 19 α β ρ Q WHILE NC<NC maxdo FORk=1tomantsDO η ( jk)= max π D h (j) LFπ-LFk+1 FORg=1toJDO sort(lij j) PSGS (6) BREAK D g END D g END IF D g (aij aij+1 aij+n) break ELSE TOPSIS pri(pi) benchmark [42026] OWA [4] :1 2 pri(a j ) (a j ) Multi ) Pri(xij =pri(pi) pri Multi ) Paterson benchmark Pri(xij Paterson END 110 benchmark C g (8) ENDFOR Δτ ij k( t) (9) NC IFf(x) NC-1<f(x) NC THEN ENDIF ENDFOR NC=NC+1 END WHILE WindowsXP Intel(R)coreTM(2)CPU1.63GHz 512 MB MATLAB7.0 5 Pareto 3 Pareto : L * =(l1l2 lh)h S FORi=1toh sort(lij j) ELSE t=t+1 untilt [1119] R 1 R 2 R 3 2 (Ⅱ) : IF li

9 1 : 91 2 (Ⅰ) 2 ID R1 R2 R3 b b a a a a a a a a a a a a a b b b b b b b b b b b b

10 b b b b b b b b c c c c c c c c c c c c ~ 8 [27] (T) (R) (P) T-R-P 3 1 (Ⅱ) 2 3 R1 R2 R3 R1 R2 R3 R1 R2 R / 5 ξ i1 ξ i2 ξ i3 ERMi LRMi (NC max ) (m ) (α) ( β ) ( ρ ) (Q ) (Ⅰ) (Ⅱ)

11 1 : 93 8 (Ⅲ) ~ 9 R 1 R 2 R 3 69d A 2d 9 R 3 B 1d C 2d

94 19 processtime) LFT(lastfinishtime) SASP(shor- 46 testactivityfromshortedproject) 3.3 11 3(J 3 =12) 2(J 2 =22) 11 m =6 5 203050 9 10 9 65 69 63 69-46 3 GA 69 69 62 69-1732 /% /% /% /s 20 0.37 13.

12 94 19 processtime) LFT(lastfinishtime) SASP(shor- 46 testactivityfromshortedproject) (J 3 =12) 2(J 2 =22) 11 m = GA /% /% /% /s GA [28] /% /% /% /s : (1) 3(J 3=12) % % 3(J 3= 12) 2(J 2=22) [28] SPT(shorest SPT LFT SASP NC max GA (2) 2(J 2=22) 50 CPU 4 20s (3) PCMPSP /% /% /% /s GA GA GA GA

13 1 : 95 agementscience200046(10): Pareto : (1) ManagementScience200349(3): (2) (3) ] TOPSIS OWA MADM (4) RCMPSP 126(2): GASPTLFT SASP : [1] BRUCKER PDREXL AM HRING Retal.Resource- constrainedprojectscheduling:notationclassificationmod- elsand methods[j].europeanjournalof OperationalRe- search (1):3-41. [2] LIUShixin.Projectschedulingtheoryand methods[m].bei- jing:chinamachinepress2007 (inchinese).[. [M]. : 2007.] [3] FANG ChenWANG Ling.Surveyonresource-constrained projectscheduling[j].controlanddecision201025(5):641- [6] PENG WuliangWANG Cheng en.a multi-moderesource- constraineddtctp[j].journalofnortheastern University: NaturalScience200829(8): (inchinese).[. [J]. : (8): ] [7] M HRING R HSCHULZ A SSTORK Fetal.Solving projectschedulingproblemsbyminimumcutcomputations[j]. [8] LIU ShixinSONGJianhai.Combinationofconstraintpro- gramming and mathematical programming for solving re- sources-constrainedproject-schedulingproblems[j].control Theory & Applications201128(8): (inChinese). [. / [J] (8): ence198228(2): [10] BROWNING T RYASSINE A A.Resource-constrained multi-projectscheduling:priorityruleperformancerevisited [J].InternationalJournalofProduction Economics2010 [9] KURTULUSIDAVISE W.Multi-projectscheduling:cate- gorizationofheuristicrulesperformance[j].managementsci- [11] LOVA ATORMOSP.Analysisofschedulingschemesand heuristicrulesperformanceinresourceconstrainedmulti-pro- jectscheduling[j].annalsofoperationsresearch (1/2/3/4): [12] LIANG YanJIN Ye.Heuristicalgorithmforresourcelevel- ingprobleminemergencyscheduling[j].computerintegrated ManufacturingSystems200915(6): (in Chi- nese).[. [J] (6): ] [13] XU CijunLIAipingLIU Xuemei.Multi-projectscheduling algorithmbasedonresourcepush-pultechnology [J].Com- puterintegrated ManufacturingSystems201016(6): (inchinese).[. [J] (6): ] [14] ELLOUMISFORTEMPSP.A hybridrank-basedevolu- tionaryalgorithmappliedtomulti-moderesource-constrained projectschedulingproblem[j].europeanjournalofopera- 650 (inchinese).[. tionalresearch (1): [J] (5): ] [15] TASANSOGEN M.Anintegratedselectionandschedu- [4] SHOU Yongyi.Resource-constrainedmulti-projectscheduling lingfordisjunctivenetworkproblems[j].computers & In- modelsand methods[m ]. Hangzhou:Zhejiang University dustrial Engineering2012DOI: /j.cie Press2010 (inchinese).[ [M]. : 2010.] [16] HARTMANN SKOLISCH R.Experimentalevaluationof [5] DORNDORF UPESCH EPHAN-HUY T.Atime-oriented state-of-the-artheuristicsfortheresource-constrainedproject branch-and-boundalgorithm forresource-constrained project schedulingproblem[j].europeanjournalofoperationalre- scheduling withgeneralizedprecedenceconstraints[j].man- search (2):

14 96 19 [17] LIU QiongLIN KuiZHANGChaoyongetal.Multi-pro- jectrobustschedulingbasedoncriticalchain [J].Computer nyoptimizationalgorithm[c]//proceedingsof2010interna- Integrated ManufacturingSystems201218(4): (in tionalconferenceoninteligent Computing andinteligent Chinese).[. Systems (ICIS 2010). WashingtonD.C. USA:IEEE [J] (4): ] 20103: [18] WANGBingLIQiaoyunYIN Lei.Robustsatisfyingpro- [23] KOLISCH R.Serialandparalelresource-constrainedproject jectscheduling based on artificialimmunealgorithm [J]. schedulingmethodsrevisited:theoryandcomputation[j]. ComputerIntegrated ManufacturingSystems201117(5): EuropeanJournalof Operational Research199690(2): (inchinese).[ [J]. [24] XU Zeshui.Uncertain multipleatributedecision making: (5): ] [19] ZHANGShaqingCHEN XinduCHEN Qingxinetal.Re- activeschedulingformultiplemouldanddieprojectsbasedon [M]. : 2004.] improved multi-objective particle swarm optimization[j]. [25] YANGER R R.Onorderedweightedaveragingaggregation ChinaMechanicalEngineering201122(10): (in operatorsinmulticreteriadecisionmaking[j].ieeetransac- Chinese).[. tionson Systems Manand Cybernetics198818(1): [J] (10): ] [20] SHOU YongyiFU Ao. Multi-colony antalgorithm for multi-objectiveresource-constrainedprojectscheduling[j]. JournalofZhejiang University:EngineeringScience2010 constrainedprojectschedulingproblems [J].ComputerInte- grated ManufacturingSystems200915(12): (in [28] ZHOU MingSUNShudong.Geneticalgorithms:theoryand Chinese).[. application [M].Beijing:NationalDefenseIndustryPress [J] (12): ] [22] WANGJunqiangZHANGSongfeiCHENJianetal.Re- source-constrainedmulti-projectschedulingbasedonantcolo- methodsandapplications[m].beijing:tsinghuauniversity Press2004 (inchinese).[. [26] VIANA ASOUSAJP.Usingmetaheuristicsinmultiobjec- tiveresourceconstrained projectscheduling[j].european JournalofOperationalResearch (2): : (inChinese).[. [M]. : 1999.] : [27] WANG JunqiangZHANGSongfeiCHENJianetal.Three- 44(1):51-55 (inchinese).[. dimensionalgantchartbasedresource-constrainedmultiplepro- [J]. : jectsschedulingandcriticalchainidentification[c]//proceedings (1):51-55.] ofthe18thinternationalconferenceonindustrialengineeringand [21] LU RuiWANGCheng en.heuristicapproachforresource- Engineering Management. WashingtonD.C.USA:IEEE (1977-) : E- mail:wangjq@nwpu.edu.cn (1986-) : (1987-) : (1979-) : (1963-) :

Ⅰ Ⅱ 1 2 Ⅲ Ⅳ

Ⅰ Ⅱ 1 2 Ⅲ Ⅳ !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!