搭接網(wǎng)絡(luò)中的路長(zhǎng)悖論及其特性研究

闞芝南，孔 峰，乞建勛

（1.華北電力大學(xué)經(jīng)濟(jì)與管理學(xué)院，北京 102206；2.華北電力大學(xué)經(jīng)濟(jì)與管理學(xué)院，河北保定 071003）

搭接網(wǎng)絡(luò)中的路長(zhǎng)悖論及其特性研究

闞芝南1，孔 峰2，乞建勛1

（1.華北電力大學(xué)經(jīng)濟(jì)與管理學(xué)院，北京 102206；2.華北電力大學(xué)經(jīng)濟(jì)與管理學(xué)院，河北保定 071003）

本文發(fā)現(xiàn)在搭接網(wǎng)絡(luò)中存在“工序間加入不同表現(xiàn)形式的同一時(shí)間約束，可能會(huì)產(chǎn)生不同的最大路長(zhǎng)”這個(gè)悖論。通過(guò)研究此悖論形成原因從而提出搭接網(wǎng)絡(luò)的一種新表示方法。該方法不但與經(jīng)典的CPM網(wǎng)絡(luò)在表示形式上完全統(tǒng)一，而且在求解時(shí)間參數(shù)及關(guān)鍵路線的方法上也保持一致。該新表示法使得CPM網(wǎng)絡(luò)中許多基礎(chǔ)理論可以推廣到搭接網(wǎng)絡(luò)中來(lái)，例如工序的總時(shí)差Tij等于關(guān)鍵路長(zhǎng)與過(guò)該工序（ij）的最大路長(zhǎng)之差（-）；任意一條路線μ上自由時(shí)差的和都等于關(guān)鍵路長(zhǎng)與該條路的路長(zhǎng)之差（-μ-）等。利用這些定理與規(guī)律，本文解決了搭接網(wǎng)絡(luò)中如何正確求解時(shí)間參數(shù)問(wèn)題，提出在搭接網(wǎng)絡(luò)中評(píng)估關(guān)鍵路長(zhǎng)與次關(guān)鍵路長(zhǎng)之差的簡(jiǎn)便方法以及求解搭接網(wǎng)絡(luò)次關(guān)鍵路線的一系列精確算法，并通過(guò)算例表明這些方法在搭接網(wǎng)絡(luò)應(yīng)用中的具有有效性與簡(jiǎn)便性。

搭接網(wǎng)絡(luò)；最大路長(zhǎng)；機(jī)動(dòng)時(shí)間；CPM網(wǎng)絡(luò)

1 引言

搭接網(wǎng)絡(luò)是在經(jīng)典的CPM網(wǎng)絡(luò)基礎(chǔ)上的發(fā)展。在CPM網(wǎng)絡(luò)中，主要表達(dá)的是工序間嚴(yán)格的“結(jié)束-開始”型（F-S型）的時(shí)間約束，在搭接網(wǎng)絡(luò)中，工序間不僅有“結(jié)束-開始”型（F-S型）的時(shí)間約束，還有“結(jié)束-結(jié)束”（F-F）、“開始-開始”（S-S）、“開始-結(jié)束”（S-F）型的時(shí)間約束。用一句話來(lái)概括，CPM網(wǎng)絡(luò)表示的是不含交叉作業(yè)的計(jì)劃而搭接網(wǎng)絡(luò)表示的是帶有交叉作業(yè)的計(jì)劃，因而搭接網(wǎng)絡(luò)比經(jīng)典的CPM網(wǎng)絡(luò)適用面更廣，更接近于工程的實(shí)際。

Crandall［1］在1973年提出搭接網(wǎng)絡(luò)后廣泛吸引了各國(guó)學(xué)者的注意。Bartusch［2］等人在1988年提出，可以對(duì)單代號(hào)的搭接網(wǎng)絡(luò)進(jìn)行標(biāo)準(zhǔn)化轉(zhuǎn)換，即將各種不同的時(shí)間約束均轉(zhuǎn)化為一種時(shí)間約束，例如S-S型時(shí)間約束，并給出了轉(zhuǎn)化的方法。Elmaghraby［3］在1992年提出了搭接網(wǎng)絡(luò)的雙代號(hào)模型，并用數(shù)學(xué)規(guī)劃的方法求解該網(wǎng)絡(luò)中的時(shí)間費(fèi)用權(quán)衡問(wèn)題。1998年以來(lái)，在帶有搭接關(guān)系的網(wǎng)絡(luò)中求解實(shí)際的問(wèn)題成為了研究的熱點(diǎn)。De Reyck等人［4-5］分別提出了解決搭接網(wǎng)絡(luò)中的資源約束下的項(xiàng)目調(diào)度問(wèn)題的分支定界法和解決搭接網(wǎng)絡(luò)中帶有現(xiàn)金流和資源約束的項(xiàng)目調(diào)度問(wèn)題的一種優(yōu)化方法；接著又在1999年時(shí)提出了搭接網(wǎng)絡(luò)中多資源約束下的項(xiàng)目調(diào)度問(wèn)題［6］。解決帶有搭接關(guān)系的資源約束下的項(xiàng)目調(diào)度問(wèn)題的不同啟發(fā)式算法綜述可以參看Brucker［7］。而De Reyck［8］，Schwindt［9］，以及Fest［10］討論了該問(wèn)題的精確算法。Dorndorf［11］提出了一種新型的分支定界法來(lái)解決帶有搭接關(guān)系的資源約束下的項(xiàng)目調(diào)度問(wèn)題。Sakellaropoulos［12］、Chassiakos［13］分析了搭接網(wǎng)絡(luò)中的時(shí)間-費(fèi)用權(quán)衡問(wèn)題。Najafi［14］提出了一種遺傳算法解決帶有現(xiàn)金流的搭接網(wǎng)絡(luò)中的資源約束下的項(xiàng)目調(diào)度問(wèn)題。Bianco等［15-17］不斷的在尋找求解一般優(yōu)先關(guān)系網(wǎng)絡(luò)中的資源約束下的項(xiàng)目調(diào)度問(wèn)題的最短總工期的精確算法。

