網絡計劃優(yōu)化

網絡計劃的優(yōu)化遼寧理工職業(yè)學院徐建元1網絡時標圖的畫法有哪幾種，這幾種畫法的區(qū)別

2時標網絡圖的箭線長度代表什么3上講回顧怎樣確定關鍵線路和自由時差

網絡計劃優(yōu)化

工期優(yōu)化資源優(yōu)化費用優(yōu)化資源有限－工期最短工期固定－資源均衡“向關鍵線路要時間，向非關鍵線路要節(jié)約?！薄A羅庚一、工期優(yōu)化

若網絡圖的工期超過計劃工期，需要縮短（優(yōu)化）工期。壓縮關鍵線路持續(xù)時間；優(yōu)先選擇下列關鍵工作壓縮：對質量和安全影響不大、資源充足、增加的費用最少；壓縮時考慮資源供應和工作面；重復以上步驟，直到滿足工期要求或工期已不能再縮短為止。不能將關鍵工作壓縮成非關鍵工作。例：某工程網絡計劃如圖。要求工期15，試優(yōu)化。選擇關鍵工作壓縮持續(xù)時間時，應選優(yōu)選系數(shù)最小的工作或優(yōu)選系數(shù)之和最小的組合。圖例：工作（優(yōu)選系數(shù)）正常時間（最短時間）124A(2)B(8)6(4)D(5)6(4)F(5)2(1)H(2)4(2)G(10)8(6)6355(3)E(4)4(3)C(∞)11、節(jié)點標號法快速計算工期、找關鍵線路正常時間下工期19，應壓縮4；關鍵線路為：1-2-4-6。124A(2)B(8)6(4)D(5)6(4)F(5)2(1)H(2)4(2)G(10)8(6)6355(3)E(4)4(3)C(∞)1（①，5）（①②，6）（②，11）（④，11）（④，19）2、可供壓縮關鍵工作：A、D、G，優(yōu)選系數(shù)最小工作為A，其持續(xù)時間壓縮至最短時間3。節(jié)點標號法快速計算工期、找關鍵線路5(3)124A(2)B(8)6(4)D(5)6(4)F(5)2(1)H(2)4(2)G(10)8(6)635E(4)4(3)C(∞)1（①，3）（①，6）（③，10）（④，10）（④，18）此時關鍵線路發(fā)生改變，應恢復節(jié)點標號法快速計算工期、找關鍵線路4124A(2)B(8)6(4)D(5)6(4)F(5)2(1)H(2)4(2)G(10)8(6)635E(4)4(3)C(∞)1（①，4）（①，6）（②③，10）（④，10）（④，18）3A工作持續(xù)時間延長為4，恢復關鍵線路出現(xiàn)兩條關鍵線路，工期18，仍需壓縮故應選同時壓縮工作A和E的方案，將工作A、E同時壓縮1（至最短時間）4(3)124A(2)B(8)6(4)D(5)6(4)F(5)2(1)H(2)4(2)G(10)8(6)635E(4)4(3)C(∞)1（①，4）（①，6）（②③，10）（④，10）（④，18）3、有5種壓縮方案：G、A+B、D+E、A+E、B+D，對應優(yōu)選系數(shù)為10、10、9、6、13節(jié)點標號法快速計算工期、找關鍵線路4(3)124A(2)B(8)6(4)D(5)6(4)F(5)2(1)H(2)4(2)G(10)8(6)635E(4)4(3)C(∞)1（①，3）（①，6）（②③，9）（④，9）（④，17）33關鍵線路未變，工期17，仍需壓縮此時工作A、E已不能壓縮，優(yōu)選系數(shù)∞A(∞)E(∞)3124A(∞)B(8)6(4)D(5)6(4)F(5)2(1)H(2)4(2)G(10)8(6)635E(∞)3C(∞)1（①，3）（①，6）（②③，9）（④，9）（④，17）故應選擇壓縮工作G的方案，將工作G壓縮2（至最短時間）4、有2種壓縮方案：G、B+D，對應優(yōu)選系數(shù)為10、13節(jié)點標號法快速計算工期、找關鍵線路3124A(∞)B(8)6(4)D(5)6(4)F(5)2(1)H(2)4(2)G(10)8(6)635E(∞)3C(∞)1（①，3）（①，6）（②③，9）（④，9）（④，15）關鍵線路未變，工期15，滿足要求此時工作A、E、G已不能壓縮，優(yōu)選系數(shù)∞6G(∞)至此，完成工期優(yōu)化二、資源優(yōu)化不可能減少資源用量；優(yōu)化資源按時間的分布。

