武小平，安 靜，熊高江

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

0 引言

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

本文的資源優(yōu)化算法是在PERT基礎(chǔ)上根據(jù)勞動密集型項目所面臨的實際情況合理地做出創(chuàng)新和改進(jìn)，由于考慮到項目的資源、面臨的風(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ǔ)上實現(xiàn)工期最短。

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

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

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

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

（3）人力資源約束：各工序調(diào)整后要保證資源曲線在資源限量下方，不超出資源限量。在網(wǎng)絡(luò)計劃中，各項工作所需資源總數(shù)Zi-j是一個常數(shù),它等于工作的資源需要量強(qiáng)度Ri-j與相應(yīng)工作持續(xù)時間Di-j的乘積，各項工作所需資源總數(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次分配時，會存在幾項工作同時進(jìn)行，但是前提是這幾項工作的緊前工作均完成了，把這幾項工作定義為工作集合F（k）。

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

參加第k次資源分配的各項工作，在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ù)時間不同，就存在幾項工作只是在（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

存在工作需要延后就是因為在t（AS_AF）時間段內(nèi)同時進(jìn)行的工作的資源強(qiáng)度的加和∑R大于資源限量Q，需要延后某項工作使該時間段內(nèi)的工作強(qiáng)度加∑R≤Q。所以確定工作延后時間就是要判斷在該時間段內(nèi)同時進(jìn)行的幾項工作中每項工作與其他工作不同時進(jìn)行的時間。每項工作與其他工作不同時進(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)整平行工作中的哪一項才能保證對工期影響盡可能小，這是對△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ò)中每條路徑中每個工作增加的延后時間都是最小值，所以每條路徑都取得該路徑所有工作延后時間的最小值，即：

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

4 算例分析

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

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

從圖1中可以觀察到在第4、5、6、7、8、9、10、11、12天所參加的工作總需要人員已經(jīng)超過了項目實際能夠提供的人員數(shù)量，由于人員受到限制就保證不了每天同時進(jìn)行的每項工作都能正常有序的進(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)出來，可以觀察到每項工作的資源需求量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)整一次就要重新計算每道工序的各項參數(shù)和重新繪制一次網(wǎng)絡(luò)計劃圖，而且對于人員需要量超出人員限量的時間段內(nèi)參與的工作，并沒有一個量化概念來確定應(yīng)該調(diào)整哪一項工作，也沒有定性的確定每一項工作對整個項目工期的影響，所以調(diào)整工作的方法大多會采取窮舉法，使得繪制的網(wǎng)絡(luò)圖增加，計算過程相對復(fù)雜，方法的實用性相對較差；而上述方法減少了項目涉及的變量，尤其是時差概念，時差相對于其他非工程領(lǐng)域理解和計算都相對復(fù)雜，減少原方法的時差概念也就簡化了整個過程的計算量，相比原來的方法本文的方法以延后時間△t的大小定量描述每項工作調(diào)整后對工期的影響，根據(jù)延后時間△t的值確定調(diào)整該時段哪一項工作；延后時間△t=Ft-AS+1的值與每項工作的開始時間和結(jié)束時間有關(guān)系，在同一時間段就有可能出現(xiàn)相同的延后時間，就需要判斷延后時間相同的工作對項目工期的影響，新方法借助層次分析法定性地判斷各個工作對項目工期的影響，確定在延后時間相同的情況下應(yīng)該調(diào)整哪一項工作。根據(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)出來，由于不涉及時差的概念對于項目工程以外的領(lǐng)域進(jìn)行擴(kuò)展和研究就會相對容易。

表3優(yōu)化過程

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

5 總結(jié)

本文設(shè)計的優(yōu)化方法是在人員受限的條件下，基于對整個項目的資源消耗、面臨風(fēng)險和成本需求的考慮，在保證任何時段人員需求不超過人員限量的情況下使整個項目實施工期最短，并且在實例分析中也證明了此方法的適用性。該優(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)一步研究方向。