我國(guó)對(duì)于搭接網(wǎng)絡(luò)的研究比較晚，目前普遍認(rèn)可的搭接網(wǎng)絡(luò)模型主要通過(guò)引入“等效時(shí)距”的概念來(lái)建立單代號(hào)網(wǎng)絡(luò)模型。由于引入了“等效時(shí)距”的概念，該搭接網(wǎng)絡(luò)模型不論在計(jì)算工序的時(shí)間參數(shù)、工序的機(jī)動(dòng)時(shí)間還是網(wǎng)絡(luò)總工期上，甚至在關(guān)鍵路線的確定上，與發(fā)展成熟的CPM方法相比都麻煩了不少。因此我國(guó)目前對(duì)搭接網(wǎng)絡(luò)的研究主要集中于對(duì)搭接網(wǎng)絡(luò)的模型建立方法［18-19］、搭接網(wǎng)絡(luò)中時(shí)間參數(shù)和機(jī)動(dòng)時(shí)間的計(jì)算方法、關(guān)鍵鏈的確定［20］、以及如何用雙代號(hào)網(wǎng)絡(luò)表示搭接網(wǎng)絡(luò)這些基礎(chǔ)問(wèn)題的研究。由于雙代號(hào)網(wǎng)絡(luò)的廣泛應(yīng)用，一些學(xué)者還致力于將建立的單代號(hào)搭接網(wǎng)絡(luò)計(jì)劃轉(zhuǎn)化為雙代號(hào)網(wǎng)絡(luò)計(jì)劃［21-23］。我國(guó)學(xué)者在這方面的論文主要有閆瑾、張奉舉［24］的“單代號(hào)搭接網(wǎng)絡(luò)模糊工期的計(jì)算方法”；楊冰［25］的“網(wǎng)絡(luò)計(jì)劃計(jì)算模型的統(tǒng)一”，魏道升、張智洪［26］的 “搭接網(wǎng)絡(luò)計(jì)劃在公路和橋梁施工項(xiàng)目管理中的應(yīng)用”；李金云［27］的“搭接網(wǎng)絡(luò)計(jì)劃時(shí)間參數(shù)計(jì)算方法的改進(jìn)”；黃彬、孟國(guó)勇［28］的“工程搭接網(wǎng)絡(luò)淺議”；張昭煌、梁會(huì)森［29］的“搭接網(wǎng)絡(luò)計(jì)劃工作總時(shí)差計(jì)算方法”等。

本文發(fā)現(xiàn)當(dāng)在CPM網(wǎng)絡(luò)中增加不同表達(dá)類型的同一搭接關(guān)系時(shí)，會(huì)造成網(wǎng)絡(luò)最大路長(zhǎng)不一致的奇異現(xiàn)象。在對(duì)該奇異現(xiàn)象進(jìn)行研究中，發(fā)現(xiàn)CPM網(wǎng)絡(luò)只能表達(dá)F-S型時(shí)間約束，而不能表達(dá)F-F，SS，S-F型時(shí)間約束，因此在運(yùn)用CPM網(wǎng)絡(luò)技術(shù)建立搭接網(wǎng)絡(luò)模型時(shí)，只有將所有類型的搭接關(guān)系均轉(zhuǎn)化為“結(jié)束-開始”型（F-S）時(shí)間約束才能正確表達(dá)工序與工序間的搭接關(guān)系，本文進(jìn)一步對(duì)這一結(jié)論的正確性做出詳細(xì)的論述與證明。這種新的搭接網(wǎng)絡(luò)模型實(shí)現(xiàn)了CPM網(wǎng)絡(luò)與搭接網(wǎng)絡(luò)表示的統(tǒng)一，因此搭接網(wǎng)絡(luò)中工序時(shí)間參數(shù)的計(jì)算方法、機(jī)動(dòng)時(shí)間大小的計(jì)算，與CPM完全統(tǒng)一，二者使用的計(jì)算公式一樣，求得的值完全一樣，由此解決了總工期和關(guān)鍵路徑的唯一確定問(wèn)題以及時(shí)間參數(shù)簡(jiǎn)單計(jì)算問(wèn)題等目前搭接網(wǎng)絡(luò)研究的熱點(diǎn)問(wèn)題；本文在此基礎(chǔ)上進(jìn)一步對(duì)搭接網(wǎng)絡(luò)的機(jī)動(dòng)時(shí)間特性進(jìn)行了深入的研究，發(fā)現(xiàn)了在搭接網(wǎng)絡(luò)中工序的總時(shí)差Tij等于關(guān)鍵路長(zhǎng)與過(guò)該工序（ij）的最大路長(zhǎng)之差（-）；任意一條路線μ上自由時(shí)差的和都等于關(guān)鍵路長(zhǎng)μ-與該條路的路長(zhǎng)之差（-μ-）等結(jié)論。并利用這些推導(dǎo)出的結(jié)論設(shè)計(jì)了評(píng)估關(guān)鍵路長(zhǎng)與次關(guān)鍵路長(zhǎng)之差的簡(jiǎn)單方法以及尋找網(wǎng)絡(luò)次關(guān)鍵路線的一系列精確算法，使搭接網(wǎng)絡(luò)中的管理風(fēng)險(xiǎn)進(jìn)一步降低并為以后深入的解決搭接網(wǎng)絡(luò)中的各種應(yīng)用問(wèn)題打下了堅(jiān)實(shí)的基礎(chǔ)。