1.資源有限，工期最短網絡計劃某些時段的資源用量超過供應限量時，需要優(yōu)化資源，即延長某些工作的持續(xù)時間，導致工期增加；若所缺資源為平行工作使用，則后移某些工作，但應使工期延長最短；若所缺資源僅為一項工作使用，延長該工作持續(xù)時間；重復調整、計算，直到資源符合要求。計算公式：優(yōu)化示例某工程網絡計劃如圖，箭線上方為工作的資源強度，下方為持續(xù)時間。假定資源限量Ra=12。12345678910111213

1

36

56

4235445834353741.計算并繪資源需用量動態(tài)曲線從曲線可看出第4天和第7、8、9天兩個時間段的資源需用量超過資源限量。需進行調整。12345678910111213

1

36

56

423544583435374111215513122.調整第4天的平行工作第4天有1-3和2-4兩項平行工作，計算工期延長工作序號工作代號最早完成時間最遲開始時間ΔT1,2ΔT2,111-3431-22-463-3ΔT1,2最小，說明將2號工作安排在1號工作之后進行，工期延長最短，只延長1。調整后的網絡計劃如圖：從曲線可看出第8、9天時間段的資源需用量超過資源限量。需進行調整。12345678910111213

1

36

56

4235445834353741112155512113.計算并繪資源需用量動態(tài)曲線4.調整第8、9天的平行工作第8、9天有3-6、4-5和4-6三項平行工作，計算工期延長如表：工作序號工作代號最早完成時間最遲開始時間ΔT1,2ΔT1,3ΔT2,1ΔT2,3ΔT3,1ΔT3,213-69820----24-5107--21--34-6119----34ΔT1,3最小，為零，說明將3號工作安排在1號工作之后進行，工期不延長。調整后的網絡計劃如圖：從曲線可看出整個工期的資源需用量均未超過資源限量。已為最優(yōu)方案，最短工期13天。12345678910111213

1

36

56

42354458343537411128512115.計算并繪資源需用量動態(tài)曲線1網絡計劃技術的分類

23上講回顧工期優(yōu)化時什么樣的工作能被壓縮2.工期固定、資源均衡

網絡計劃的資源用量雖然沒有超過供應限量，但分布不均衡，如出現(xiàn)短時間的高峰或低谷，需要優(yōu)化資源，使之均衡；用資源需用量方差描述資源的均衡性；要保持工期固定，只能調整有時差的工作（非關鍵工作），即左移或者右移某些工作；多次調整，直至所有工作不能移動。左移或右移一項工作是否使資源更加均衡應根據以下判據：

設k工作從i時間單位開始，j時間單位完成，資源強度為γk，Ri為i時間單為的資源用量。k工作右移一個時間單位能使資源均衡的判據：k工作左移一個時間單位能使資源均衡的判據：移動工作能否使資源均勻的判據：

k工作右移數(shù)個時間單位能使資源均衡的判據：k工作左移數(shù)個時間單位能使資源均衡的判據：優(yōu)化示例某工程網絡計劃如圖，箭線上方為工作的資源強度，下方為持續(xù)時間。試進行“工期固定，資源均衡優(yōu)化”。0102030405060708091011121314

1

36

56

42234474456523455731.計算并繪資源需用量動態(tài)曲線工期14天，資源需用量平均值：1481251990102030405060708091011121314

1

36

56

