一種基于PERT的資源優化新方法

武小平，安 靜，熊高江

（1.西安郵電大學 經濟管理學院，西安 710061；2.陜西地礦第二綜合物探大隊，西安 710016）

0 引言

目前，解決有限資源優化問題的方法有最小工作時差優先法（MINSLK）、最小最遲完成時間優先法（LFT）和資源進度安排法（RSM），其中RSM法是本文所采用方法的基礎[2]；在這些方法的基礎上烏日娜、徐方舟等[3]提出項目資源約束下資源優化的一種啟發式算法，減少了涉及變量和計算量，但是在工期計算中涉及工作順序并不適用于時序性強的項目；陳志勇、杜志達[4]提出用隨機數產生的隨機優先度來區分平行活動的先后關系，使用隨機搜索算法進行尋優；李嵐[5]提出基于網絡圖時間參數UTM算法的施工項目資源優化；魏欣海[6]提出水利工程中資源有限優化工期的方法。

本文的資源優化算法是在PERT基礎上根據勞動密集型項目所面臨的實際情況合理地做出創新和改進，由于考慮到項目的資源、面臨的風險和消耗的成本對工期的影響，運用了層次分析法計算了影響因素的權重，以上文獻在資源優化過程中很少考慮資源、風險和成本對工期的影響，本文在考慮這三個因素對工期影響的情況下提出了新的求解網絡計劃資源優化方法。

1 問題描述和優化策略設計

1.1 問題描述

給定一個進度計劃網絡圖，假設工作（i-j）是其中的一個工作，在某個時間段里不可能只進行（i-j）工作，會存在與（i-j）并行的工作，那么在該時間段或工作之間存在交疊時間段時，對資源的需求量就會增加，如何配置能夠保證這種增加不超過資源限量，且在不超過資源限量的基礎上實現工期最短。

1.2 優化策略設計

在資源有限的條件下，以調整相應工作后的工期最短為目標。這里著重討論每項工作資源強度固定和每項工作連續（工作內部不可中斷）情況下的優化方法。那么相應的優化策略就要在此限制條件下進行。因此，如何調整工序延后時間，使得所有工作結束時工期最短？為了研究方便，下面給出3個限制條件：

（1）時序關系：有些工作可以同時進行，而有些工作則必須在其他若干項工作完成之后才能進行，把工作之間的這種限制關系稱作時序關系。

（2）工序工作連續性：為保證工序工作合理性，在前一次資源分配時已經進行的工作在后續分配中不可中斷。

（3）人力資源約束：各工序調整后要保證資源曲線在資源限量下方，不超出資源限量。在網絡計劃中，各項工作所需資源總數Zi-j是一個常數,它等于工作的資源需要量強度Ri-j與相應工作持續時間Di-j的乘積，各項工作所需資源總數為：Zi-j=Ri-j×Di-j。

本文重點討論工作資源強度固定，工作內部連續不可中斷的情況，優化策略如下：

（1）先根據初始網絡計劃圖確定可能同時進行的所有工作 F（k）

在第k次分配時，會存在幾項工作同時進行，但是前提是這幾項工作的緊前工作均完成了，把這幾項工作定義為工作集合F（k）。

（2）計算在t（AS_AF）階段同時進行的工作總資源強度∑R

參加第k次資源分配的各項工作，在t（AS—AF）時間段的總資源數量應該為在該階段參加工作的資源強度加和。將∑R與資源限量Q進行比較∑R＞Q，則在該時段參加的工作要延后進行；∑R≤Q，則該時段參加的工作不需要延后進行。

（3）表示同時進行工作的開始時間ASi-j，持續時間Di-j和結束時間AFi-j

由于工作連續性：AFi-j=ASi-j+Di-j。

（4）各工作持續時間不同，就存在幾項工作只是在（ASi-j_AFi-j）過程中某一時段同時進行，把各工作同時進行的時間段表示為t（AS_AF）

若同時進行的工作為i-j,m-n和h-s則對同時進行工作開始時間到結束時間這一時間段取交集即：

（5）同時進行工作的時間段（tAS_AF）的結束時間為Ft

如同時工作時間t（AS_AF）=（1-3）則Ft=3。

（6）計算工作延后時間段△t

存在工作需要延后就是因為在t（AS_AF）時間段內同時進行的工作的資源強度的加和∑R大于資源限量Q，需要延后某項工作使該時間段內的工作強度加∑R≤Q。所以確定工作延后時間就是要判斷在該時間段內同時進行的幾項工作中每項工作與其他工作不同時進行的時間。每項工作與其他工作不同時進行時間為ti-j=Ft-ASi-j+1；該時間段內延后時間△t=min（ti-j）對應延后工作為i-j。