2 搭接網(wǎng)絡(luò)中的時(shí)間約束類型及表示方法

最早開始 節(jié)點(diǎn)（i）的最早開始ESi是指從節(jié)點(diǎn)（i）開始的各項(xiàng)工序最早可能開始工作的時(shí)刻。節(jié)點(diǎn)（i）的最早開始ESi等于節(jié)點(diǎn)（i）的緊前工序最早結(jié)束的最大值，用公式表示為ESi=max｛EShi+Thi｝。

工序（ij）的最早開始ESij是指緊前工序完成之后，工序（ij）可能開始的最早時(shí)間。工序（ij）的最早開始ESij等于節(jié)點(diǎn)（i）的最早開始，用公式表示為ESij=ESi。

最遲結(jié)束 節(jié)點(diǎn)（j）的最遲結(jié)束LFj是指以該節(jié)點(diǎn)（j）為結(jié)束的各項(xiàng)工序最遲必須完成的時(shí)刻。節(jié)點(diǎn)（j）的最遲結(jié)束LFj等于節(jié)點(diǎn)（j）的緊后工序最遲開始的最小值，用公式表示為：

LFj=min｛LFjk-Tjk｝

工序（ij）的最遲結(jié)束LFij是指指工序（ij）最遲必須結(jié)束的時(shí)間。工序（ij）的最遲結(jié)束LFij等于節(jié)點(diǎn)（j）的最遲結(jié)束，用公式表示為L(zhǎng)Fij=LFj

最遲開始 工序（ij）的最遲開始LSij是指工序（ij）最遲必須開始的時(shí)間。其大小為：

LSij=LFi-Tij

最早結(jié)束 工序（ij）的最早結(jié)束EFij是指工序最早可能完成的時(shí)間。工序 （ij）的最早結(jié)束EFij就是它的最早開始時(shí)間加上該工序的工期，用公式表示為EFij=ESi+Tij。

總時(shí)差 工序（ij）的總時(shí)差TFij表示在不影響項(xiàng)目總工期的條件下，各工序的最早開始（結(jié)束）時(shí)間可以推遲的最大時(shí)間間隔。工序（ij）的總時(shí)差TFij等于TFij=LFj-ESi-Tij。

自由時(shí)差 工序的自由時(shí)差是指工序在不影響其緊后工序最早開始前提下，該工序結(jié)束時(shí)間最多可延長(zhǎng)的時(shí)間。工序（ij）的自由時(shí)差FFij等于工序（ij）的最早結(jié)束時(shí)間與其緊后工序的最早開始時(shí)間之差，用公式表示為：

FFij=ESjk-EFij=ESj-ESi-Tij

安全時(shí)差 工序的安全時(shí)差是指工序的緊前工序在最遲結(jié)束時(shí)間結(jié)束時(shí)，該工序不影響總工期時(shí)最多可以延遲的時(shí)間。工序（ij）的安全時(shí)差SFij等于工序（ij）的最遲開始與其緊前工序最遲結(jié)束時(shí)間的差，用公式表示為：

SFij=LSij-LFhi=LFj-LFi-Tij

在搭接網(wǎng)絡(luò)中搭接關(guān)系，主要是通過(guò)工序之間各種時(shí)間約束來(lái)體現(xiàn)的。工序間的搭接關(guān)系主要有以下幾種：

（1）結(jié)束-開始型約束（F-S）表示工序A結(jié)束后至少r天工序B才能夠開始，記為

（2）結(jié)束-結(jié)束型約束（F-F）表示工序A結(jié)束后至少r天工序B才能夠結(jié)束，記為

（3）開始-開始型約束（S-S）表示工序A開始后至少r天工序B才能夠開始，記為

（4）開始-結(jié)束型約束（S-F）表示工序A開始后至少r天工序B才能夠結(jié)束，記為

3 搭接網(wǎng)絡(luò)中的“路長(zhǎng)悖論”

我們?cè)谘芯看罱泳W(wǎng)絡(luò)的過(guò)程中發(fā)現(xiàn)了一個(gè)關(guān)于路長(zhǎng)的悖論：在網(wǎng)絡(luò)中加入同一約束的不同表達(dá)形式，分別計(jì)算出的網(wǎng)絡(luò)最大路長(zhǎng)不相等。例如，圖1是個(gè)普通雙代號(hào)CPM網(wǎng)絡(luò)計(jì)劃圖。

圖1 普通雙代號(hào)CPM網(wǎng)絡(luò)計(jì)劃

圖2 增加時(shí)間約束“FAFB”、“SBSC”后的網(wǎng)絡(luò)圖

圖中，時(shí)間約束我們用點(diǎn)劃線“○-····-→○”表示，我們把這類箭線稱約束工序，時(shí)間約束工序的特點(diǎn)是只消耗時(shí)間但不消耗資源；實(shí)工序用一條實(shí)箭線表示“○→○”，實(shí)工序既消耗時(shí)間又消耗資源；虛工序用虛箭線表示“○-→○”，虛工序既不消耗時(shí)間又不消耗資源，它只代表一種邏輯順序關(guān)系：虛工序的緊前工序全部結(jié)束后，虛工序的緊后工序才能開始。虛工序看做“r=0”的約束工序。由圖2可知，加入時(shí)間約束“FA→—65FB”，“SB→—20SC”之后網(wǎng)絡(luò)的最大路長(zhǎng)為140天?，F(xiàn)在對(duì)增加的約束換成另外一種等價(jià)類型，將原先的F-F型約束和SS型約束均替換為等價(jià)的F-S型約束，如圖3所示，卻與上面圖2中的最大路長(zhǎng)不一致。

圖3 轉(zhuǎn)化為“FASB”，“FBSC”后的網(wǎng)絡(luò)圖