422344744565234557320Rm=(2×14+2×19+20+8+4×12+9+3×5)/14=11.862.對節(jié)點6位為完成節(jié)點的工作調整以終點節(jié)點6為完成節(jié)點的非關鍵工作有工作3-6和4-6，先調整開始時間晚的工作4-6。1481251990102030405060708091011121314

1

36

56

422344744565234557320根據右移工作判別式：Rj+1+rk≦Ri1481251990102030405060708091011121314

1

36

56

422344744565234557320R11+r4-6=12=R7=12R12+r4-6=8<R8=12R13+r4-6=8<R9=12R14+r4-6=8<R10=12故工作4-6可右移4個時間單位，總時差用完工作4-6調整后的網絡計劃如圖：1489819120102030405060708091011121314

1

36

56

422344744565234557320R12+r3-6=12<R5=20R13+r3-6=12>R6=8R14+r3-6=12>R7=9接著調整工作3-6，該工作總時差3工作3-6只能右移一個時間單位工作3-6調整后的網絡計劃如圖：1489819120102030405060708091011121314

1

36

56

422344744565234557316以節(jié)點5為完成節(jié)點的非關鍵工作只有2-5，該工作時差73.對節(jié)點5為完成節(jié)點的工作調整1489819120102030405060708091011121314

1

36

56

422344744565234557316R6+r2-5=15<R3=19R7+r2-5=16<R4=19R8+r2-5=16=R5=16調整工作2-5，根據右移工作判別式工作2-5可右移三個時間單位R9+r2-5=16>R6=8工作2-5調整后的網絡計劃如圖：14159812120102030405060708091011121314

1

36

56

42234474456523455739以節(jié)點4為完成節(jié)點的非關鍵工作只有1-4，該工作時差14.對節(jié)點4為完成節(jié)點的工作調整1614159812120102030405060708091011121314

1

36

56

42234474456523455739調整工作1-4，根據右移工作判別式16R6+r1-4=20>R1=14故工作1-4不能右移14159812120102030405060708091011121314

1

36

56

42234474456523455739以節(jié)點3為完成節(jié)點的非關鍵工作只有1-3，該工作時差1，根據右移工作判別式：5.對節(jié)點3為完成節(jié)點的工作調整16R5+r1-3=12<R1=14故工作1-3可右移一個時間單位工作1-3調整后的網絡計劃如圖：14159812120102030405060708091011121314

1

36

56

422344744565234557311以節(jié)點2為完成節(jié)點的只有關鍵工作1-2，不能移動，至此，第一次調整結束。1614159812120102030405060708091011121314

1

36

56

422344744565234557311以節(jié)點6為完成節(jié)點的只有工作3-6有2個單位機動時間，根據右移工作判別式：166.進行第2次調整R13+r3-6=12<R6=15R14+r3-6=12<R7=16工作3-6可右移2個時間單位，結果如圖：141191212120102030405060708091011121314

1

36

56

422344744565234557311由圖可知，所有工作左移或右移均不能使資源需用量更加均衡，因此該方案即為最優(yōu)方案。167.比較優(yōu)化前后的方差值初始方案方差值：優(yōu)化方案方差值：方差降低率：工程總成本=直接費＋間接費費用工期總成本不同工期的最低直接費間接費及工期引起的資金損益等優(yōu)化工期最短工期正常工期工期與費用關系曲線三、費用優(yōu)化工程費用包括直接費和間接費；縮短工期導致直接費用增加，間接費用減少；尋求成本最低；直接費用率：縮短單位時間而增加的直接費；應選用直接費用率小的關鍵工作作為壓縮對象；

多條關鍵線路應壓縮組合直接費用率最小的關鍵工作；壓縮時間時應考慮間接費用減少的費用；縮短時間的關鍵工作不能變成非關鍵工作。