如工作1的持續時間D1=4，開始時間到結束時間（AS1-AF1）=（1-4）；工作2的持續時間D2=4，開始時間到結束時間（AS2-AF2）=（4-7）；工作3的持續時間D3=6，開始時間到結 束 時 間 （AS3-AF3）=（1-6）;可 知 道 t（AS_AF）= （AS1_AF1）∩（AS2_AF2）∩（AS3_AF3）=4，Ft=4。 工 作 1 延 后 時 間 t1=Ft-AS1+1=4-1+1=4；工作2延后時間t2=Ft-AS2+1=4-4+1=1；工作3延后時間t3=Ft-AS3+1=4-1+1=4；延后時間△t=min （t1，t2，t3）=1，工作2延后一天。

（7）在△t的基礎上對延后工作開始時間和結束時間進行相應的調整，然后再進入下一階段的分配

工作調整后的開始時間ASg=AS+△t；工作調整后的結束時間AFg=AF+△t。

（8）最終工期為最后一次分配中工作的結束時間為T=AF（maxK）

2 △t的討論和影響因素權重計算

同一時段會出現許多并行工作，為了使該時段參加工作的總資源需求量小于資源限量，對該時段所有參加的工作進行調整，但是調整平行工作中的哪一項才能保證對工期影響盡可能小，這是對△t進行的討論的重要原因。在資源受限條件下，選擇對工期影響小的工作進行調整，對工期影響的大小可以直觀的從各個工序的延后時間表現出來，延后時間大的工作對工期影響大，延后時間小的對工期影響小；但是通過計算發現同時段的并行工作的延后時間有可能出現想同值，這時候就需要對出現延后時間相同的工作進行權重分析，在延后時間相同的情況下，考慮工作緊后工作數（C1），工作緊后路線長度（C2）和工作資源強度（C3）三個非直觀因素對工期的影響，構建層次結構圖和判斷矩陣進行權重分析。

2.1 △t的討論

在優化策略中，延后時間△t的選取涉及多因素，使得延后時間△t的確定出現困難，由于工期由工作持續時間和工作延后時間組成，延后時間△t的選擇影響整個工期，于是引入權重來明確各因素對△t影響程度，最終通過權重比較確定延后時間△t的選取。在確定延后時間△t的值時既簡化了計算又避免使用窮舉法計算工期。這里運用層次分析法（AHP）來確定權重。考慮到△t值對工期的影響，計算出并行工作的△t值，當△t值不同時，選擇△t的最小值；當并行工作的△t值出現相同值且都為最小的△t值時，在資源優化過程中，要考慮△t值所對應的工序對資源優化整體水平的影響，層次結構如表1所示[7]。

表1 層次結構圖

資源有限條件下，對工期優化進行決策時，往往難以把影響這一目標的各個因素做出精確的量化排序，這樣會給決策者做出正確決策帶來難度。層次分析法就是根據對各個因素之間的重要程度進行量化，再通過對量化結果的處理得到各個因素對于總目標的影響的一個排序，該排序是以數字的形式表現出來的，雖然這些數字并不能精確的量化各個指標的權重，但是它們清晰地顯示出了對總目標的重要程度，給決策帶來了便利。

2.2 影響因素權重計算

工作的緊后工作數目C1：工作的緊后工作越多，對整個工期影響越大，所以工作緊后工作數目可以作為衡量工作先后安排的指標；工作緊后路線長度C2：工作后續影響路線越長，對整個工期影響越大，所以工作緊后路線長度可以作為衡量工作先后安排的指標；工作資源強度C3:根據起始資源曲線圖資源強度大的優先延后，使資源使用量不超過資源限量且資源分布較為均衡。如表2所示運用層次分析法對影響工期的因素工作緊后工作數（C1），工作緊后路線長度（C2）和工作資源強度（C3）進行權重比較[8-10]。

表2 B-C層次總排序

設C1（i,j）為工作（i,j）的緊后工作數目；設C2（i,j）為工作（i,j）的緊后線路的最大長度；設C3（i,j）為工作（i,j）的資源強度，為了使三個因素具有可比性，對它們進行歸一化處理，即：

其中max是對所有工作求最大值。綜上，得出權重Ω（i，j）=0.4SC1（i，j）+0.4SC2（i，j）+0.2SC3（i，j）。 對 工 作 延后時間△t進行討論，可以保證在同一時間段內進行的各個工作延后時間中選取最小值，由于工期T=∑D+∑△t,在∑D固定情況下，∑△t取得最小值，使得工期最短。