因?yàn)椤癆結(jié)束后至少65天，B工序才能結(jié)束”等價(jià)于“A工序結(jié)束后至少（65-30）=35天，B才能開始”；而“B開始后至少20天，C才能開始”等價(jià)于“B結(jié)束后至少（20+30）=50天，C工序才能開始”。因此將“”替換為“”，“SB”替換為“”是一種等價(jià)變換，圖2與圖3的總工期也應(yīng)當(dāng)相等。

但是由圖3可知，網(wǎng)絡(luò)的總工期由140天變?yōu)?50天。為什么同一個(gè)約束條件卻得到完全不等的總工期呢？

4 “路長(zhǎng)悖論”的分析

在經(jīng)典的CPM網(wǎng)絡(luò)中工序最早計(jì)算公式為

ESij=max｛EFk1i，EFk2i，…，EFkni｝

代表工序（ij）必須在所有的緊前工序（k1i），（k2i），…，（kni）全部結(jié)束后，該工序（ij）才能開始，因此，這種時(shí)間約束是“結(jié)束-開始”型的時(shí)間約束。

因此，在一條路線μ上的工序，前邊的先開始，后面的后開始，例如圖4所示：

圖4 路線μ示意圖

在路線μ上的工序（ab）在前，則（ab）先開始，（ab）結(jié)束后，（bi）才能開始，（bi）結(jié)束后，（ij）才能開始。所以在一條路線上的工序彼此間都有時(shí)間約束。在圖4，可以認(rèn)為“（ij）工序結(jié)束后至少50天，（kr）工序才能開始”，因此這是典型的“結(jié)束-開始”型約束：“”。所以CPM網(wǎng)絡(luò)是可以表達(dá)“結(jié)束-開始”型的時(shí)間約束的。

在CPM網(wǎng)絡(luò)中，不在同一條路線上的工序稱為平行工序，平行工序之間沒(méi)有任何時(shí)間約束。例如在圖一中，D工序和E工序不在同一條路線上，它們是平行工序，則D和E之間沒(méi)有任何時(shí)間約束，既不能表示“D結(jié)束后E才能結(jié)束”又不能表示“E結(jié)束后D才能結(jié)束”，D和E之間誰(shuí)先誰(shuí)后，沒(méi)有任何約束。同理，因?yàn)閳D2中A與B是平行工序，二者不存在任何約束，因此不能滿足“A結(jié)束65天B才能結(jié)束”這一約束，所以圖2的表示方法不對(duì)。相反，在圖3中A與B在同一條路線上，它們之間存在時(shí)間約束，表示“A結(jié)束后至少35天B才能開始”，因此圖3中的表示方法才是正確的。

所以搭接網(wǎng)絡(luò)中所有的“結(jié)束-結(jié)束”型的時(shí)間約束，都需要等價(jià)變成“結(jié)束-開始”型的時(shí)間約束，這樣在CPM網(wǎng)絡(luò)中才能正確表達(dá)出來(lái)。

同理在圖1中，E、F兩工序不在同一條路線上，因此二者之間不存在任何時(shí)間約束，既不表示“E開始后F才能開始”，也不表示“F開始后E才能開始”。因此，在圖2中，B和C不在同一條路線上，所以B和C之間不存在任何約束，因此，圖2無(wú)法表達(dá)“B開始后至少20天C才能開始”這種時(shí)間約束。而在圖3中，等價(jià)轉(zhuǎn)化成“結(jié)束-開始”型約束后的B與C變成了一條路線上的工序，能夠表示“B結(jié)束后50天，C才能開始”，所以圖3的表示方法才是正確的。

因此搭接網(wǎng)絡(luò)中的“開始-開始”型約束，都需要先等價(jià)轉(zhuǎn)化為“結(jié)束-開始”型的時(shí)間約束，才能用CPM網(wǎng)絡(luò)表達(dá)這些約束。

同理“開始-結(jié)束”型的時(shí)間約束也必須轉(zhuǎn)化為“結(jié)束-開始”型時(shí)間約束，才能用CPM網(wǎng)絡(luò)表示。因?yàn)镃PM網(wǎng)絡(luò)只能表達(dá)“結(jié)束-開始”型時(shí)間約束。

用這種等價(jià)轉(zhuǎn)化的方法表達(dá)各種時(shí)間約束，既簡(jiǎn)單，又能與CPM相統(tǒng)一，但是目前人們都沒(méi)有采用這個(gè)方法，而是另起爐灶，獨(dú)立設(shè)計(jì)了各種表示方法。這些表示方法雖然多種多樣，但是一個(gè)共同點(diǎn)是不能與CPM統(tǒng)一，而在實(shí)際應(yīng)用中人們已經(jīng)習(xí)慣運(yùn)用CPM的表達(dá)方法，換上一種新的表示方法，不僅復(fù)雜，還大大影響了它的實(shí)用功能。而利用等價(jià)轉(zhuǎn)化的方法就可以克服以上的缺點(diǎn)，十分利于網(wǎng)絡(luò)計(jì)劃的推廣。

下面給出在搭接網(wǎng)絡(luò)中各種約束關(guān)系等價(jià)轉(zhuǎn)化為“結(jié)束-開始”型時(shí)間約束“”的具體公式及證明，供參考：

證明：“結(jié)束-結(jié)束”型最小約束FA→—rFB，表示工序A結(jié)束后至少r天，工序B才能結(jié)束，即：

因?yàn)镕B=SB+TB，所以：

FB-FA=（SB+TB）-FA≥r

得SB-FA≥r-TB

再由（3）式，

式（2）成立。證畢。

式（4）成立。證畢。

證明：“開始-結(jié)束”型最小時(shí)間約束，記為“SA”，表示工序A開始后至少r天，工序B才能結(jié)束，即SB-FA≥r

式（5）成立。證畢。

