搭接網絡中的路長悖論及其特性研究

闞芝南，孔 峰，乞建勛

（1.華北電力大學經濟與管理學院，北京 102206；2.華北電力大學經濟與管理學院，河北保定 071003）

搭接網絡中的路長悖論及其特性研究

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

（1.華北電力大學經濟與管理學院，北京 102206；2.華北電力大學經濟與管理學院，河北保定 071003）

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

搭接網絡；最大路長；機動時間；CPM網絡

1 引言

搭接網絡是在經典的CPM網絡基礎上的發展。在CPM網絡中，主要表達的是工序間嚴格的“結束-開始”型（F-S型）的時間約束，在搭接網絡中，工序間不僅有“結束-開始”型（F-S型）的時間約束，還有“結束-結束”（F-F）、“開始-開始”（S-S）、“開始-結束”（S-F）型的時間約束。用一句話來概括，CPM網絡表示的是不含交叉作業的計劃而搭接網絡表示的是帶有交叉作業的計劃，因而搭接網絡比經典的CPM網絡適用面更廣，更接近于工程的實際。

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

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

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

2 搭接網絡中的時間約束類型及表示方法

最早開始 節點（i）的最早開始ESi是指從節點（i）開始的各項工序最早可能開始工作的時刻。節點（i）的最早開始ESi等于節點（i）的緊前工序最早結束的最大值，用公式表示為ESi=max｛EShi+Thi｝。

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

最遲結束 節點（j）的最遲結束LFj是指以該節點（j）為結束的各項工序最遲必須完成的時刻。節點（j）的最遲結束LFj等于節點（j）的緊后工序最遲開始的最小值，用公式表示為：

LFj=min｛LFjk-Tjk｝

工序（ij）的最遲結束LFij是指指工序（ij）最遲必須結束的時間。工序（ij）的最遲結束LFij等于節點（j）的最遲結束，用公式表示為LFij=LFj

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

LSij=LFi-Tij

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

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

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

FFij=ESjk-EFij=ESj-ESi-Tij

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

SFij=LSij-LFhi=LFj-LFi-Tij

在搭接網絡中搭接關系，主要是通過工序之間各種時間約束來體現的。工序間的搭接關系主要有以下幾種：

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

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

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

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

3 搭接網絡中的“路長悖論”

我們在研究搭接網絡的過程中發現了一個關于路長的悖論：在網絡中加入同一約束的不同表達形式，分別計算出的網絡最大路長不相等。例如，圖1是個普通雙代號CPM網絡計劃圖。

圖1 普通雙代號CPM網絡計劃

圖2 增加時間約束“FAFB”、“SBSC”后的網絡圖

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

圖3 轉化為“FASB”，“FBSC”后的網絡圖

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

但是由圖3可知，網絡的總工期由140天變為250天。為什么同一個約束條件卻得到完全不等的總工期呢？

4 “路長悖論”的分析

在經典的CPM網絡中工序最早計算公式為

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

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

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

圖4 路線μ示意圖

在路線μ上的工序（ab）在前，則（ab）先開始，（ab）結束后，（bi）才能開始，（bi）結束后，（ij）才能開始。所以在一條路線上的工序彼此間都有時間約束。在圖4，可以認為“（ij）工序結束后至少50天，（kr）工序才能開始”，因此這是典型的“結束-開始”型約束：“”。所以CPM網絡是可以表達“結束-開始”型的時間約束的。

在CPM網絡中，不在同一條路線上的工序稱為平行工序，平行工序之間沒有任何時間約束。例如在圖一中，D工序和E工序不在同一條路線上，它們是平行工序，則D和E之間沒有任何時間約束，既不能表示“D結束后E才能結束”又不能表示“E結束后D才能結束”，D和E之間誰先誰后，沒有任何約束。同理，因為圖2中A與B是平行工序，二者不存在任何約束，因此不能滿足“A結束65天B才能結束”這一約束，所以圖2的表示方法不對。相反，在圖3中A與B在同一條路線上，它們之間存在時間約束，表示“A結束后至少35天B才能開始”，因此圖3中的表示方法才是正確的。

所以搭接網絡中所有的“結束-結束”型的時間約束，都需要等價變成“結束-開始”型的時間約束，這樣在CPM網絡中才能正確表達出來。

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

因此搭接網絡中的“開始-開始”型約束，都需要先等價轉化為“結束-開始”型的時間約束，才能用CPM網絡表達這些約束。

同理“開始-結束”型的時間約束也必須轉化為“結束-開始”型時間約束，才能用CPM網絡表示。因為CPM網絡只能表達“結束-開始”型時間約束。

用這種等價轉化的方法表達各種時間約束，既簡單，又能與CPM相統一，但是目前人們都沒有采用這個方法，而是另起爐灶，獨立設計了各種表示方法。這些表示方法雖然多種多樣，但是一個共同點是不能與CPM統一，而在實際應用中人們已經習慣運用CPM的表達方法，換上一種新的表示方法，不僅復雜，還大大影響了它的實用功能。而利用等價轉化的方法就可以克服以上的缺點，十分利于網絡計劃的推廣。