3 合理性證明

總工期T為從網絡計劃圖起始點到終點的最長路徑的持續時間D和延后時間△t的加和時間。在整個網絡中其中一條路徑為i-j-k-l-m-n；總工期為：

由于 AS（i-j）+{D（i-j）+D（j-k）+D（k-L）+D（L-m）+D（m-n）} 是固 定 的 ，T（i-j）的 大 小 取 決 于 Δt（j-k）+ Δt（k-L）+ Δ t（L-m）+Δt（m-n）}，而上述方法是在既考慮資源限量又考慮工期影響因素情況下，整個網絡中每條路徑中每個工作增加的延后時間都是最小值，所以每條路徑都取得該路徑所有工作延后時間的最小值，即：

同上，算出整個工期所有路徑工期，因為每條路徑各工作的持續時間是固定的，而上述方法對每條路徑增加的延后時間都是在滿足要求下的最小值，所以最終總工期T為調整后所有路徑工期的最大值也是相比較調整前工期增加的最小值。

4 算例分析

已知某項目工作流程以及各項工作的人員需用量和持續時間（工作箭線上方為人員需要量，箭線下方為工作持續時間），根據已知數據繪制初始網絡計劃圖和資源曲線，該項目的資源限量Q=15萬人，繪制的網絡計劃圖如圖1所示。

圖1 初始網絡計劃圖和資源曲線

從圖1中可以觀察到在第4、5、6、7、8、9、10、11、12天所參加的工作總需要人員已經超過了項目實際能夠提供的人員數量，由于人員受到限制就保證不了每天同時進行的每項工作都能正常有序的進行，所以對4～12天的工作進行調整，在滿足人員配備的情況下適當的根據優化策略進行調整。

依據優化策略對原始網絡計劃圖進行調整，通過下頁表3的形式將優化步驟呈現出來，可以觀察到每項工作的資源需求量R、延后時間△t、對整個工期影響權重Ω以及調整次數K，而且優化步驟結束后,會得出優化后的工期T=Ft（K=10）=20。

從原來的PERT方法可以看出，計算過程相對復雜，涉及時差概念和多個變量，對網絡計劃調整一次就要重新計算每道工序的各項參數和重新繪制一次網絡計劃圖，而且對于人員需要量超出人員限量的時間段內參與的工作，并沒有一個量化概念來確定應該調整哪一項工作，也沒有定性的確定每一項工作對整個項目工期的影響，所以調整工作的方法大多會采取窮舉法，使得繪制的網絡圖增加，計算過程相對復雜，方法的實用性相對較差；而上述方法減少了項目涉及的變量，尤其是時差概念，時差相對于其他非工程領域理解和計算都相對復雜，減少原方法的時差概念也就簡化了整個過程的計算量，相比原來的方法本文的方法以延后時間△t的大小定量描述每項工作調整后對工期的影響，根據延后時間△t的值確定調整該時段哪一項工作；延后時間△t=Ft-AS+1的值與每項工作的開始時間和結束時間有關系，在同一時間段就有可能出現相同的延后時間，就需要判斷延后時間相同的工作對項目工期的影響，新方法借助層次分析法定性地判斷各個工作對項目工期的影響，確定在延后時間相同的情況下應該調整哪一項工作。根據表3可以畫出調整過后的網絡計劃圖，如下頁圖2所示。

上述策略通過表格的方式清楚地呈現出每道工序的工作順序、延后時間、影響因素的權重和工期，不需要重復多次繪制調整網絡計劃圖，根據表3中的數據就可以畫出最終優化網絡圖，將整個優化過程清晰地呈現出來，由于不涉及時差的概念對于項目工程以外的領域進行擴展和研究就會相對容易。

表3優化過程

圖2優化策略調整后的網絡計劃圖和資源曲線

5 總結

本文設計的優化方法是在人員受限的條件下，基于對整個項目的資源消耗、面臨風險和成本需求的考慮，在保證任何時段人員需求不超過人員限量的情況下使整個項目實施工期最短，并且在實例分析中也證明了此方法的適用性。該優化方法在網絡計劃的資源優化中應用前景廣泛，不再涉及傳統方法中的時差概念，理解和掌握起來相對容易，區別于RSM方法，不再是根據某個單一條件來調整工作，開始考慮定量和定性相結合的方法來確定調整工序，使得在人員配置優化的條件下既保證了調整工作后對工期影響較小又提高了工作的時效性和顧客的滿意度，這在服務行業發展迅速的時代至關重要，但是針對大型復雜網絡計算步驟偏多，如何運用優化理論，軟件計算進行處理，可作為進一步研究方向。