把各種時(shí)間的約束都轉(zhuǎn)化為“結(jié)束-開始”型時(shí)間約束后，畫出的CPM網(wǎng)絡(luò)圖，成為等價(jià)的CPM網(wǎng)絡(luò)圖，記為G*。

5 在等價(jià)CPM網(wǎng)絡(luò)G*中，機(jī)動(dòng)時(shí)間與路長(zhǎng)的聯(lián)系規(guī)律

在G*中，實(shí)工序、約束工序、虛工序在計(jì)算路長(zhǎng)和各種事件參數(shù)時(shí)，都視同為實(shí)工序，與在經(jīng)典的CPM網(wǎng)絡(luò)G中，計(jì)算各種時(shí)間參數(shù)時(shí)都把虛工序視同為零的實(shí)工序一樣。

（1）任意節(jié)點(diǎn)（i）與源點(diǎn)（1）之間的任意路線μ1-i上自由時(shí)差與路長(zhǎng)的聯(lián)系規(guī)律。

在路μ1-i上各工序的自由時(shí)差的和等于節(jié)點(diǎn)（i）的最早開始ESi與該路長(zhǎng)μ-1-i的差（ESiμ-1-i），即：

證明：設(shè)μ（1，i）=（1）→（a）→（b）→（c）→…→（f）→（g）→（h）→（i）則：

因（1）是源點(diǎn)，所以ES1=0，又因：

所以：

證畢。

此時(shí)的μ1-i稱為節(jié)點(diǎn)（i）的前主鏈μ*i。

證明：在式（6）中令μ1-i=μ*i得：

已知

因（w）為匯點(diǎn)，所以ESw=。-證畢。

（2）任意節(jié)點(diǎn)（i）與匯點(diǎn)（w）之間的任意路線μi-w上安全時(shí)差與路長(zhǎng)的關(guān)聯(lián)規(guī)律路線μj-w上各工序的安全時(shí)差的和等于匯點(diǎn)（w）的結(jié)束時(shí)間LFw與該節(jié)點(diǎn)（i）的結(jié)束時(shí)間LFi之差（LFw-LFi）再減去該路長(zhǎng)，即：

證明：設(shè)任意節(jié)點(diǎn)（i）與匯點(diǎn)（w）之間的任意路線段為：

則：

再由定義SFij=LFj-LFi-Tij可得：

因?yàn)椋?/p>

此時(shí)的μi-w即為節(jié)點(diǎn)（i）的后主鏈。

因μ=μ1-w，則-，當(dāng)i=1時(shí)，。（w）為匯點(diǎn)，所以LFw=。又因（1）為源點(diǎn)，則LF1= 0，證畢。

（3）總時(shí)差和路長(zhǎng)的關(guān)系

任意工序的總時(shí)差TFij都等于關(guān)鍵路長(zhǎng)μ-?與過(guò)該工序的最大路長(zhǎng)的差（-），即：

推論5：若TFij=0，則（ij）∈μ?；若TFij＞0，則（ij）?μ?。

證明：當(dāng)TFij=0，由式（12）0，則。

當(dāng)TFij＞0，由式（12），＞0，

（4）節(jié)點(diǎn)時(shí)差與路長(zhǎng)的關(guān)系

任意節(jié)點(diǎn)（i）的節(jié)點(diǎn)時(shí)差TFi都等于關(guān)鍵路長(zhǎng)與過(guò)該節(jié)點(diǎn)（i）的最大路長(zhǎng)之差（-）。即：

（5）自由時(shí)差與路長(zhǎng)的關(guān)系

任意工序（ij）的自由時(shí)差FFij等于過(guò)結(jié)束節(jié)點(diǎn)（j）的最大路長(zhǎng)減去過(guò)該工序（ij）的最大路長(zhǎng)，即：

（6）安全時(shí)差與路長(zhǎng)的關(guān)系

任意工序（ij）的安全時(shí)差SFij等于過(guò)開始節(jié)點(diǎn)（i）的最大路長(zhǎng)減去過(guò)該工序（ij）的最大路長(zhǎng)減去過(guò)該工序（ij）的最大路長(zhǎng)，即：

6 機(jī)動(dòng)時(shí)間與路長(zhǎng)的聯(lián)系規(guī)律的應(yīng)用——搭接網(wǎng)絡(luò)次關(guān)鍵路線的求法

在實(shí)際的項(xiàng)目進(jìn)度計(jì)劃管理和決策活動(dòng)中，我們不但需要知道關(guān)鍵路線，控制關(guān)鍵工序，有時(shí)還需要知道網(wǎng)絡(luò)中次關(guān)鍵路線，因?yàn)樵诖侮P(guān)鍵路線的長(zhǎng)與關(guān)鍵路線的長(zhǎng)度差異很小時(shí)，次關(guān)鍵路線往往很容易變成關(guān)鍵路線。因此在二者路長(zhǎng)之差很小時(shí)尋找網(wǎng)絡(luò)的次關(guān)鍵路線，控制好次關(guān)鍵路線上的工序也是十分重要的。目前搭接網(wǎng)絡(luò)雖應(yīng)用面十分廣泛，但對(duì)于其研究?jī)H僅局限于搭接網(wǎng)絡(luò)中時(shí)間參數(shù)的確定、尋找關(guān)鍵路徑、關(guān)鍵工序等這類基礎(chǔ)特性的研究，還未見到如何尋找次關(guān)鍵路徑與關(guān)鍵路徑路長(zhǎng)之差的評(píng)估，也沒(méi)見到求次關(guān)鍵路線的簡(jiǎn)單算法。本文根據(jù)以上推導(dǎo)出的機(jī)動(dòng)時(shí)間與路長(zhǎng)的聯(lián)系規(guī)律解決了這一問(wèn)題，彌補(bǔ)了這一研究的空白，減少了推遲總工期的風(fēng)險(xiǎn)。

