廣義優(yōu)先關(guān)系下工序共用時差的計算與應(yīng)用

蘇志雄，顧輝明，魏漢英

(南昌工程學(xué)院 工商管理學(xué)院，江西 南昌 330099)

在現(xiàn)代化生產(chǎn)和管理中，日益激烈的時間競爭已成為最顯著特征之一。時間早在上世紀(jì)80年代就被認(rèn)為是競爭優(yōu)勢來源[1]，使得管理者越發(fā)重視時間在項目中的功能。機(jī)動時間是該競爭優(yōu)勢來源的具體化表現(xiàn)，主要用于避免和緩和潛在的項目延期，保護(hù)項目的重要工序。某工序的機(jī)動時間不僅刻畫了該工序?qū)τ陧椖康闹匾?，而且還反映了項目的結(jié)構(gòu)特性，為項目計劃與進(jìn)度提供指導(dǎo)依據(jù)。鑒于此，機(jī)動時間長期被視作項目優(yōu)化的重要參數(shù)，多數(shù)項目管理方法，特別是項目調(diào)度，均以機(jī)動時間為基礎(chǔ)[2-3]。工序機(jī)動時間的概念和算法是在網(wǎng)絡(luò)計劃技術(shù)(以Critical Path Method為代表，簡稱CPM[4])出現(xiàn)后被逐步提出并完善，其經(jīng)典類型包括總時差，自由時差，安全時差，節(jié)點(diǎn)時差和干擾時差[2，5]。前三類時差主要界定單工序的活動范圍，而后兩類時差的實質(zhì)則是不同工序的機(jī)動時間的相互重疊和互斥，體現(xiàn)了工序間的相互影響情況，是項目調(diào)度復(fù)雜程度的重要決定因素[3]。其中，工序節(jié)點(diǎn)時差概念的提出源自Activity-on-Arrow網(wǎng)絡(luò)，反映的是該網(wǎng)絡(luò)中前后相鄰工序的共用節(jié)點(diǎn)的時差，但是這一時差概念在Activity-on-Node網(wǎng)絡(luò)中卻體現(xiàn)的不夠直觀，為化解這一矛盾，工序節(jié)點(diǎn)時差也被稱為工序共用時差[2]。本文將使用這一概念名稱。

廣義優(yōu)先關(guān)系[6](generalized precedence relations，簡稱GPRs)及其理論是對網(wǎng)絡(luò)計劃技術(shù)的拓展，較全面涵蓋了現(xiàn)代工程項目中工序間的優(yōu)先關(guān)系，包括各類型最小和最大時距。隨著GPRs的提出，GPRs下的工序機(jī)動時間成為研究的必然。Elmaghraby[7]等提出目前通用的GPRs表示法，并較早提出GPRs下工序總時差，自由時差和安全時差的計算方法，適用于工序工期不變的情況。Valls和Lino[8]，楊冰[9]，Yakhchali和Ghodsypour[10]針對最小時距，而周夢和杜志達(dá)[11]針對最大時距，分別研究了工序時間參數(shù)的計算方法。在GPRs下工序機(jī)動時間研究過程中，一些學(xué)者發(fā)現(xiàn)，當(dāng)工序的工期發(fā)生變動時，現(xiàn)有時差會出現(xiàn)諸多奇異現(xiàn)象。Elmaghraby[7]等發(fā)現(xiàn)GPRs 下一些關(guān)鍵工序的工期延長/縮短，反而導(dǎo)致總工期縮短/延長，即關(guān)鍵工序與總工期逆相關(guān)，還發(fā)現(xiàn)一些關(guān)鍵工序的工期變化不會影響總工期。與關(guān)鍵工序相對應(yīng)，非關(guān)鍵工序很可能也具有類似的奇異現(xiàn)象。Qi[12]等發(fā)現(xiàn)一些工序隨著工期的延長，其總時差反而增加，即“總時差越用越多”。蘇志雄[13]等提出隱性時間參數(shù)的概念，一定程度上對奇異現(xiàn)象做出解釋。闞芝南[14]等發(fā)現(xiàn)在GPRs網(wǎng)絡(luò)中，工序間加入不同表現(xiàn)形式的同一時間約束，可能會產(chǎn)生不同的最大路長，可能導(dǎo)致奇異現(xiàn)象出現(xiàn)。受此啟發(fā)，Su[15]等從GPRs網(wǎng)絡(luò)路長的角度分析了上述GPRs下工序總時差奇異現(xiàn)象的起因和機(jī)理。最近，Su[16]發(fā)現(xiàn)了GPRs下機(jī)動時間隱性消耗現(xiàn)象等新奇異現(xiàn)象。

