網(wǎng)絡(luò)計劃的優(yōu)化3：資源優(yōu)化

1、網(wǎng)絡(luò)計劃優(yōu)化網(wǎng)絡(luò)計劃優(yōu)化 資源優(yōu)化專題資源優(yōu)化專題第一節(jié) 工期-資源優(yōu)化內(nèi)容：根據(jù)資源情況對網(wǎng)絡(luò)計劃進(jìn)行調(diào)整，在規(guī)定工期和資源供應(yīng)之間尋求相互協(xié)調(diào)和相互適應(yīng)。(1)“資源有限，工期最短”優(yōu)化在資源供應(yīng)有限制的條件下，尋求計劃的最短工期(2)“工期固定，資源均衡”優(yōu)化在工期規(guī)定的條件下，力求資源消耗均衡。優(yōu)化前提：(1)網(wǎng)絡(luò)計劃一經(jīng)制定，在優(yōu)化過程中不得改變各工序的持續(xù)時間；(2)各工序每天的資源需要是均衡的，合理的，優(yōu)化過程中不予改變；(3)除規(guī)定可以中斷的工序外，其它工序均應(yīng)連續(xù)作業(yè)。(4)優(yōu)化過程中不得改變網(wǎng)絡(luò)計劃各工序間的邏輯關(guān)系。時段與工序的關(guān)系：網(wǎng)絡(luò)計劃的每日資源需要量曲線是資源優(yōu)化

2、的初始狀態(tài)。每日資源需要量曲線的每一變化都說明有工序在該時間點(diǎn)開始或結(jié)束。每日資源需要量不變且連續(xù)的一段時間，稱為時段，用ta表示時段開始時間，tb表示時段完成時間，可用ta, tb表示這個時段。一、資源有限，工期最短優(yōu)化設(shè)某工程項目需要s種不同的資源，已知每天可能供應(yīng)的資源數(shù)量分別為r1(t)、 r2(t)、 rs(t)，完成每一個工序只需其中一種資源，設(shè)為第k種資源，單位時間資源需要量(強(qiáng)度)以表示，并假定為常數(shù)，在資源供應(yīng)滿足的條件下，完成工序i-j持續(xù)時間為tij，對資源有限，工期最短優(yōu)化，可按照極差原理確定其最優(yōu)方案，即網(wǎng)絡(luò)計劃資源動態(tài)曲線中任何資源時段ta, tb內(nèi)每天的資源消耗量

3、總和rk均應(yīng)小于或等于該計劃每天的資源限定量rt，即滿足 rkrt(一)時差、資源分析法1、分析步驟(1)根據(jù)網(wǎng)絡(luò)的邏輯關(guān)系和各工序作業(yè)持續(xù)時間，繪出相應(yīng)于各工序最早開始的時標(biāo)網(wǎng)絡(luò)圖及資源需要量動態(tài)圖。(2)逐個時段對資源總需要量進(jìn)行檢查，若不滿足供應(yīng)限量的要求時，則就需要對計劃進(jìn)行調(diào)整。直到所有內(nèi)資源總需要量都滿足供應(yīng)限量的要求為止。2、各時段內(nèi)資源分析及工序計劃調(diào)整的原則。(1)第一時段，假定在時段t0,t1內(nèi)，當(dāng)資源總需要量不滿足限量要求時： 先對位于關(guān)鍵線路上的工序進(jìn)行編號，其次對位于非關(guān)鍵線路上的工序按其總時差遞增順序進(jìn)行編號，如總時差相等，則按工序每天資源需要量遞減的順序編號。 把

4、位于本時段內(nèi)的工序，按編號由小到大順序依次分配每天所需資源，以不超過可能供應(yīng)的數(shù)量為限，余下的工序分配不到資源就右移到t1開始。(2)其它時段，假定已計算至k步，在時段t0,tk內(nèi)的工序 每天資源需要量之和沒有超過供應(yīng)的限量時，則就繼續(xù)計算第k+1步。先繪出前一步工序 右移后的新的時標(biāo)網(wǎng)絡(luò)圖及資源需要量動態(tài)圖；其次檢查時段tk,tk+1內(nèi)資源總需要量是否超過供應(yīng)的限量，若超過就對tk,tk+1內(nèi)的工序，根據(jù)以下原則調(diào)整：對于各工序內(nèi)部不允許中斷時：先對tk之前開始而在tk之后結(jié)束的工序，根據(jù)新的總時差與其開始時間至tk+1的距離之差的遞增順序編號，對上述差值相等的工序，按其每天資源量遞減的順序