下面給出在搭接網絡中各種約束關系等價轉化為“結束-開始”型時間約束“”的具體公式及證明，供參考：

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

因為FB=SB+TB，所以：

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

得SB-FA≥r-TB

再由（3）式，

式（2）成立。證畢。

式（4）成立。證畢。

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

式（5）成立。證畢。

把各種時間的約束都轉化為“結束-開始”型時間約束后，畫出的CPM網絡圖，成為等價的CPM網絡圖，記為G*。

5 在等價CPM網絡G*中，機動時間與路長的聯系規律

在G*中，實工序、約束工序、虛工序在計算路長和各種事件參數時，都視同為實工序，與在經典的CPM網絡G中，計算各種時間參數時都把虛工序視同為零的實工序一樣。

（1）任意節點（i）與源點（1）之間的任意路線μ1-i上自由時差與路長的聯系規律。

在路μ1-i上各工序的自由時差的和等于節點（i）的最早開始ESi與該路長μ-1-i的差（ESiμ-1-i），即：

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

因（1）是源點，所以ES1=0，又因：

所以：

證畢。

此時的μ1-i稱為節點（i）的前主鏈μ*i。

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

已知

因（w）為匯點，所以ESw=。-證畢。

（2）任意節點（i）與匯點（w）之間的任意路線μi-w上安全時差與路長的關聯規律路線μj-w上各工序的安全時差的和等于匯點（w）的結束時間LFw與該節點（i）的結束時間LFi之差（LFw-LFi）再減去該路長，即：

證明：設任意節點（i）與匯點（w）之間的任意路線段為：

則：

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

因為：

此時的μi-w即為節點（i）的后主鏈。

因μ=μ1-w，則-，當i=1時，。（w）為匯點，所以LFw=。又因（1）為源點，則LF1= 0，證畢。

（3）總時差和路長的關系

任意工序的總時差TFij都等于關鍵路長μ-?與過該工序的最大路長的差（-），即：

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

證明：當TFij=0，由式（12）0，則。

當TFij＞0，由式（12），＞0，

（4）節點時差與路長的關系

任意節點（i）的節點時差TFi都等于關鍵路長與過該節點（i）的最大路長之差（-）。即：

（5）自由時差與路長的關系

任意工序（ij）的自由時差FFij等于過結束節點（j）的最大路長減去過該工序（ij）的最大路長，即：

（6）安全時差與路長的關系

任意工序（ij）的安全時差SFij等于過開始節點（i）的最大路長減去過該工序（ij）的最大路長減去過該工序（ij）的最大路長，即：

6 機動時間與路長的聯系規律的應用——搭接網絡次關鍵路線的求法

在實際的項目進度計劃管理和決策活動中，我們不但需要知道關鍵路線，控制關鍵工序，有時還需要知道網絡中次關鍵路線，因為在次關鍵路線的長與關鍵路線的長度差異很小時，次關鍵路線往往很容易變成關鍵路線。因此在二者路長之差很小時尋找網絡的次關鍵路線，控制好次關鍵路線上的工序也是十分重要的。目前搭接網絡雖應用面十分廣泛，但對于其研究僅僅局限于搭接網絡中時間參數的確定、尋找關鍵路徑、關鍵工序等這類基礎特性的研究，還未見到如何尋找次關鍵路徑與關鍵路徑路長之差的評估，也沒見到求次關鍵路線的簡單算法。本文根據以上推導出的機動時間與路長的聯系規律解決了這一問題，彌補了這一研究的空白，減少了推遲總工期的風險。

（1）自由時差法

①找出關鍵節點的緊前非關鍵工序中，自由時差的最小值FFij，FFij即為網絡關鍵路線μ?與次關鍵路線μ［1］的路長之差（μ?-μ［1］）。

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

③找出工序（ij）開始節點（i）的前主鏈μi*以及結束節點（j）到匯點（w）的關鍵路線段。

圖5 關鍵路線示意圖

圖5中，1-2-3-…-W為網絡的關鍵路線，A1，A2，A3，…，An-1，An為所有關鍵節點的緊前非關鍵工序，則所有的非關鍵路線μ≠μ?必會經過A1，A2，A3，…，An-1，An中的一個工序。

如果經過多個Ai，按最后的Ai計算，則經過Ai的所有非關鍵路線μAi的集合設為｛μAi｝，i=1，2，…，n。那么網絡中所有的非關鍵路線的集合為｛μ/μ

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

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

網絡次關鍵路線與關鍵路線的差值即為找出的緊前非關鍵工序的自由時差值。

設min｛FFA1，FFA2，…，FFAn｝=FFAk=FFuv，則由（6）：。

（2）安全時差法