（1）自由時(shí)差法

①找出關(guān)鍵節(jié)點(diǎn)的緊前非關(guān)鍵工序中，自由時(shí)差的最小值FFij，F(xiàn)Fij即為網(wǎng)絡(luò)關(guān)鍵路線μ?與次關(guān)鍵路線μ［1］的路長(zhǎng)之差（μ?-μ［1］）。

②判斷（μ?-μ［1］）的大小，若較小需要找出次關(guān)鍵路線μ［1］則到③，若較大則結(jié)束。

③找出工序（ij）開始節(jié)點(diǎn)（i）的前主鏈μi*以及結(jié)束節(jié)點(diǎn)（j）到匯點(diǎn)（w）的關(guān)鍵路線段。

圖5 關(guān)鍵路線示意圖

圖5中，1-2-3-…-W為網(wǎng)絡(luò)的關(guān)鍵路線，A1，A2，A3，…，An-1，An為所有關(guān)鍵節(jié)點(diǎn)的緊前非關(guān)鍵工序，則所有的非關(guān)鍵路線μ≠μ?必會(huì)經(jīng)過(guò)A1，A2，A3，…，An-1，An中的一個(gè)工序。

如果經(jīng)過(guò)多個(gè)Ai，按最后的Ai計(jì)算，則經(jīng)過(guò)Ai的所有非關(guān)鍵路線μAi的集合設(shè)為｛μAi｝，i=1，2，…，n。那么網(wǎng)絡(luò)中所有的非關(guān)鍵路線的集合為｛μ/μ

設(shè)Ai=（uv），由公式（7）μ-*u≥μ-1-u，公式（10）μ-⊕v≥μ-v-w，有：

又因已知條件（v）∈μ?，所以

網(wǎng)絡(luò)次關(guān)鍵路線與關(guān)鍵路線的差值即為找出的緊前非關(guān)鍵工序的自由時(shí)差值。

設(shè)min｛FFA1，F(xiàn)FA2，…，F(xiàn)FAn｝=FFAk=FFuv，則由（6）：。

（2）安全時(shí)差法

①找出關(guān)鍵節(jié)點(diǎn)的緊后非關(guān)鍵工序中，自由時(shí)差的最小值SFij，SFij即為網(wǎng)絡(luò)關(guān)鍵路線μ?與次關(guān)鍵路線μ［1］的路長(zhǎng)之差（μ?-μ［1］）。

②判斷（μ?-μ［1］）大小，若較小需要找出次關(guān)鍵路線μ［1］則到③，若較大則結(jié)束。

③找出工序（ij）開始節(jié)點(diǎn)（i）到源點(diǎn)（1）的關(guān)鍵路線段以及結(jié)束節(jié)點(diǎn)（j）的后主鏈。

證明：與自由時(shí)差法類似，略。

（3）總時(shí)差法

①找出關(guān)鍵節(jié)點(diǎn)的緊前或緊后非關(guān)鍵工序中，總時(shí)差的最小值T，T即為網(wǎng)絡(luò)關(guān)鍵路線與次關(guān)鍵路線的路長(zhǎng)之差。

證明：與自由時(shí)差法類似，略。

7 案例

本文以楊冰在《網(wǎng)絡(luò)計(jì)劃計(jì)算的統(tǒng)一》［25］這篇論文中給出的一搭接網(wǎng)絡(luò)計(jì)劃為例，說(shuō)明了轉(zhuǎn)化為CPM形式后的網(wǎng)絡(luò)與原網(wǎng)絡(luò)求得的各類時(shí)間參數(shù)一致，運(yùn)用CPM求解關(guān)鍵路線的方法就可以簡(jiǎn)便的找出該網(wǎng)絡(luò)的關(guān)鍵路線，并利用推導(dǎo)出的機(jī)動(dòng)時(shí)間與路長(zhǎng)的聯(lián)系規(guī)律判斷出網(wǎng)絡(luò)關(guān)鍵路線與次關(guān)鍵路線的路長(zhǎng)之差，并找出網(wǎng)絡(luò)的次關(guān)鍵路線。

該實(shí)例包含有F-F，S-F，S-S，F(xiàn)-S這幾種基本搭接類型，表1給出了搭接網(wǎng)絡(luò)計(jì)劃的工序間的優(yōu)先關(guān)系及工序工期。

對(duì)案例中的約束類型進(jìn)行處理，將F-F，SF，S-S這三種類型的時(shí)間約束等效轉(zhuǎn)化為F-S型的時(shí)間約束，得表2。根據(jù)表2的各工序間的優(yōu)先關(guān)系、約束關(guān)系及工序工期，繪制CPM網(wǎng)絡(luò)計(jì)劃圖，并計(jì)算時(shí)間參數(shù)得圖6。得出的CPM網(wǎng)絡(luò)計(jì)劃圖中的各工序的時(shí)間參數(shù)與原算例的單代號(hào)網(wǎng)絡(luò)圖的時(shí)間參數(shù)均一致，說(shuō)明了轉(zhuǎn)化方法是正確的。

表1 工序間的優(yōu)先關(guān)系及工序工期

（1）以工序D為例，驗(yàn)證機(jī)動(dòng)時(shí)間的總時(shí)差理論。

工序D的總時(shí)差TFD=13-2-6=5，過(guò)工序的最長(zhǎng)路線為工序A-B-D-F，該路線的路長(zhǎng)為10-7+8-9+6+14=22，關(guān)鍵路線的長(zhǎng)度為27，可以發(fā)現(xiàn)，工序D的總時(shí)差=關(guān)鍵路線的路長(zhǎng)減去過(guò)工序D的最大路長(zhǎng)，即TFD=-，由此驗(yàn)證了總時(shí)差定理的正確性。同理可以驗(yàn)證其它的機(jī)動(dòng)時(shí)間與路長(zhǎng)的關(guān)聯(lián)規(guī)律。

