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

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

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

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

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

5、編號(hào)。例：某工程網(wǎng)絡(luò)計(jì)劃初始方案如下，資源限定時(shí)rk=8(單位/天)，假設(shè)各工序的資源相互通用，每項(xiàng)工序開(kāi)始后就不得中斷，試進(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ù)各項(xiàng)工序持續(xù)時(shí)間tij,計(jì)算節(jié)點(diǎn)時(shí)間參數(shù)tei和tli,如圖5-1所示。(2)按節(jié)點(diǎn)最早時(shí)間tei繪制時(shí)標(biāo)網(wǎng)絡(luò)圖，圖中箭線(xiàn)數(shù)字為該工序資源需要量，并該圖下方繪出資源動(dòng)態(tài)曲線(xiàn)。施工進(jìn)度計(jì)劃(天)12345678935443434811674(3)從圖5-2看出，第一個(gè)超過(guò)資源資源供應(yīng)限額的資源高峰時(shí)段為2,5時(shí)段，需進(jìn)行調(diào)

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

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

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

9、l1個(gè)時(shí)間單位，則t1l-l1若t1=2，即一次右移二個(gè)時(shí)間單位：則可由式(5-2)推出下式：r(b+1)-r(a+1)+rij+r(b+2)-r(a+2)+rij0 (5-3)當(dāng)一次右移t1天時(shí)，式(5-3)則為：110)()(tprijparpbr例：某工程網(wǎng)絡(luò)計(jì)劃如圖所示，時(shí)間單位為天。試確定工期固定、資源均衡的方案。解：(1)計(jì)算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時(shí)標(biāo)網(wǎng)絡(luò)圖，計(jì)算出資源動(dòng)態(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)用判別式時(shí)，必須工序每移動(dòng)一次，就要對(duì)網(wǎng)絡(luò)計(jì)劃的工序進(jìn)行調(diào)整，重新計(jì)算資源量，作圖和計(jì)算工作量大。對(duì)下圖中工序2-7分析(1)根據(jù)式(5-2)2-7可右移1d，如圓點(diǎn)所示,8,9兩天資源量無(wú)變化，只考慮7,10兩天1234567891011

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

14、10天的資源量不一致。1234567891011121314157781099888522222135462712214323382)46()49(7, 24rrr工序右移的判別公式：本次調(diào)整的累計(jì)右移時(shí)間為l1，單一工序一次右移一個(gè)時(shí)間單位單一工序一次右移一個(gè)時(shí)間單位：當(dāng)l1tij時(shí)，當(dāng)l1tij時(shí)，若滿(mǎn)足上兩式，則可將該工序右移1個(gè)時(shí)間單位。單一工序一次右移t1個(gè)時(shí)間單位當(dāng)l1tij時(shí)，當(dāng)l1tij時(shí)，注：上述公式中的資源量均是該本次調(diào)整前的網(wǎng)絡(luò)圖中的資源量。不必移動(dòng)一次工序，就對(duì)資源量進(jìn)行重新計(jì)算。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右移后的時(shí)標(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不能移動(dòng)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 此時(shí)，l1=1=t=1,以下計(jì)算l1將大于t,應(yīng)用公式(5-6)。 可再右移1d，共2d 可推導(dǎo)3-5可右移共5天。問(wèn)題：直接應(yīng)用公式5-8推導(dǎo)3-5能否右移5天。調(diào)整后見(jiàn)下圖。 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)整，無(wú)工序可調(diào)整，過(guò)程結(jié)束。1234567891011

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

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

20、同，就使資源數(shù)量小的優(yōu)先移動(dòng)。在本例中，第5天資源數(shù)量為11，超過(guò)r=10的規(guī)定，這個(gè)時(shí)段內(nèi)2-5、2-4、3-6、3-10四個(gè)工序，分別計(jì)算它們的時(shí)間差值。將3-10向右移動(dòng)2天。見(jiàn)下圖)(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)整后，沒(méi)有時(shí)段資源超過(guò)10，第一次調(diào)整結(jié)束。第二次

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

22、02122555461111668887744444555第8,9兩天資源數(shù)量超過(guò)r=8，此時(shí)段中有工序2-4、3-6、3-10，計(jì)算時(shí)間差值：1234567891011121314151617181920212255546889988877444445551)47(25 , 23)47(04, 28)57(106 , 311)57(1310, 3得：將3-10優(yōu)先調(diào)整，向右移動(dòng) 4天，見(jiàn)下表。第10至13天資源數(shù)量超過(guò)r=8，時(shí)段內(nèi)有工序5-7、4-6、3-10、6-9。將3-10向后移動(dòng) 4天，計(jì)算每日資源數(shù)量后，第14天仍超過(guò)，將其再后移1天，滿(mǎn)足r=8，第二次調(diào)整完成。畫(huà)出時(shí)標(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)整后的時(shí)標(biāo)網(wǎng)絡(luò)計(jì)劃12345678910111213141516171819202122555466677888776666455512456798103(4)(1)(3)(2)(4)(2)(5)(3)