①找出關鍵節點的緊后非關鍵工序中，自由時差的最小值SFij，SFij即為網絡關鍵路線μ?與次關鍵路線μ［1］的路長之差（μ?-μ［1］）。

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

③找出工序（ij）開始節點（i）到源點（1）的關鍵路線段以及結束節點（j）的后主鏈。

證明：與自由時差法類似，略。

（3）總時差法

①找出關鍵節點的緊前或緊后非關鍵工序中，總時差的最小值T，T即為網絡關鍵路線與次關鍵路線的路長之差。

證明：與自由時差法類似，略。

7 案例

本文以楊冰在《網絡計劃計算的統一》［25］這篇論文中給出的一搭接網絡計劃為例，說明了轉化為CPM形式后的網絡與原網絡求得的各類時間參數一致，運用CPM求解關鍵路線的方法就可以簡便的找出該網絡的關鍵路線，并利用推導出的機動時間與路長的聯系規律判斷出網絡關鍵路線與次關鍵路線的路長之差，并找出網絡的次關鍵路線。

該實例包含有F-F，S-F，S-S，F-S這幾種基本搭接類型，表1給出了搭接網絡計劃的工序間的優先關系及工序工期。

對案例中的約束類型進行處理，將F-F，SF，S-S這三種類型的時間約束等效轉化為F-S型的時間約束，得表2。根據表2的各工序間的優先關系、約束關系及工序工期，繪制CPM網絡計劃圖，并計算時間參數得圖6。得出的CPM網絡計劃圖中的各工序的時間參數與原算例的單代號網絡圖的時間參數均一致，說明了轉化方法是正確的。

表1 工序間的優先關系及工序工期

（1）以工序D為例，驗證機動時間的總時差理論。

工序D的總時差TFD=13-2-6=5，過工序的最長路線為工序A-B-D-F，該路線的路長為10-7+8-9+6+14=22，關鍵路線的長度為27，可以發現，工序D的總時差=關鍵路線的路長減去過工序D的最大路長，即TFD=-，由此驗證了總時差定理的正確性。同理可以驗證其它的機動時間與路長的關聯規律。

表2 將所有約束關系轉化為FˉS型約束后的工序優先關系及工期

（2）以總時差法找出網絡的次關鍵路線。

①找出關鍵節點的緊前或緊后工序中，總時差最小的工序為工序（2，3）總時差為5。可以得知網絡的次關鍵路線與關鍵路線的路長之差為5。

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

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

圖6 計算實例的CPM網絡計劃圖

8 結語

本文發現在CPM網絡中加入搭接關系時，兩工序間加入不同類型的同一時間約束，求出的網絡最大路長會不一致這一悖論現象。通過對CPM網絡中工序間的優先關系進行分析，發現運用CPM網絡計劃表示工序間的搭接關系時，只有將所有的時間約束均轉化為結束-開始型（F-S）的時間約束，才能在CPM網絡中正確表達工序間的搭接關系，并對這種轉化進行了正確性分析與證明。這種轉化方法使得運用CPM網絡計劃技術建立搭接網絡模型變得可行。而目前搭接網絡的研

究中，普遍認可的建模方法是將各種搭接關系轉化為“等效時距”，再用單代號的網絡計劃形式表現出來。對于搭接網絡中工序的時間參數、機動時間、網絡總工期以及關鍵路徑的確定都比較復雜。

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

［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］楊冰.搭接網絡計劃計算模型的改進［J］.中國公路學報，2002，15（1）：116-122.

［19］楊冰.搭接網絡計劃模型分析［J］.北方交通大學學報，2002，26（5）：84-87.

［20］廖鈺.搭接網絡中關鍵鏈的識別方法［D］.武漢：華中科技大學，2007.

［21］夏中煌.實用雙代號搭接網絡［J］.施工技術，1993，22（3）：29-30.

［22］趙鐵生.雙代號搭接施工網絡計劃研究［J］.基建優化，1985，6（4）：55-58.

［23］佟鶴晶，乞建勛.搭接網絡向雙代號網絡的轉化［J］.技術經濟，2009，28（10）：125-128.

［24］閆瑾，張奉舉，閆睿.單代號搭接網絡模糊工期的計算方法［J］.河南城建高等專科學校學報，2000，9（3）：23 -24.

［25］楊冰.網絡計劃計算模型的統一［J］.系統工程理論與實踐，2002，03：51-55.

［26］魏道升，張智洪.搭接網絡計劃在公路和橋梁施工項目管理中的應用［J］.2001，1（3）：48-50.

［27］李金云.搭接網絡計劃時間參數計算方法的改進［J］.建筑科學，2009，21（02）：88-91.

［28］黃彬，孟國勇.工程搭接網絡計劃淺議［J］.大眾科技，2009，14（2）：75-77.

［29］張照煌，梁會森.搭接網絡計劃工作總時差計算方法［J］.應用基礎與工程科學學報，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

國家自然科學基金資助項目（711171079）

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