表2 將所有約束關(guān)系轉(zhuǎn)化為FˉS型約束后的工序優(yōu)先關(guān)系及工期

（2）以總時(shí)差法找出網(wǎng)絡(luò)的次關(guān)鍵路線。

①找出關(guān)鍵節(jié)點(diǎn)的緊前或緊后工序中，總時(shí)差最小的工序?yàn)楣ば颍?，3）總時(shí)差為5?？梢缘弥W(wǎng)絡(luò)的次關(guān)鍵路線與關(guān)鍵路線的路長(zhǎng)之差為5。

②工序（2，3）的前主鏈為1-2，工序（2，3）的后主鏈為3-5-8-10-12-14。

所以次關(guān)鍵路線μ［1］=（1）→（2）→（3）→（5）→（8）→（10）→（12）→（14）

圖6 計(jì)算實(shí)例的CPM網(wǎng)絡(luò)計(jì)劃圖

8 結(jié)語(yǔ)

本文發(fā)現(xiàn)在CPM網(wǎng)絡(luò)中加入搭接關(guān)系時(shí)，兩工序間加入不同類型的同一時(shí)間約束，求出的網(wǎng)絡(luò)最大路長(zhǎng)會(huì)不一致這一悖論現(xiàn)象。通過(guò)對(duì)CPM網(wǎng)絡(luò)中工序間的優(yōu)先關(guān)系進(jìn)行分析，發(fā)現(xiàn)運(yùn)用CPM網(wǎng)絡(luò)計(jì)劃表示工序間的搭接關(guān)系時(shí)，只有將所有的時(shí)間約束均轉(zhuǎn)化為結(jié)束-開始型（F-S）的時(shí)間約束，才能在CPM網(wǎng)絡(luò)中正確表達(dá)工序間的搭接關(guān)系，并對(duì)這種轉(zhuǎn)化進(jìn)行了正確性分析與證明。這種轉(zhuǎn)化方法使得運(yùn)用CPM網(wǎng)絡(luò)計(jì)劃技術(shù)建立搭接網(wǎng)絡(luò)模型變得可行。而目前搭接網(wǎng)絡(luò)的研

究中，普遍認(rèn)可的建模方法是將各種搭接關(guān)系轉(zhuǎn)化為“等效時(shí)距”，再用單代號(hào)的網(wǎng)絡(luò)計(jì)劃形式表現(xiàn)出來(lái)。對(duì)于搭接網(wǎng)絡(luò)中工序的時(shí)間參數(shù)、機(jī)動(dòng)時(shí)間、網(wǎng)絡(luò)總工期以及關(guān)鍵路徑的確定都比較復(fù)雜。

本文運(yùn)用CPM網(wǎng)絡(luò)計(jì)劃技術(shù)建立起的搭接網(wǎng)絡(luò)模型不僅簡(jiǎn)單方便，還能把已發(fā)展成熟的CPM網(wǎng)絡(luò)計(jì)劃技術(shù)中的成果推廣到搭接網(wǎng)絡(luò)中來(lái)，有效的解決了目前搭接網(wǎng)絡(luò)研究中的基本問(wèn)題。本文在此基礎(chǔ)上證明了“任意工序（ij）的自由時(shí)差FFij等于過(guò)結(jié)束節(jié)點(diǎn) （j）的最大路長(zhǎng)減去過(guò)該工序（ij）的最大路長(zhǎng)”等一系列搭接網(wǎng)絡(luò)中工序機(jī)動(dòng)時(shí)間與路長(zhǎng)的聯(lián)系規(guī)律。利用這些規(guī)律設(shè)計(jì)了評(píng)估關(guān)鍵路長(zhǎng)與次關(guān)鍵路長(zhǎng)之差的簡(jiǎn)單方法以及尋找網(wǎng)絡(luò)次關(guān)鍵路線的一系列精確算法，降低了搭接網(wǎng)絡(luò)中的管理風(fēng)險(xiǎn)，并為以后深入的解決搭接網(wǎng)絡(luò)中的各種應(yīng)用問(wèn)題打下了堅(jiān)實(shí)的基礎(chǔ)。

［1］Crandall K C.1973.Project planning with precedence lead/lag factors［J］.Project Management Quarterly，1973，4：18-27.

［2］Bartusch M，Mohring R H，Radermacher F J.Scheduling project networks with resource constraints and time windows［J］.Annals of Operations Research，1988，16（1）：201-240.

［3］Elmaghraby S E，Kamburowski J.The analysis of activity networks under generalized precedence relations（GPRs）［J］.Management Science，1992，38（9）：1245 -1263.

［4］De Reyck B，Herroelen W.A branch-and-bound algorithm for the resource-constrained project scheduling problem with generalized precedence relations［J］.European Journal of Operational Research，1998，111（1）：152 -174.

［5］De Reyck B，Herroelen W.An optimal procedure for the resource-constrained project scheduling problem with discounted cash-flows and generalized precedence relations.［J］Computers and Operations Research， 1998，25（1）：1-17.

［6］De Reyck B，Demeulemeester E，Herroelen W.Algorithms for scheduling projects with generalised precedence relations［M］//WOeglarz J.Project Scheduling-Recent Models，Algorithms and Applications.Boston，MA：Kluwer Academic Publishers，77-105.

［7］Brucker P，Drexl A，MNohring R，et al.Resource-constrained project scheduling：Notation，classification，models，and methods［J］.European Journal of Operational Research，1999，112（1）：3-41.

［8］De Reyck B.Willy Herroelen.The multi-mode resource-constrained project scheduling problem with generalized precedence relations［J］.European Journal of Operational Research，1999，119（2）：538-556.

