基于改進(jìn)縮方差法的工期固定-資源均衡優(yōu)化方法

高 婷

重慶交通大學(xué),重慶 400074

0 引言

在網(wǎng)絡(luò)計(jì)劃中,最大資源需求量小于或等于實(shí)際可供應(yīng)的資源,就是一個(gè)可行的網(wǎng)絡(luò)計(jì)劃。在建設(shè)工程施工中,當(dāng)工期固定時(shí),為減少資源浪費(fèi)、降低成本,對(duì)資源配置進(jìn)行優(yōu)化以提高企業(yè)經(jīng)濟(jì)效益。對(duì)于工期固定的資源均衡配置問題,常用的方法有很多,例如縮方差法(方差法)[1]、方差值最小法[2]、削峰填谷法[3]等?？s方差法在資源均衡配置中應(yīng)用較廣。對(duì)于大型工程項(xiàng)目來說,網(wǎng)絡(luò)計(jì)劃的工序很多,若用原始的方法步驟求解,就會(huì)使有限時(shí)間內(nèi)的優(yōu)化工作變得不可行。因此,引入非關(guān)鍵工序組[4]的概念,將多個(gè)非關(guān)鍵工作放在一組進(jìn)行調(diào)整,以減少調(diào)整步驟。原有方差法是對(duì)問題進(jìn)行逐一試算、逐一調(diào)整,不能一次達(dá)到最大限度的資源均衡,特別是在大型網(wǎng)絡(luò)計(jì)劃中,使得計(jì)算和調(diào)整尤為繁瑣,降低優(yōu)化效率。因此,引入最小方差法的概念,選擇使方差變化最大的移動(dòng)時(shí)間作為調(diào)整時(shí)間。 本文結(jié)合非關(guān)鍵工序組概念與最小方差法對(duì)原有縮方差法進(jìn)行改進(jìn),并給出非關(guān)鍵工序組調(diào)整判別式的一般化形式,進(jìn)一步簡(jiǎn)化了計(jì)算過程。

1 縮方差法

方差是衡量隨機(jī)變量或一組數(shù)據(jù)時(shí)離散程度的度量,概率論中方差用來度量隨機(jī)變量和其數(shù)學(xué)期望之間的偏離程度。網(wǎng)絡(luò)計(jì)劃中,把每項(xiàng)工作上所配備的資源看作隨機(jī)變量,利用時(shí)差來調(diào)整工作的開始時(shí)間和與完成時(shí)間以縮小方差,當(dāng)這組隨機(jī)變量方差值盡可能小的時(shí)候,即資源得到盡可能均衡的分配。

縮方差法是利用平衡性指標(biāo)作為網(wǎng)絡(luò)計(jì)劃實(shí)現(xiàn)資源優(yōu)化的定量指標(biāo),以Δ作為判定是否進(jìn)行資源調(diào)整的依據(jù)。當(dāng)Δ≤0時(shí),可以對(duì)非關(guān)鍵工作進(jìn)行調(diào)整,調(diào)整后變小,說明資源得到更均衡的分配。

1.1 平衡性指標(biāo)∑R2

資源消耗的均方差可用下式表示[5]。

(1)

(2)

1.2 調(diào)整判別式Δ

(3)

Δ′=Rj+1-Ri+Rmn

(4)

式中:若Δ<0,則∑R2減少,該工作可以進(jìn)行調(diào)整;若Δ=0,則∑R2無變化,該工作可以不調(diào)整也可以調(diào)整;若Δ>0,則∑R2增加,該工作不能進(jìn)行調(diào)整。同理,當(dāng)該工作推遲nd時(shí),資源變化量判別式如下[1]。

(5)

式中:k為累計(jì)推遲時(shí)間,R(j+n)為該非關(guān)鍵工作在第j+n天的資源需求量,R(i+n-1)為該非關(guān)鍵工作在第i+n-1天的資源需求量,tmn為該非關(guān)鍵工作的持續(xù)時(shí)間,T1為總推遲時(shí)間。

2 非關(guān)鍵工序組