現(xiàn)有文獻(xiàn)顯示，目前對GPRs下工序機(jī)動時間計算方法的研究主要針對工序總時差，自由時差和安全時差，在機(jī)動時間特性研究上尤以總時差為重點(diǎn)對象。然而，對于GPRs下另兩類經(jīng)典類型時差——工序共用時差和干擾時差，尚缺乏充分研究。對工序共用時差和干擾時差的研究在經(jīng)典CPM網(wǎng)絡(luò)中有一定的體現(xiàn)，具有較明確的概念和計算方法[2]。Michael[17]等發(fā)現(xiàn)CPM箭線式網(wǎng)絡(luò)中的虛箭線對工序共用時差和干擾時差會產(chǎn)生較大影響，進(jìn)而研究了虛箭線最小化問題。Demeulemeester[3]等進(jìn)一步研究了CPM網(wǎng)絡(luò)中的虛箭線，提出了工序時間參數(shù)的修正方法，力求避免虛箭線對工序共用時差和干擾時差的影響。張立輝[18]等建立了工序共用時差與CPM網(wǎng)絡(luò)路長間的關(guān)系，進(jìn)而開發(fā)出工序共用時差對相關(guān)網(wǎng)絡(luò)優(yōu)化問題的新功能。針對工序共用時差和干擾時差所導(dǎo)致的工序間相互影響的規(guī)律，李星梅[19]等借助CPM網(wǎng)絡(luò)研究了這兩類時差的動態(tài)特征，揭示了單工序?qū)ζ渌ば虻挠绊懗潭群头秶?。蘇志雄[20]等發(fā)現(xiàn)由于工序共用時差和干擾時差的存在，項目的總體機(jī)動時間并非定值，而是會隨著工序使用共用時差的不同而變化。GPRs網(wǎng)絡(luò)和CPM網(wǎng)絡(luò)差異很大，CPM網(wǎng)絡(luò)中的節(jié)點(diǎn)可表示工序共用時差，但GPRs網(wǎng)絡(luò)中的節(jié)點(diǎn)卻只能表示工序總時差[8]，并且CPM網(wǎng)絡(luò)中工序干擾時差的計算方法也同樣不適用于GPRs網(wǎng)絡(luò)。Li[21]等進(jìn)一步分析了GPRs下工序間時距與工序工期的關(guān)系，兩者的動態(tài)變化交叉影響者工序機(jī)動時間的值和可用范圍。因此，需要新的思路和方法研究GPRs下的工序共用時差和干擾時差。

工序共用時差和干擾時差導(dǎo)致了項目中工序間的關(guān)系錯綜復(fù)雜，對任何具有這兩類時差的工序的調(diào)整都可能改變其他大量工序的時間參數(shù)，可謂“牽一發(fā)而動全身”，是項目調(diào)度優(yōu)化中最怕遇見且最難處理的情況之一。因此，要獲得更優(yōu)甚至最優(yōu)的項目調(diào)度結(jié)果，提高項目管理效率，從工序共用時差和干擾時差入手有可能成為新的研究視角和突破口。本文重點(diǎn)針對GPRs下的工序共用時差，借助GPRs網(wǎng)絡(luò)研究其概念、計算方法、以及特性，并應(yīng)用于帶有 GPRs的資源均衡中，主要包括：化簡該問題模型；對模型的難易區(qū)域進(jìn)行區(qū)分，使得在求解過程中具有針對性，進(jìn)而提出更有效混合算法的新思路。