［9］Schwindt C.A branch-and-bound algorithm for the resource-constrained project duration problem subject to temporal constraints［R］.Technical report，1998.

［10］Fest A R H，MNohring F，Uetz S M.Resource constrained project scheduling with time windows：A branching scheme based on dynamic release dates［R］. Technical report，1999.

［11］Dorndorf U，Pesch E，Phan-Huy T.A time-oriented branch-and-bound algorithm for resource-constrained project scheduling with generalised precedence constraints［J］.Management Science，2000，46（10）：1365 -1384.

［12］Sakellaropoulos S，Chassiakos A P.Project time-cost analysis under generalized precedence relations［J］.Advances in Engineering Software，2004，35：715-724.

［13］Chassiakos A P，Sakellaropoulos S P.Time-cost optimization of construction projects with generalized activity constraints［J］.Journal of Construction Engineering and Management，2005，131（10）：1115-1124.

［14］Najafi A A，Niaki S T A，Shahsavar M.A parametertuned genetic algorithm for the resource investment problem with discounted cash flows and generalized precedence relations［J］.Computers&Operations Research，2009，36（11）：2994-3001.

［15］Bianco L，Caramia M.A new formulation of the resource-unconstrained project scheduling problem with generalized precedence relations to minimize the completion time［J］.Networks，2010，56：263-271.

［16］Bianco L，Caramia M，A new lower bound for the resource-constrained project scheduling problem with generalized precedence relations［J］.Computers&Operations Research，2011，38（1）：14-20.

［17］Bianco L，Caramia M.An exact algorithm to minimize the makespan in project scheduling with scarce re-sources and generalized precedence relations［J］.European Journal of Operational Research，2012，219：73-85.

［18］楊冰.搭接網(wǎng)絡(luò)計(jì)劃計(jì)算模型的改進(jìn)［J］.中國(guó)公路學(xué)報(bào)，2002，15（1）：116-122.

［19］楊冰.搭接網(wǎng)絡(luò)計(jì)劃模型分析［J］.北方交通大學(xué)學(xué)報(bào)，2002，26（5）：84-87.

［20］廖鈺.搭接網(wǎng)絡(luò)中關(guān)鍵鏈的識(shí)別方法［D］.武漢：華中科技大學(xué)，2007.

［21］夏中煌.實(shí)用雙代號(hào)搭接網(wǎng)絡(luò)［J］.施工技術(shù)，1993，22（3）：29-30.

［22］趙鐵生.雙代號(hào)搭接施工網(wǎng)絡(luò)計(jì)劃研究［J］.基建優(yōu)化，1985，6（4）：55-58.

［23］佟鶴晶，乞建勛.搭接網(wǎng)絡(luò)向雙代號(hào)網(wǎng)絡(luò)的轉(zhuǎn)化［J］.技術(shù)經(jīng)濟(jì)，2009，28（10）：125-128.

［24］閆瑾，張奉舉，閆睿.單代號(hào)搭接網(wǎng)絡(luò)模糊工期的計(jì)算方法［J］.河南城建高等?？茖W(xué)校學(xué)報(bào)，2000，9（3）：23 -24.

［25］楊冰.網(wǎng)絡(luò)計(jì)劃計(jì)算模型的統(tǒng)一［J］.系統(tǒng)工程理論與實(shí)踐，2002，03：51-55.

［26］魏道升，張智洪.搭接網(wǎng)絡(luò)計(jì)劃在公路和橋梁施工項(xiàng)目管理中的應(yīng)用［J］.2001，1（3）：48-50.

［27］李金云.搭接網(wǎng)絡(luò)計(jì)劃時(shí)間參數(shù)計(jì)算方法的改進(jìn)［J］.建筑科學(xué)，2009，21（02）：88-91.

［28］黃彬，孟國(guó)勇.工程搭接網(wǎng)絡(luò)計(jì)劃淺議［J］.大眾科技，2009，14（2）：75-77.

［29］張照煌，梁會(huì)森.搭接網(wǎng)絡(luò)計(jì)劃工作總時(shí)差計(jì)算方法［J］.應(yīng)用基礎(chǔ)與工程科學(xué)學(xué)報(bào)，2009，17：151-157.

Tresearch on Path Lengths Paradox and Its Characteristics Under Spliced Network

KAN Zhi-nan1，KONG Feng1，2，QI Jian-xun1
（1.Economics and Management School of North China Electric Power University，Beijing 102206，China；2.Economics and Management School of North China Electric Power University（Baoding），Baoding 071003，China）

A paradox in spliced network is found in this paper，that is when adding a time constraint but in two different types between activities may produce different longest path.A whole new presentation of spliced network is given by studying the paradox.The new spliced network presentation is quite simple but also unified with the classic CPM network in forms.This unification not only helps to solve the problems of how to calculate the time parameters，activity floats and how to find the critical path in spliced network，but also makes extension of the theory found in CPM network to spliced network becomes possible.For example，the activity total float Tijequals to the critical path lengthminus the longest path lengththrough activity（ij），that is（-）；the sum of activity free float of any pathμequals to the critical path lengthμ-?minus the length of this pathμ-，that is-μ-）.By using these extended theory，three convenient methods are designed to detect the difference of critical and sub-critical path lengths and to find out the sub-critical path.These methods are illustrated both effective and convenient in spliced network applications.

spliced network；longest path；activity floats；CPM network

C931

：A

1003-207（2014）05-0121-10

2012-07-05；

2013-05-06

國(guó)家自然科學(xué)基金資助項(xiàng)目（711171079）

闞芝南（1987-），女（漢族），江蘇揚(yáng)州人，華北電力大學(xué)經(jīng)濟(jì)與管理學(xué)院博士生，研究方向：管理科學(xué)與工程.