非關(guān)鍵工序組定義為初始總時(shí)差相等的非關(guān)鍵工序的集合。按工序總時(shí)差的大小,將非關(guān)鍵工序分組,同一組內(nèi)的工序,總時(shí)差相等,將單一非關(guān)鍵工序(即沒有與此工序總時(shí)差相同的工序)看成是只有一個(gè)工序的非關(guān)鍵工序組。將非關(guān)鍵工序組視為網(wǎng)絡(luò)圖中的1個(gè)獨(dú)立單位來進(jìn)行資源均衡優(yōu)化。非關(guān)鍵工序組優(yōu)化判別式由姚玉玲 等[4]提出,由實(shí)例分析得判別公式。

ΔFGJ=REF+1-RES+1+R1≤0

(6)

式中:ES和EF分別為非關(guān)鍵工序組的最早開始時(shí)間和最早完成時(shí)間,R1為非關(guān)鍵工序組中第1個(gè)工作的資源需要量。此公式為非關(guān)鍵工序組移動(dòng)1個(gè)單位時(shí)間的判別公式,將公式一般化得到非關(guān)鍵工序組移動(dòng)n個(gè)單位時(shí)間的判別式。

Δ′=

(7)

式中:T1為推遲的總時(shí)間;n為推遲的單位時(shí)間;kmn為非關(guān)鍵工序mn推遲的累計(jì)時(shí)間;tmn為非關(guān)鍵工序mn持續(xù)時(shí)間;kmn-tmn為非關(guān)鍵工序mn被推遲天數(shù)與持續(xù)時(shí)間之差;Rmn為非關(guān)鍵工序mn上的資源需求量;REF+n為第EF+n天的資源需求量,RES+n為第ES+n天的資源需求量;∑(kmn-tmn)Rmn為該非關(guān)鍵工序組中每個(gè)kmn≤tmn的非關(guān)鍵工序的推遲時(shí)間和持續(xù)時(shí)間之差與其資源需求量之積的和。

3 最小方差法

(8)

(9)

4 資源優(yōu)化步驟

5 實(shí)例應(yīng)用

圖1為雙代號(hào)時(shí)標(biāo)網(wǎng)絡(luò)圖及某種資源需要量動(dòng)態(tài)數(shù)列。假定時(shí)間單位為d。

圖1 初始時(shí)標(biāo)網(wǎng)絡(luò)圖及資源需求量

5.1 原始方法資源優(yōu)化過程

5.1.1 第1次調(diào)整

在網(wǎng)絡(luò)圖中,利用時(shí)差進(jìn)行調(diào)整的順序是自右向左逆箭線方向進(jìn)行。當(dāng)同一時(shí)間有多個(gè)工序擁有自由時(shí)差時(shí),按單位時(shí)間資源需要量由大到小的順序進(jìn)行調(diào)整。因此在圖1中,先考慮工序5→7的移動(dòng)。

計(jì)算Δ′,計(jì)算式參考式(4)、(5)。

①R(10+1)-R(3+1)+R57=2-10+4=-4<0,可右移1 d。

②R(10+2)-R(3+2)+R57=2-9+4=-3<0,可右移1 d,共2 d。

③R(10+3)-R(3+3)+R57=2-9+4=-3<0,可右移1 d,共3 d。

④R(10+4)-R(3+4)+R57=2-8+4=-2<0,可右移1 d,共4 d。

⑤R(10+5)-R(3+5)+R57=2-8+4=-2<0,可右移1 d,共5 d。

由于自由時(shí)差已全部用完,且所有Δ′均小于等于0,所以5→7工序一共可以移動(dòng)5 d。

5.1.2 第2次調(diào)整

由于工序2→7自由時(shí)差存在最后,所以考慮工序2→7的移動(dòng)。

計(jì)算Δ′,計(jì)算式參考式(4)、(5)。

①R(9+1)-R(6+1)+R27=-2+3=1>0,不可移動(dòng)1 d。

考察工序2→7是否可以移動(dòng)2 d,3 d,…,6 d。