1 廣義優(yōu)先關(guān)系(GPRs)

1.1 GPRs包含的時距類型

GPRs包含的工序j和k之間時距類型如表1所示(sk和fk分別表示工序k的開始和結(jié)束時間)。

1.2 GPRs表示方法

Elmaghraby[7]等提出的GPRs箭線式網(wǎng)絡(luò)是當(dāng)前國際通用的GPRs表示法，特征如下：

(1)網(wǎng)絡(luò)起點(diǎn)編號為(0)，終點(diǎn)編號為(2n+1)，n表示工序數(shù)；

(2)工序k的圖示包含開始節(jié)點(diǎn)(2k-1)，結(jié)束節(jié)點(diǎn)(2k)，箭線(2k-1，2k)，(長度d2k-1，2k=dk)和箭線(2k，2k-1)，(長度d2k，2k-1=-dk)，dk為該工序的工期；

(3)工序j到k的時距用箭線(h，i)或(i，h)表示，h=2j-1，2j，i=2k-1，2k，其中，箭線(h，i)表示最小時距，其長度dhi=δ，箭線(i，h)表示最大時距，其長度dih=-δ。

1.3 GPRs下的現(xiàn)有工序時差

文獻(xiàn)[7]針對工序工期不變的情況，提出了工序k的總時差TFk，自由時差FFk和安全時差SFk：

(1)

(2)

(3)

(4)

(5)

(6)

(7)

2 GPRs下的工序共用時差

2.1 工序工期不變的情況

類似地，假設(shè)工序j和k之間存在其他類型優(yōu)先關(guān)系(如圖1(a)～(d)所示為工序間最小時距)，同樣可以得出CFjk。若工序j和k之間存在多類型優(yōu)先關(guān)系，包括最小時距(從工序j指向工序k的箭線)和最大時距(從工序k指向工序j的箭線)，則CFjk取決于這些箭線干擾時差中的最大者，即

(8)

前式為該情況的特例，因此式(8)是相鄰工序共用時差的總公式。

由于工序k可能有多個相鄰工序，且與各相鄰工序的共用時差不同，為便于分析，給出工序k的統(tǒng)一共用時差，以工序間的共用時差最大值為基礎(chǔ)。首先介紹緊前和緊后工序概念。GPRs網(wǎng)絡(luò)中，如果有表示優(yōu)先關(guān)系的箭線從工序j指向工序k，稱工序j是工序k的緊前工序，工序j是工序k的緊后工序。

(1)工序k的前共用時差，記為CFk，表示該工序與其緊前工序的共用時差，

(9)

(10)

(3)工序k的總共用時差，記為CFk，表示該工序與所有相鄰工序的共用時差，

(11)

圖1 各類型最小時距

2.2 工序工期可延長的情況

根據(jù)式(4)～(7)，GPRs網(wǎng)絡(luò)中，任意工序k的工期延長時，可能會出現(xiàn)以下現(xiàn)象：

(12)

(13)

根據(jù)式(8)～(11)算出工序j和k的各類共用時差CFjk、*CFk和CFk。

2.3 工序工期可縮短的情況

GPRs網(wǎng)絡(luò)中工序k由箭線(2k-1，2k)和(2k，2k-1)組成，也可繪成圖2，為避免混淆，記工序k在圖2中為-k，其開始節(jié)點(diǎn)為(2k)，結(jié)束節(jié)點(diǎn)為(2k-1)。根據(jù)隱性時差和偽時差理論，若-dk增大，即工序k工期縮短，則對應(yīng)工序-k可能出現(xiàn)隱性時差和偽時差，根據(jù)式(12)～(13)：

(14)

(15)

2.4 半島工序和孤島工序

*CFk=0

則稱其為“孤島工序”，在執(zhí)行過程中不會與任何工序相互影響。孤島工序的特點(diǎn)使其能夠降低管理(特別是調(diào)度等)方面的難度，若項目中的孤島工序越多，則該項目在處理調(diào)度等問題時難度可能越低。