最小組合直接費用率大于間接費用率說明已不能再優(yōu)化。例：某工程網絡計劃如圖，該工程間接費用率為0.8萬元/天，試對其進行費用優(yōu)化。（單位：萬元、天）圖例：工作正常時間直接費（最短時間直接費）正常時間（最短時間）124A7.0(7.4)B9.0(11.0)8(6)D5.5(6.0)2(1)F8.0(9.6)6(4)I6.5(6.9)4(2)H7.5(8.5)6(4)6354(2)E8.0(8.4)5(3)C5.7(6.0)2(1)G5.0(5.7)2(1)1、節(jié)點標號法快速計算工期、找關鍵線路正常時間下工期19，關鍵線路為：1-3-4-6和1-3-4-5-6兩條。124A7.0(7.4)B9.0(11.0)8(6)D5.5(6.0)2(1)F8.0(9.6)6(4)I6.5(6.9)4(2)H7.5(8.5)6(4)6354(2)E8.0(8.4)5(3)C5.7(6.0)2(1)G5.0(5.7)2(1)（①，4）（①，8）（③，13）（④，15）（④⑤，19）2、計算各工作直接費用率：直接費總和Cd=62.2萬元間接費總和Ci=0.8×19=15.2萬元工程總費用Ct=62.2+15.2=77.4萬元3、壓縮費用將直接費用率標在工作旁壓縮方案有4種：B、E、G+H、H+I，對應直接費用率為1.0、0.2、1.2、0.7萬元/天。124A(0.2)B(1.0)8(6)D(0.5)2(1)F(0.8)6(4)I(0.2)4(2)H(0.5)6(4)6354(2)E(0.2)5(3)C(0.3)2(1)G(0.7)2(1)工作E直接費用率最小，選工作E作為壓縮對象，壓縮至最短時間3節(jié)點標號法快速計算工期、找關鍵線路5(3)124A(0.2)B(1.0)8(6)D(0.5)2(1)F(0.8)6(4)I(0.2)4(2)H(0.5)6(4)6354(2)E(0.2)C(0.3)2(1)G(0.7)2(1)3（①，4）（①，8）（③，11）（③，14）（⑤，18）工作E變?yōu)榉顷P鍵工作，時間延長為4，恢復節(jié)點標號法快速計算工期、找關鍵線路4124A(0.2)B(1.0)8(6)D(0.5)2(1)F(0.8)6(4)I(0.2)4(2)H(0.5)6(4)6354(2)E(0.2)C(0.3)2(1)G(0.7)2(1)3（①，4）（①，8）（③，12）（③

④，14）（④

⑤，18）壓縮方案：B、E+F、E+I、F+G+H、H+I，對應直接費用率1、1、0.4、2、0.7萬元/天4、第二次壓縮（三條關鍵線路）直接費用率最小為E+I組合，故同時壓縮工作E、I各1，此時E已至最短時間，不能再壓縮。48(6)6(4)4(2)124A(0.2)B(1.0)D(0.5)2(1)F(0.8)I(0.2)H(0.5)6(4)6354(2)E(0.2)C(0.3)2(1)G(0.7)2(1)3（①，4）（①，8）（③，11）（③，14）（④

⑤，17）3節(jié)點標號法快速計算工期、找關鍵線路關鍵線路變?yōu)閮蓷l，工作G被動變?yōu)榉顷P鍵E(∞)8(6)6(4)124A(0.2)B(1.0)D(0.5)2(1)F(0.8)I(0.2)H(0.5)6(4)6354(2)C(0.3)2(1)G(0.7)2(1)3（①，4）（①，8）（③，11）（③，14）（④

⑤，17）3可供壓縮的方案有三：B、F+H、H+I，對應直接費用率為1、1.3、0.7萬元/天E(∞)4、第三次壓縮應選擇同時壓縮工作H和I進行優(yōu)化。8(6)6(4)124A(0.2)B(1.0)D(0.5)2(1)F(0.8)I(0.2)H(0.5)6(4)6354(2)C(0.3)2(1)G(0.7)2(1)3（①，4）（①，8）（③，11）（③，14）（④

⑤，16）3同時壓縮工作H、I各1E