由上述計(jì)算知,工序2→7不可向右移動(dòng),所以以下考慮工序3→5的調(diào)整。

計(jì)算Δ′,計(jì)算式參考式(4)、(5)。

①R(3+1)-R(2+1)+R35=6-8+2=0,可向右移動(dòng)1 d。

②R(3+2)-R(2+2)=5-6=-1<0,可向右移動(dòng)1 d,共2 d。

③R(3+3)-R(2+3)=5-5=0,可向右移動(dòng)1 d,共3 d。

④R(3+4)-R(2+4)=4-5=-1,可向右移動(dòng)1 d,共4 d。

⑤R(3+5)-R(2+5)=4-4=0,可向右移動(dòng)1 d,共5 d。

由上述式子可知,工序3→5可向右移動(dòng)5 d,資源得到更均衡的分配,現(xiàn)對(duì)1→3工作進(jìn)行調(diào)整。

5.1.3 第3次調(diào)整

計(jì)算Δ′,計(jì)算式參考式(4)、(5)。

①R(2+1)-R(0+1)+R13=6-7+1=0,可向右移動(dòng)1 d。

②R(2+2)-R(0+2)+R13=6-7+1=0,可向右移動(dòng)1 d,共2 d。

③R(2+3)-R(0+3)=5-6=-1<0,可向右移動(dòng)1 d,共3 d。

④R(2+4)-R(0+4)=5-6=-1<0,可向右移動(dòng)1 d,共4 d。

⑤R(2+5)-R(0+5)=4-5=-1<0,可向右移動(dòng)1 d,共5 d。

由上述計(jì)算結(jié)果可知,工序1→3一共可向右移動(dòng)5 d。資源得到更均衡分配,所有可調(diào)整箭線均已調(diào)整完成,優(yōu)化結(jié)束,圖2為最后優(yōu)化結(jié)果。

圖2 第3次調(diào)整網(wǎng)絡(luò)圖及資源需求量

5.2 優(yōu)化方法過程(1次調(diào)整)

1)確定非關(guān)鍵線路組。圖1中非關(guān)鍵線路1→2→7的總時(shí)差相等都為6;非關(guān)鍵線路1→3→5→7的總時(shí)差相等都為6;所以令1→2→7為一個(gè)非關(guān)鍵線路組,1→3→5→7為一個(gè)非關(guān)鍵線路組。

表1 非關(guān)鍵工序組移動(dòng)后的方差變化值

圖3 第1次調(diào)整后時(shí)標(biāo)網(wǎng)絡(luò)圖及資源需求量

6 結(jié)論

改進(jìn)后的縮方差法其實(shí)質(zhì)就是將原優(yōu)化過程許多中間環(huán)節(jié)進(jìn)行合并、化簡(jiǎn)。例如引入的非關(guān)鍵工序組方法,將多個(gè)可一起移動(dòng)的非關(guān)鍵工序合并進(jìn)行一起調(diào)整,減少了計(jì)算的工作量,從而使網(wǎng)絡(luò)計(jì)劃資源均衡優(yōu)化模型得到進(jìn)一步的完善。引入的最小方差法,針對(duì)同一節(jié)點(diǎn)有多個(gè)非關(guān)鍵工序組進(jìn)行調(diào)整,將方差最小(即對(duì)應(yīng)使資源配置最接近均衡的情況)值對(duì)應(yīng)的移動(dòng)時(shí)間作為調(diào)整時(shí)間,使資源配置盡可能一次性達(dá)到最優(yōu)。本文更正并完善了縮方差法的判別公式,整合非關(guān)鍵工序組、最小方差法等方法使調(diào)優(yōu)過程變得更加精簡(jiǎn),并減少了大量的計(jì)算和調(diào)整過程。從實(shí)例可以得出結(jié)論:原始縮方差法需要3次優(yōu)化調(diào)整的資源,改進(jìn)后的方法只需要1次即可完成,效率提升了近70%。證明了改進(jìn)后的方法是切實(shí)有效的。