5、編號。例：某工程網(wǎng)絡(luò)計劃初始方案如下，資源限定時rk=8(單位/天)，假設(shè)各工序的資源相互通用，每項工序開始后就不得中斷，試進(jìn)行資源有限、工期最短優(yōu)化。1246735(3)(4)23(4)23(5)(3)3(4)(3)42(4)0 06 78 82 22 59 9解：(1)根據(jù)各項工序持續(xù)時間tij,計算節(jié)點(diǎn)時間參數(shù)tei和tli,如圖5-1所示。(2)按節(jié)點(diǎn)最早時間tei繪制時標(biāo)網(wǎng)絡(luò)圖，圖中箭線數(shù)字為該工序資源需要量，并該圖下方繪出資源動態(tài)曲線。施工進(jìn)度計劃(天)12345678935443434811674(3)從圖5-2看出，第一個超過資源資源供應(yīng)限額的資源高峰時段為2,5時段，需進(jìn)行調(diào)

6、整。(4)資源時段2,5調(diào)整。該時段內(nèi)有2-4、2-5、3-6三道工序。根據(jù)資源分配規(guī)則，將其排序，并分配資源，如下表所示。二、工期固定、資源均衡優(yōu)化(一)用“使方差值最小”方法均衡資源設(shè)r(t)為時間t所需要的資源量，t為規(guī)定工期， 為資源需要量的平均值，則方差 為_r220_20_02_220_2)(1)(2)(1)(1ttttrdttrtrdttrtrdttrtdtrtrt由于施工網(wǎng)絡(luò)計劃資源需要量曲線是階梯形曲線，假定第i天資源量為ri，則2_1222222101221)(rrtrrrrdttrtiitttii此時，要使得方差最小，即要使：2212112ttiirrrr最小1、網(wǎng)絡(luò)計劃

7、調(diào)整的條件為了使目標(biāo)函數(shù) 減少，可以利用網(wǎng)絡(luò)中有時差的各項工序進(jìn)行計劃的調(diào)整，調(diào)整應(yīng)當(dāng)滿足以下條件。 (1)為了不改變總工期，每項工序的調(diào)整只能在工序活動許可的范圍內(nèi)進(jìn)行。(2)調(diào)整的結(jié)果應(yīng)使 減小，資源計劃較為均衡。(3)要求雙代號網(wǎng)絡(luò)圖的編號自始至終由小到大順序排列。2、調(diào)整各項工序的順序資源均衡是在編制網(wǎng)絡(luò)計劃之后進(jìn)行的。通過非關(guān)鍵線路上的非關(guān)鍵工序，在時差范圍內(nèi)進(jìn)行調(diào)整，必須按工序的邏輯關(guān)系逆序進(jìn)行。當(dāng)同一時間有多個工序 擁有自由時差時，應(yīng)按單位時間資源由大到小的順序逐一進(jìn)行。223、調(diào)整方法(一)(1)單一工序右移一個時間單位將計劃中的某一工序向右移動一個時間單位，假設(shè)該工序原來最早

8、開始時間為a，最早結(jié)束時間為b，資源需要量為rij,若向右移一個時間單位，則：第a+1天資源需要量將減少為r(a+1)-rij第b+1天資源需要量將增加為r(b+1)+rij要使 縮小，則移動工序后必須：tiir12) 1() 1() 1() 1(2222arbrrarrbrijij0) 1() 1(ijrarbr上式簡化得當(dāng)為平衡資源而調(diào)整工序時，若能滿足不等式(5-2)，則資源需要量趨向均衡，則可令該工序右移一個時間單位。(5-2)(2)單一工作右移幾個時間單位在工序時差范圍內(nèi)逐一試算是否可一次右移一至多個時間單位 。如果以t1記錄一次右移的時間，以l表示該工序能右移的最大時間，現(xiàn)已移動了

9、l1個時間單位，則t1l-l1若t1=2，即一次右移二個時間單位：則可由式(5-2)推出下式：r(b+1)-r(a+1)+rij+r(b+2)-r(a+2)+rij0 (5-3)當(dāng)一次右移t1天時，式(5-3)則為：110)()(tprijparpbr例：某工程網(wǎng)絡(luò)計劃如圖所示，時間單位為天。試確定工期固定、資源均衡的方案。解：(1)計算tei、tlij、tfij、ffij填入圖中3145672606(4)5 00 02(1)4(2)3(3)1(2)6(1)7(4)5(2)0 00 05 5660 06 122 74 43 810 1015 15(2)繪制es-ef時標(biāo)網(wǎng)絡(luò)圖，計算出資源動態(tài)數(shù)

10、列123456789101112131415778109988852222213546271221432第一次調(diào)整。節(jié)點(diǎn)7：以節(jié)點(diǎn)7為結(jié)束節(jié)點(diǎn)的工序有2-7、5-7、6-7，6-7為關(guān)鍵工序，故只考慮2-7和5-7工序。1)先考慮5-7：a=3,b=10,tf=ff5,r=4r(10+1)-r(3+1)+r5，7=2-10+4=-40，可右移一天。若5-7工序再右移1d，根據(jù)式5-2有：r(10+2)-r(3+2)+r5，7=2-9+4=-30，可以右移1天，共2天。 r(10+3)-r(3+3)+r5，7=2-9+4=-30，可再右移1天，共3天。r(10+4)-r(3+4)+r5，7=-2