圖2 反向視角的各類型最小時距

3 應(yīng)用分析

本文提出的GPRs下的新工序概念可為項目調(diào)度提供新思路和方法。結(jié)合節(jié)2.4可知，半島工序和孤島工序可為GPRs下工序?qū)椖空{(diào)度的復(fù)雜程度進(jìn)行分級。例如，孤島工序獨(dú)立于其他工序，調(diào)整時所需考慮的因素最少；干擾工序是導(dǎo)致項目調(diào)度中工序關(guān)系錯綜復(fù)雜的主因，調(diào)整時所需考慮的因素最多。因此，根據(jù)工序類型的不同，可在項目中進(jìn)行復(fù)雜程度劃分，分別用具有對應(yīng)特征和功能的算法進(jìn)行處理，進(jìn)而以此為基礎(chǔ)進(jìn)行算法綜合，設(shè)計出新的混合算法，實現(xiàn)更好的求解效果。

minz

(16)

s.t.

(17)

(18)

(19)

(20)

(21)

(22)

(23)

(24)

(25)

(26)

(27)

(28)

(29)

(30)

(31)

(32)

上述模型中，式(19)～(26)表示工序間優(yōu)先關(guān)系。GPRs下工序間優(yōu)先關(guān)系數(shù)量遠(yuǎn)多于工序數(shù)量，若能鑒別刪減冗余優(yōu)先關(guān)系，可顯著減小模型約束條件，實現(xiàn)模型簡化。以圖3為例，該網(wǎng)絡(luò)所示項目的資源均衡問題。根據(jù)節(jié)2.1，計算工序共用時差，例如，根據(jù)式(8)計算工序2和8的共用時差CF2，8，

因此兩工序沒有共用時差，實際并無約束，可刪去箭線(4，15)；依此類推，得圖4所示網(wǎng)絡(luò)，與圖3相比，表示優(yōu)先關(guān)系的箭線數(shù)量由32減少到6，即模型中優(yōu)先關(guān)系約束條件減少81.25%。圖4顯示有較多半島和孤島工序，弱化了工序間相互影響，只有少數(shù)工序在資源均衡中會影響其他工序，降低了問題求解難度。

4 結(jié)論

工序機(jī)動時間是項目管理的重要優(yōu)化參數(shù)。在基于CPM的項目中，工序機(jī)動時間包括總時差，自由時差，安全時差，共用時差和干擾時差。然而在帶有GPRs的項目中，現(xiàn)有工序機(jī)動時間卻只包括總時差，自由時差和安全時差。隨著現(xiàn)代工程項目的規(guī)模擴(kuò)大化和結(jié)構(gòu)復(fù)雜化，工序間遍布GPRs。工序共用時差和干擾時差能夠體現(xiàn)工序間相互影響的規(guī)律，若合理應(yīng)用有助于減小項目復(fù)雜結(jié)構(gòu)的影響，對于項目管理十分重要。本文重點(diǎn)研究GPRs下的工序共用時差。

GPRs的表示方法與經(jīng)典CPM網(wǎng)絡(luò)相比差異顯著，GPRs下的工序時差難以直接借助CPM方法計算。本文根據(jù)工序共用時差和干擾時差的含義，以GPRs箭線式網(wǎng)絡(luò)為工具，提出相應(yīng)的概念和計算公式。通過分析上述公式及GPRs網(wǎng)絡(luò)結(jié)構(gòu)，發(fā)現(xiàn)具有獨(dú)特性質(zhì)的工序，并提出新的工序概念，如半島工序和孤島工序。這些工序的特性有助于GPRs下項目調(diào)度的更有效求解。本文研究了GPRs下的工序共用時差在資源均衡問題中的應(yīng)用。工序共用時差可以實現(xiàn)資源均衡問題的簡化，主要體現(xiàn)在能刪減冗余優(yōu)先關(guān)系，減小資源均衡模型的規(guī)模。