一種基于PERT的資源優(yōu)化新方法

武小平，安 靜，熊高江

（1.西安郵電大學(xué) 經(jīng)濟(jì)管理學(xué)院，西安 710061；2.陜西地礦第二綜合物探大隊(duì)，西安 710016）

0 引言

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

本文的資源優(yōu)化算法是在PERT基礎(chǔ)上根據(jù)勞動密集型項(xiàng)目所面臨的實(shí)際情況合理地做出創(chuàng)新和改進(jìn)，由于考慮到項(xiàng)目的資源、面臨的風(fēng)險和消耗的成本對工期的影響，運(yùn)用了層次分析法計算了影響因素的權(quán)重，以上文獻(xiàn)在資源優(yōu)化過程中很少考慮資源、風(fēng)險和成本對工期的影響，本文在考慮這三個因素對工期影響的情況下提出了新的求解網(wǎng)絡(luò)計劃資源優(yōu)化方法。

1 問題描述和優(yōu)化策略設(shè)計

1.1 問題描述

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

1.2 優(yōu)化策略設(shè)計

在資源有限的條件下，以調(diào)整相應(yīng)工作后的工期最短為目標(biāo)。這里著重討論每項(xiàng)工作資源強(qiáng)度固定和每項(xiàng)工作連續(xù)（工作內(nèi)部不可中斷）情況下的優(yōu)化方法。那么相應(yīng)的優(yōu)化策略就要在此限制條件下進(jìn)行。因此，如何調(diào)整工序延后時間，使得所有工作結(jié)束時工期最短？為了研究方便，下面給出3個限制條件：

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

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

（3）人力資源約束：各工序調(diào)整后要保證資源曲線在資源限量下方，不超出資源限量。在網(wǎng)絡(luò)計劃中，各項(xiàng)工作所需資源總數(shù)Zi-j是一個常數(shù),它等于工作的資源需要量強(qiáng)度Ri-j與相應(yīng)工作持續(xù)時間Di-j的乘積，各項(xiàng)工作所需資源總數(shù)為：Zi-j=Ri-j×Di-j。

本文重點(diǎn)討論工作資源強(qiáng)度固定，工作內(nèi)部連續(xù)不可中斷的情況，優(yōu)化策略如下：

（1）先根據(jù)初始網(wǎng)絡(luò)計劃圖確定可能同時進(jìn)行的所有工作 F（k）

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

（2）計算在t（AS_AF）階段同時進(jìn)行的工作總資源強(qiáng)度∑R

參加第k次資源分配的各項(xiàng)工作，在t（AS—AF）時間段的總資源數(shù)量應(yīng)該為在該階段參加工作的資源強(qiáng)度加和。將∑R與資源限量Q進(jìn)行比較∑R＞Q，則在該時段參加的工作要延后進(jìn)行；∑R≤Q，則該時段參加的工作不需要延后進(jìn)行。

（3）表示同時進(jìn)行工作的開始時間ASi-j，持續(xù)時間Di-j和結(jié)束時間AFi-j

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

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

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

（5）同時進(jìn)行工作的時間段（tAS_AF）的結(jié)束時間為Ft

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

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

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

如工作1的持續(xù)時間D1=4，開始時間到結(jié)束時間（AS1-AF1）=（1-4）；工作2的持續(xù)時間D2=4，開始時間到結(jié)束時間（AS2-AF2）=（4-7）；工作3的持續(xù)時間D3=6，開始時間到結(jié) 束 時 間 （AS3-AF3）=（1-6）;可 知 道 t（AS_AF）= （AS1_AF1）∩（AS2_AF2）∩（AS3_AF3）=4，F(xiàn)t=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的基礎(chǔ)上對延后工作開始時間和結(jié)束時間進(jìn)行相應(yīng)的調(diào)整，然后再進(jìn)入下一階段的分配

工作調(diào)整后的開始時間ASg=AS+△t；工作調(diào)整后的結(jié)束時間AFg=AF+△t。

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

2 △t的討論和影響因素權(quán)重計算

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

2.1 △t的討論

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

表1 層次結(jié)構(gòu)圖

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

2.2 影響因素權(quán)重計算

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

表2 B-C層次總排序

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

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

3 合理性證明

總工期T為從網(wǎng)絡(luò)計劃圖起始點(diǎn)到終點(diǎn)的最長路徑的持續(xù)時間D和延后時間△t的加和時間。在整個網(wǎng)絡(luò)中其中一條路徑為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）}，而上述方法是在既考慮資源限量又考慮工期影響因素情況下，整個網(wǎng)絡(luò)中每條路徑中每個工作增加的延后時間都是最小值，所以每條路徑都取得該路徑所有工作延后時間的最小值，即：

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

4 算例分析

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

圖1 初始網(wǎng)絡(luò)計劃圖和資源曲線

從圖1中可以觀察到在第4、5、6、7、8、9、10、11、12天所參加的工作總需要人員已經(jīng)超過了項(xiàng)目實(shí)際能夠提供的人員數(shù)量，由于人員受到限制就保證不了每天同時進(jìn)行的每項(xiàng)工作都能正常有序的進(jìn)行，所以對4～12天的工作進(jìn)行調(diào)整，在滿足人員配備的情況下適當(dāng)?shù)母鶕?jù)優(yōu)化策略進(jìn)行調(diào)整。

依據(jù)優(yōu)化策略對原始網(wǎng)絡(luò)計劃圖進(jìn)行調(diào)整，通過下頁表3的形式將優(yōu)化步驟呈現(xiàn)出來，可以觀察到每項(xiàng)工作的資源需求量R、延后時間△t、對整個工期影響權(quán)重Ω以及調(diào)整次數(shù)K，而且優(yōu)化步驟結(jié)束后,會得出優(yōu)化后的工期T=Ft（K=10）=20。

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

上述策略通過表格的方式清楚地呈現(xiàn)出每道工序的工作順序、延后時間、影響因素的權(quán)重和工期，不需要重復(fù)多次繪制調(diào)整網(wǎng)絡(luò)計劃圖，根據(jù)表3中的數(shù)據(jù)就可以畫出最終優(yōu)化網(wǎng)絡(luò)圖，將整個優(yōu)化過程清晰地呈現(xiàn)出來，由于不涉及時差的概念對于項(xiàng)目工程以外的領(lǐng)域進(jìn)行擴(kuò)展和研究就會相對容易。

表3優(yōu)化過程

圖2優(yōu)化策略調(diào)整后的網(wǎng)絡(luò)計劃圖和資源曲線

5 總結(jié)

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