11、0，可再右移1天，共4天。r(10+5)-r(3+5)+r5，7=-20,不能右移1天。r(9+1)-r(6+1)+r2，7+r(9+2)-r(6+2)+r2，7=4+6-4+3=90，不能右移2天，同理，2-7工序不能右移。節(jié)點(diǎn)5：以節(jié)點(diǎn)5為結(jié)束節(jié)點(diǎn)的工序只有3-5工序。a=2，b=3,tf=5,r=2.根據(jù)公式5-2：r(3+1)-r(2+1)+r3，5=6-8+2=0，可右移1 天。r(3+2)-r(2+2)+r3，5=5-8+2=-10，可再右移1 天。3-5工序共右移5天。12345678910111213141577685544856666677667544856666613546

12、27122143243-5工序右移5天后的網(wǎng)絡(luò)圖。123456789101112131415776655468566666135462712214324節(jié)點(diǎn)3：a=0,b=2,tf=5,據(jù)式5-2，1-3工序可右移5天。如下圖123456789101112131415666656568566666135462712214324調(diào)整方法(二)方法一的缺點(diǎn)：在運(yùn)用判別式時，必須工序每移動一次，就要對網(wǎng)絡(luò)計劃的工序進(jìn)行調(diào)整，重新計算資源量，作圖和計算工作量大。對下圖中工序2-7分析(1)根據(jù)式(5-2)2-7可右移1d，如圓點(diǎn)所示,8,9兩天資源量無變化，只考慮7,10兩天1234567891011

13、121314157781099888522222135462712214320385) 16() 19(7, 21rrr1234567891011121314157781099888522222135462712214323382)26()29(7, 22rrr(2)2-7可再右移1d，如點(diǎn)劃線所示，與圓點(diǎn)相比較，8,11兩天資源量有變化。(3)工序可再右移1d，如虛線所示，與點(diǎn)劃線比較，9,12兩天資源量變化。1234567891011121314157781099888522222135462712214323382)36()39(7, 21rrr(4)注意：式中第10天與初始網(wǎng)絡(luò)圖中的第

14、10天的資源量不一致。1234567891011121314157781099888522222135462712214323382)46()49(7, 24rrr工序右移的判別公式：本次調(diào)整的累計右移時間為l1，單一工序一次右移一個時間單位單一工序一次右移一個時間單位：當(dāng)l1tij時，當(dāng)l1tij時，若滿足上兩式，則可將該工序右移1個時間單位。單一工序一次右移t1個時間單位當(dāng)l1tij時，當(dāng)l1tij時，注：上述公式中的資源量均是該本次調(diào)整前的網(wǎng)絡(luò)圖中的資源量。不必移動一次工序，就對資源量進(jìn)行重新計算。0) 1() 1(ijrarbr0) 1() 1(arbr0)()(11ijtprparp

15、br0)()(11parpbrtp例：以圖5-11為例1234567891011121314157781099888522222135462712214324第一次調(diào)整：節(jié)點(diǎn)：以為結(jié)束節(jié)點(diǎn)的非關(guān)鍵工序有2-7和5-7。(1)先考慮5-7工序：a=3,b=10,tf=ff=5,r=4,t=7應(yīng)用公式(5-5)，以初始網(wǎng)絡(luò)圖為基礎(chǔ)： 可右移1d 可右移1d，共2d 可右移1d，共3d 可右移1d，共4d 可右移1d，共4d 可右移1d，共5d右移后的時標(biāo)網(wǎng)絡(luò)圖及每資源需要量如下圖03492) 13() 110(7, 5rrr03492)23()210(7, 5rrr03492)33()310(7,

16、 5rrr03482)43()410(7, 5rrr03482)43()410(7, 5rrr03482)53()510(7, 5rrr123456789101112131415778655448566666135462712214324以上圖為基礎(chǔ)，考慮工序2-7：a=6,b=9,tf=ff=6,r=3,t=3應(yīng)用式(5-5) 不能右移1d 應(yīng)用式(5-7) 不能右移2天。應(yīng)用式(5-8)不能右移4天，同理，可推導(dǎo)2-7不能移動09)26()29() 16() 19(7, 27, 2rrrrrr0256864645)46()49()36()39()26()29()16()19(rrrrrrr

17、r04) 16() 19(7, 2rrr節(jié)點(diǎn)：只有非關(guān)鍵工序3-5，a=2,b=3,tf=5,r=2,t=1 可右移1 d 此時，l1=1=t=1,以下計算l1將大于t,應(yīng)用公式(5-6)。 可再右移1d，共2d 可推導(dǎo)3-5可右移共5天。問題：直接應(yīng)用公式5-8推導(dǎo)3-5能否右移5天。調(diào)整后見下圖。 0) 12() 13(5 , 3rrr0165)22()23(rr123456789101112131415776655468566666135462712214324節(jié)點(diǎn)：非關(guān)鍵工序1-3，可推導(dǎo)，1-3可右移5天，第一次調(diào)整結(jié)束。第二次調(diào)整，無工序可調(diào)整，過程結(jié)束。1234567891011

18、12131415666656568566666135462712214324(二)用“使極差值為最小”方法均衡資源極差值為：資源平均值為常數(shù)，因此欲使極差值最小，應(yīng)使 最小，即使每天資源的最大用量為最低，常用“削高峰法”。利用時差將高峰的某些工序后移以逐步降低峰值，每次削去高峰的一個資源計量單位，反復(fù)進(jìn)行直到不能再削為止。|)(|max_, 0rtrtt)(max, 0trtt例：某工程網(wǎng)絡(luò)計劃如下圖。12346910578(4)4(1)3(3)2(2)4(3)3(4)5(2)3(5)5(4)5(3)3(2)3(2)2解：第一步：按最早開始時間繪制時標(biāo)網(wǎng)絡(luò)計劃，計算每日資源需要量動態(tài)數(shù)列 第二

19、步：確定資源數(shù)量上限(動態(tài)數(shù)列中的最大 值減去它的一個計量單位，本例中在本例中，最大值是第5天的11，則削峰目標(biāo)為： r=11-1=10第三步：分析資源限值的高峰并調(diào)整。如時段內(nèi)的資源量超過限值用正式判斷能否調(diào)整：1234567891011121314151617181920212212456798103(4)(1)(3)(2)(4)(2)(5)(3)(4)(2)(2)(3)ij如時段內(nèi)的資源量超過限值用正式判斷能否調(diào)整：若不等式成立，則該可以向右移動至高峰值之后，即移 個時間單位；不等不成立，則不能移動。當(dāng)在需要調(diào)整的時段內(nèi)不止一個工序可使不等成立時，就按時間差值的大小順序移動。如時間差值相

20、同，就使資源數(shù)量小的優(yōu)先移動。在本例中，第5天資源數(shù)量為11，超過r=10的規(guī)定，這個時段內(nèi)2-5、2-4、3-6、3-10四個工序，分別計算它們的時間差值。將3-10向右移動2天。見下圖)(1ijkest0)(1ijkijijesttf1)45(23 , 21)45(04, 210) 35(126, 313) 35(1510, 312345678910111213141516171819202122555798866888774444455512456798103(4)(1)(3)(2)(4)(2)(5)(3)(4)(2)(2)(3)ij經(jīng)調(diào)整后，沒有時段資源超過10，第一次調(diào)整結(jié)束。第二次

21、調(diào)整：從上圖，現(xiàn)資源數(shù)量最大 值為9，故資源數(shù)量上限為9-1=8，檢查可知第5天資源數(shù)量超過了限量，此時段內(nèi)有工序2-4、3-6、2-5、計算時間差值。調(diào)整3-6，將其向右移動2天。資源數(shù)量見下表。1)45(04, 210) 35(126 , 31)45(25 , 2第6,7兩資源數(shù)量超過r=8，此時段中有工序2-5.2-4、3-6、3-10計算時間差值：如是選擇3-10，但其資源數(shù)量為2，移動后仍不能解決資源沖突，故移動3-6，將其右移2天。1)47(25 , 23)47(04, 28)57(106 , 311)57(1310, 3123456789101112131415161718192

22、02122555461111668887744444555第8,9兩天資源數(shù)量超過r=8，此時段中有工序2-4、3-6、3-10，計算時間差值：1234567891011121314151617181920212255546889988877444445551)47(25 , 23)47(04, 28)57(106 , 311)57(1310, 3得：將3-10優(yōu)先調(diào)整，向右移動 4天，見下表。第10至13天資源數(shù)量超過r=8，時段內(nèi)有工序5-7、4-6、3-10、6-9。將3-10向后移動 4天，計算每日資源數(shù)量后，第14天仍超過，將其再后移1天，滿足r=8，第二次調(diào)整完成。畫出時標(biāo)網(wǎng)絡(luò)圖。5)49(04, 26)79(86, 39)59(1310, 31234567891011121314151617181920212255546667710101097444445554)913(07, 51)913(56, 45)913(910, 3第二次調(diào)整后的時標(biāo)網(wǎng)絡(luò)計劃12345678910111213141516171819202122555466677888776666455512456798103(4)(1)(3)(2)(4)(2)(5)(3)