等效化簡(jiǎn)帶有廣義優(yōu)先關(guān)系的時(shí)間-費(fèi)用權(quán)衡問題

等效化簡(jiǎn)帶有廣義優(yōu)先關(guān)系的時(shí)間-費(fèi)用權(quán)衡問題

蘇志雄1,2，乞建勛1，闞芝南1

(1.華北電力大學(xué)經(jīng)濟(jì)與管理學(xué)院，北京102206；2.南昌工程學(xué)院工商管理學(xué)院，江西南昌330099)

摘要：對(duì)于經(jīng)典的時(shí)間-費(fèi)用權(quán)衡問題，工序之間只存在單一時(shí)間約束，可用CPM網(wǎng)絡(luò)表示。但是對(duì)于工序之間存在多種時(shí)間約束的時(shí)間-費(fèi)用權(quán)衡問題，包括最大和最小時(shí)間約束(稱為廣義優(yōu)先關(guān)系，簡(jiǎn)稱GPRs)，則只能用GPRs網(wǎng)絡(luò)表示，比CPM網(wǎng)絡(luò)復(fù)雜許多。首先，論述了帶有GPRs的時(shí)間-費(fèi)用權(quán)衡問題與經(jīng)典問題的巨大差別：在GPRs中，(1)縮短某些關(guān)鍵工序的工期能使總工期縮短，但縮短另一些關(guān)鍵工序的工期反而能使總工期延長；(2)縮短或延長工序的工期可能會(huì)破壞項(xiàng)目自身的可行性；等。其次，研究了GPRs網(wǎng)絡(luò)的特性，推導(dǎo)出該網(wǎng)絡(luò)的路長定理。第三，根據(jù)該定理，設(shè)計(jì)出等效化簡(jiǎn)帶有GPRs的大型時(shí)間-費(fèi)用權(quán)衡問題的簡(jiǎn)單方法，從而大幅減小求解該問題的難度和計(jì)算量。最后，通過算例演示了該方法。

關(guān)鍵詞：項(xiàng)目調(diào)度；時(shí)間-費(fèi)用權(quán)衡問題；等效化簡(jiǎn)；路長定理；廣義優(yōu)先關(guān)系

收稿日期：2012-09-29

基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目(71171079)

作者簡(jiǎn)介：蘇志雄(1983-)，男，山西朔州人，博士生，研究方向：運(yùn)籌學(xué)，項(xiàng)目進(jìn)度與計(jì)劃管理；乞建勛(1946-)，男，河北邢臺(tái)人，教授，博士生導(dǎo)師，研究方向：運(yùn)籌學(xué)，項(xiàng)目進(jìn)度與計(jì)劃管理；闞芝南(1987-)，女，江蘇揚(yáng)州人，博士生，研究方向：運(yùn)籌學(xué)，項(xiàng)目進(jìn)度與計(jì)劃管理。

中圖分類號(hào)：TB114.1文章標(biāo)識(shí)碼：A

Simplification of Time-cost Tradeoff Problem with Generalized Precedence Relations

SU Zhi-xiong1,2, QI Jian-xun1, KAN Zhi-nan1

(1.SchoolofEconomicandManagement，NorthChinElectricPowerUniversity,Beijing102206,China; 2.BusinessAdministrationCollege,NanchangInstituteofTechnology,Nanchang330099,China)

Abstract:For classic time-cost tradeoff problem, only single time constraint exists between activities, and it could be represented by CPM network. But for time-cost tradeoff problem when multiple time constraints exist between activities, which mainly contain maximal and minimal time constraints and are named as generalized precedence relations(GPRs), it only could be represented by GPRs network which is more complicated than CPM network. Firstly, huge differences between the time-cost tradeoff problem with GPRs and the classic problem are analyzed: under GPRs, (1)compressing durations of some critical activities could compress total duration, but compressing durations of some other ones could prolong the total duration; (2)compressing or prolonging duration of activity may damage feasibility of project etc. Secondly, property of GPRs network is studied, and path length theorem of the network is deduced. Thirdly, according to the theorem, simple algorithm to simplify large scale time-cost tradeoff problem with GPRs is designed for decreasing difficulty and computation greatly of solving the problem. And finally, the algorithm is illustrated by example.

Key words:project scheduling; time-cost tradeoff problem; equivalent simplification; path length theorem; generalized precedence relations(GPRs)

0引言

時(shí)間-費(fèi)用權(quán)衡問題是項(xiàng)目調(diào)度的核心問題。根據(jù)項(xiàng)目中各工序選取工期的區(qū)間是否連續(xù)，經(jīng)典的時(shí)間-費(fèi)用權(quán)衡問題可劃分為連續(xù)型和離散型兩類，其中，離散型時(shí)間-費(fèi)用權(quán)衡問題是NP-hard[1]，目前沒有多項(xiàng)式算法可以求解；對(duì)于連續(xù)型非線性時(shí)間-費(fèi)用權(quán)衡問題，通常先用分段線性函數(shù)近似逼近非線性函數(shù)，然后再求解[2～4]，分段越精細(xì)，逼近效果越好，但是計(jì)算量及難度也越大。因此，求解經(jīng)典時(shí)間-費(fèi)用權(quán)衡問題的最大難點(diǎn)是其高復(fù)雜度和大計(jì)算量，尤其隨著現(xiàn)代科技的飛速發(fā)展，大型工程項(xiàng)目越來越多，所包含的工序均數(shù)以萬計(jì)，所涉及的問題規(guī)模往往都大得驚人。

在經(jīng)典的時(shí)間-費(fèi)用權(quán)衡問題[5,6]中，工序之間只存在單一時(shí)間約束，任意工序只能在其緊前工序全部結(jié)束后才能開始，可用CPM網(wǎng)絡(luò)表示。但在實(shí)際中，工序之間的時(shí)間約束類型很多，任意工序之間、以及工序與項(xiàng)目之間都可能存在時(shí)間約束(參見節(jié)1)，例如，工序A開始后至少3天，工序B才能開始，這是工序A和B之間的一類最小時(shí)間約束；再如，工序A開始后最多5天，工序B必須開始，這是工序A和B之間的一類最大時(shí)間約束。所有時(shí)間約束統(tǒng)稱為廣義優(yōu)先關(guān)系(Generalized Precedence Relations，簡(jiǎn)稱GPRs)。GPRs的多樣性使其無法用CPM網(wǎng)絡(luò)表示，當(dāng)前通用的表示方法稱為GPRs網(wǎng)絡(luò)[7,8]。該網(wǎng)絡(luò)雖然能夠準(zhǔn)確表示所有的時(shí)間約束，但是與CPM網(wǎng)絡(luò)相比要復(fù)雜得多，例如圖1就是一個(gè)只包含3個(gè)工序的GPRs網(wǎng)絡(luò)，其中既有負(fù)權(quán)弧，也有回路，并且不能有正回路，否則表明對(duì)應(yīng)的項(xiàng)目不可行。

圖1　GPRs網(wǎng)絡(luò)

帶有GPRs的時(shí)間-費(fèi)用權(quán)衡問題只能用GPRs網(wǎng)絡(luò)表示，它與CPM網(wǎng)絡(luò)表示的經(jīng)典問題有巨大的不同：(1)在GPRs網(wǎng)絡(luò)中，縮短某些關(guān)鍵工序的工期能使總工期縮短，但縮短另一些關(guān)鍵工序的工期反而能使總工期延長，并且延長某些關(guān)鍵工序的工期也能使總工期縮短，這是與CPM網(wǎng)絡(luò)最根本的差異；(2)GPRs網(wǎng)絡(luò)中存在回路，回路上工序工期的變化可能會(huì)產(chǎn)生正回路，從而導(dǎo)致網(wǎng)絡(luò)即項(xiàng)目不可行，因此帶有GPRs的時(shí)間-費(fèi)用權(quán)衡問題還存在著可行性問題，而CPM網(wǎng)絡(luò)沒有回路，不存在可行性問題。所以，帶有GPRs的時(shí)間-費(fèi)用權(quán)衡問題，其難度遠(yuǎn)遠(yuǎn)大于經(jīng)典的時(shí)間-費(fèi)用權(quán)衡問題。國內(nèi)外學(xué)者對(duì)該問題的研究還相對(duì)較少。Elmaghraby和Kamburowski[7,8]利用GPRs網(wǎng)絡(luò)，將帶有GPRs的時(shí)間-費(fèi)用權(quán)衡問題轉(zhuǎn)化為特殊的最小費(fèi)用流問題；另外他們還發(fā)現(xiàn)GPRs網(wǎng)絡(luò)中存在奇異關(guān)鍵工序，該類工序的工期縮短，總工期反而延長，反之亦然，顛覆了關(guān)鍵工序的傳統(tǒng)觀念和求解問題的傳統(tǒng)思路，進(jìn)一步揭示了帶有GPRs的時(shí)間-費(fèi)用權(quán)衡問題的高難度。Neumann和ZhanI[9]研究了在資源限制條件下，含最小與最大時(shí)間延期約束的項(xiàng)目工期最小化問題，給出了啟發(fā)式方法求解。Sakellaropoulos和Chassiakos[10,11]研究了帶有GPRs的時(shí)間-費(fèi)用權(quán)衡問題，提出用線性/整數(shù)規(guī)劃方法求最佳時(shí)間-費(fèi)用曲線，以及最低成本進(jìn)度。國內(nèi)學(xué)者主要針對(duì)帶有GPRs中最小時(shí)間約束的時(shí)間-費(fèi)用權(quán)衡問題，利用搭接網(wǎng)絡(luò)對(duì)其進(jìn)行研究。吳喚群、唐莉等人[12]研究了搭接施工網(wǎng)絡(luò)的工期優(yōu)化問題，提出相應(yīng)的優(yōu)化算法。楊冰[13]給出了統(tǒng)一計(jì)算經(jīng)典網(wǎng)絡(luò)、搭接網(wǎng)絡(luò)和流水作業(yè)網(wǎng)絡(luò)的時(shí)間參數(shù)的方法。

可見，當(dāng)前對(duì)帶有GPRs的時(shí)間-費(fèi)用權(quán)衡問題的研究主要集中在求解算法上。鑒于該問題的難度，當(dāng)問題規(guī)模很大，或者問題是離散型或非線性連續(xù)型時(shí)，運(yùn)用任何算法求解都將十分困難，因此只通過研究算法試圖實(shí)現(xiàn)對(duì)該問題的有效求解終究是有限的，有必要改變思路，探索新的解決方法。

本文采用對(duì)問題進(jìn)行等效化簡(jiǎn)的思路，找出并去掉求解過程中無需考慮的對(duì)象，既不影響問題的最優(yōu)解，又縮小了問題的規(guī)模，從而降低了求解難度，無論使用任何算法求解都能大幅減小計(jì)算量。

對(duì)于經(jīng)典的時(shí)間-費(fèi)用權(quán)衡問題，文獻(xiàn)[14～17]提出了相應(yīng)的等效化簡(jiǎn)方法，其主要思路是，從路長的角度考慮，若要縮短總工期，只需要縮短CPM網(wǎng)絡(luò)中的較長路線即可，因此只需保留較長路線，而較短路線可以去掉，例如，若要將總工期從100天縮短到95天，則只需將路長大于95的所有路線縮短到95即可，而其余路線均無需考慮。這里暗藏著一個(gè)前提，隨著工序工期的縮短，路線也隨之縮短，因此最初短于95的路線，必然始終短于95。

但是對(duì)于帶有GPRs的時(shí)間-費(fèi)用權(quán)衡問題，由于GPRs網(wǎng)絡(luò)中存在奇異工序，其工期縮短，經(jīng)過該工序的路線反而延長，因此若單從路長的角度考慮，縮短某些工序的工期可能會(huì)使較短路線變長，使得較短路線在問題的求解過程中也需要考慮，即相當(dāng)于網(wǎng)絡(luò)中的所有路線可能都需要考慮，無法等效化簡(jiǎn)。所以，文獻(xiàn)[14～17]的化簡(jiǎn)思路和方法并不完全適用于帶有GPRs的時(shí)間-費(fèi)用權(quán)衡問題。

本文通過分析帶有GPRs的時(shí)間-費(fèi)用權(quán)衡問題的特點(diǎn)，重點(diǎn)研究了GPRs網(wǎng)絡(luò)中的奇異工序，得出了等效化簡(jiǎn)該問題的原理，并以此為依據(jù)設(shè)計(jì)出簡(jiǎn)單的等效化簡(jiǎn)方法。

1GPRs網(wǎng)絡(luò)分析

1.1GPRs網(wǎng)絡(luò)描述

GPRs包含工序之間的“最小”和“最大”兩類時(shí)間約束，具體類型如表1所示。

表1　GPRs的類型

當(dāng)前通用的表示GPRs的GPRs網(wǎng)絡(luò)，其主要特點(diǎn)為：

(1)在工序的表示上，每個(gè)工序k都用兩個(gè)方向相反的弧(i,j)和(j,i)表示，其中，正向弧(i,j)表示工序k的走向，弧權(quán)數(shù)wij為該工序的工期dk，即wij=dk；而反向弧(j,i)與工序k的走向相反，并且弧權(quán)數(shù)wji為該工序工期的相反數(shù)-dk，即wji=-dk；另外，實(shí)工序之間不允許有公共的節(jié)點(diǎn)。

(2)在時(shí)間約束的表示上，用一個(gè)弧表示一個(gè)時(shí)間約束，其中，正向弧表示工序之間的最小時(shí)間約束，其方向與約束關(guān)系同向，弧權(quán)數(shù)為約束值；而反相弧表示工序之間的最大時(shí)間約束，其方向與約束關(guān)系反向，并且弧權(quán)數(shù)為約束值的相反數(shù)。

表2工序之間的GPRs

工序?qū)r(shí)間約束類型時(shí)間約束起點(diǎn),工序1BS0≤s1起點(diǎn),工序2BS0≤s2工序1,2FSSFf1+4≤s2s1+8≤f2工序1,3SSFFs1+1≤s3f3≤f1+3工序2,3FFf2≤f3+7工序5,終點(diǎn)FEf2+1≤T工序7,終點(diǎn)FEf3≤T

鑒于上述特點(diǎn)，GPRs網(wǎng)絡(luò)與表示單一時(shí)間約束的CPM網(wǎng)絡(luò)有很大差別，例如圖1，圖中3個(gè)工序之間的時(shí)間約束如表2所示，其中si表示工序i的開始時(shí)間，fi表示工序i的結(jié)束時(shí)間。

1.2奇異工序

在CPM網(wǎng)絡(luò)中，任意工序的工期如果延長或者縮短，那么經(jīng)過該工序的所有路線長度必然都會(huì)同步延長或者縮短。但是在GPRs網(wǎng)絡(luò)中，會(huì)存在這樣一些工序，它們的工期延長或者縮短后，經(jīng)過它們的路線長度卻不會(huì)隨之同步變化，甚至還會(huì)逆向變化，這些工序就稱為奇異工序。

奇異工序不僅包括逆工序(例如文獻(xiàn)[7,8]發(fā)現(xiàn)的奇異關(guān)鍵工序)，我們還發(fā)現(xiàn)了中性工序。

1.2.1中性工序

GPRs網(wǎng)絡(luò)中，如果某工序的工期不論縮短還是延長，經(jīng)過該工序的某些路線的路長都不變化，則該奇異工序就稱為這些路線的中性工序。

例如，圖1中的工序1就是中性工序，因?yàn)樵摼W(wǎng)絡(luò)中存在著同時(shí)經(jīng)過該工序的正向弧(2,3)和反向弧(3,2)各一次的路線μ=(1)→(2)→(3)→(2)→(6)→(7)→(8)。如果將工序1的工期從2縮短到1，則弧(2,3)的權(quán)數(shù)由2變?yōu)?，即減小1，而弧(3,2)的權(quán)數(shù)由-2變?yōu)?1，即增大1，其它弧的權(quán)數(shù)不變，因此路線μ上所有弧權(quán)數(shù)之和不變，即路長不變，工序1是該路線μ的中性工序。

特別當(dāng)μ是關(guān)鍵路線μ▽時(shí)，工序k就是中性關(guān)鍵工序，其工期無論縮短還是延長，總工期都不變。

1.2.2逆工序

GPRs網(wǎng)絡(luò)中，如果某工序的工期縮短后，經(jīng)過該工序的某些路線反而會(huì)延長；相反，如果該工序的工期延長后，這些路線反而會(huì)縮短，則該奇異工序就稱為這些路線的逆工序。

例如，圖1中的工序1也是逆工序，因?yàn)樵摼W(wǎng)絡(luò)中存在著經(jīng)過該工序的反向弧(3,2)而不經(jīng)過其正向弧(2,3)的路線μ=(1)→(6)→(7)→(3)→(2)→(5)→(8)，如果將工序1的工期從2縮短到1，則弧(3,2)的權(quán)數(shù)就由-2變?yōu)?1，即增大1，并且該路線上其它弧的權(quán)數(shù)沒有變，因此該路線μ的路長也增大1，說明工序1的工期縮短后，路線μ反而延長，工序1是該路線μ的逆工序。

特別當(dāng)μ是關(guān)鍵路線μ▽時(shí)，工序k就是逆關(guān)鍵工序，其工期縮短，總工期必然延長。

2等效化簡(jiǎn)帶有GPRs的時(shí)間-費(fèi)用權(quán)衡問題的原理

時(shí)間-費(fèi)用權(quán)衡問題是指如何用最低的費(fèi)用實(shí)現(xiàn)項(xiàng)目的預(yù)定總工期。由于通常工序的工期越長，費(fèi)用越低，因此，求解該問題的常用方法是，用最低的費(fèi)用將總工期從最長值縮短到預(yù)定值。

對(duì)于帶有GPRs的時(shí)間-費(fèi)用權(quán)衡問題，設(shè)初始GPRs網(wǎng)絡(luò)中，各工序都選用各自的最長工期，且項(xiàng)目可行，總工期為T，若要求將總工期縮短ΔT，為了使問題變得簡(jiǎn)單易解，我們可以先對(duì)問題進(jìn)行等效化簡(jiǎn)，即等效化簡(jiǎn)GPRs網(wǎng)絡(luò)，去掉對(duì)求解過程沒有影響的路線、工序和時(shí)間約束。

由于GPRs網(wǎng)絡(luò)中包含奇異工序，因此等效化簡(jiǎn)該網(wǎng)絡(luò)時(shí)，不能參照文獻(xiàn)[14～17]只從路長的角度考慮。針對(duì)該問題，我們給出了化簡(jiǎn)原理，并將其總結(jié)為以下命題1～4。

由于GPRs網(wǎng)絡(luò)中的工序和時(shí)間約束都由弧表示，為了便于描述，我們?cè)诤竺嬷挥谩盎　钡母拍睢?/p>

命題1等效化簡(jiǎn)帶有GPRs的時(shí)間-費(fèi)用權(quán)衡問題時(shí)，不能只考慮GPRs網(wǎng)絡(luò)中的路長，還必須結(jié)合“每步壓縮中，工序工期的變化對(duì)于總工期的縮短都必須是有效的”這一前提。

證明求解任何時(shí)間-費(fèi)用權(quán)衡問題時(shí)，基本原則之一就是要求每步壓縮必須是有效壓縮，不能使縮短了的總工期再延長，并且壓縮費(fèi)用最低。求解帶有GPRs的時(shí)間-費(fèi)用權(quán)衡問題也同樣遵循該原則。

由于GPRs網(wǎng)絡(luò)中存在奇異工序，使得在壓縮工序工期時(shí)，網(wǎng)絡(luò)中的路線可能縮短，可能延長，也可能不變，無法確定路長始終不大于T-ΔT的路線，因而在求解時(shí)間-費(fèi)用權(quán)衡問題的過程中，所有路線都可能因?yàn)樽兊瞄L于T-ΔT而需要考慮。所以，只從路長的角度考慮無法進(jìn)行化簡(jiǎn)。

但是求解帶有GPRs的時(shí)間-費(fèi)用權(quán)衡問題的本質(zhì)是“用最低的費(fèi)用縮短總工期”，因此必然要求工序工期的每步調(diào)整對(duì)于總工期的縮短都是有效的。我們對(duì)該問題進(jìn)行等效化簡(jiǎn)，并不單是去掉網(wǎng)絡(luò)中的較短路線，其根本目的是簡(jiǎn)化問題的求解過程，而并不改變其本質(zhì)，因此必須在“每步壓縮中，工序工期的變化對(duì)于總工期的縮短都必須是有效的”這一前提下進(jìn)行。

結(jié)合上述前提來考慮GPRs網(wǎng)絡(luò)中的路長，就會(huì)得到全新的結(jié)論，因?yàn)樵撉疤崾轻槍?duì)網(wǎng)絡(luò)整體，而“逆工序”和“中性工序”只是針對(duì)單條路線。在保證該前提下，只要經(jīng)過某弧的所有路線不長于T-ΔT，那么即使受奇異工序的影響，這些路線在壓縮總工期過程中也不會(huì)長于T-ΔT，具體參見命題2和3。

命題2在壓縮總工期的過程中，GPRs網(wǎng)絡(luò)中只有表示工序的弧的權(quán)數(shù)可以改變，而表示時(shí)間約束的弧的權(quán)數(shù)不可以改變，更不會(huì)產(chǎn)生奇異現(xiàn)象。

證明由于工序之間的最大和最小時(shí)間約束都是硬性條件，不可以改變，所以GPRs網(wǎng)絡(luò)中表示這些時(shí)間約束的弧及權(quán)數(shù)也不可以改變，因此，它們的權(quán)數(shù)雖然可能為正，也可能為負(fù)，但是對(duì)所在路線的長度變化沒有影響，更不會(huì)導(dǎo)致奇異現(xiàn)象的產(chǎn)生，在等效化簡(jiǎn)時(shí)，無需將它們進(jìn)行特殊考慮。

命題3在初始GPRs網(wǎng)絡(luò)中，如果經(jīng)過(i,j)弧的所有路線均不長于T-ΔT，那么無論奇異工序存在與否，在“用最低的費(fèi)用將總工期從T縮短到T-ΔT”的過程中，這些路線始終都不會(huì)長于T-ΔT。

證明GPRs網(wǎng)絡(luò)中，實(shí)工序k用權(quán)數(shù)為wuv=dk的正向弧(u,v)和權(quán)數(shù)為wvu=-dk的反向弧(v,u)表示。設(shè)初始網(wǎng)絡(luò)中經(jīng)過弧(i,j)的所有路線均不長于T-ΔT，下面針對(duì)具體情況進(jìn)行分析。

根據(jù)工序的類型，經(jīng)過弧(i,j)的路線最多有3類：不包含奇異工序的路線，包含中性工序的路線，以及包含逆工序的路線。下面我們分別進(jìn)行分析。

(1)如果經(jīng)過弧(i,j)的某路線上沒有奇異工序，則縮短任意工序都只會(huì)使該路線變得更短。

(2)如果經(jīng)過弧(i,j)的某路線上有中性工序k，即該路線經(jīng)過弧(u,v)和(v,u)各一次，縮短該工序的工期不會(huì)使該路線長度發(fā)生變化，而縮短其它工序只會(huì)使其變短，因此該路線必然不會(huì)長于T-ΔT。

(4)如果經(jīng)過弧(i,j)的非最長路線μij上有逆工序k，即μij經(jīng)過工序k的反向弧(v,u)，弧權(quán)數(shù)wvu=-dk，而不經(jīng)過其正向弧(u,v)，弧權(quán)數(shù)wuv=dk，我們也從以下幾方面考慮：

1)若(v,u)=(i,j)，則與(2)-1)情況相同。

2)若(v,u)≠(i,j)，且弧(v,u)所表示的工序k是非關(guān)鍵工序，或者同時(shí)也是中性關(guān)鍵工序或逆關(guān)鍵工序，要實(shí)現(xiàn)“用最低的費(fèi)用縮短總工期”，工序k的工期不能縮短，因此μij始終不會(huì)長于T-ΔT。

圖2　示例圖

3)若(v,u)≠(i,j)，且弧(v,u)所表示的工序k雖是逆工序，但同時(shí)也是非奇異的關(guān)鍵工序，如圖2，粗線表示關(guān)鍵路線，點(diǎn)劃線表示經(jīng)過弧(v,u)的路線μij=…→(i)→(j)→…→(v)→(u)→…→(n)。

結(jié)合(1)～(4)可知，如果經(jīng)過弧(i,j)的所有路線都不長于T-ΔT，那么在“用最低的費(fèi)用將總工期從T縮短到T-ΔT”的過程中，這些路線在任何時(shí)候也都不會(huì)長于T-ΔT。

命題4如果初始GPRs網(wǎng)絡(luò)中經(jīng)過弧(i,j)的最長路線不長于T-ΔT，則該弧可以去掉。

證明如果初始GPRs網(wǎng)絡(luò)中經(jīng)過弧(i,j)的最長路線不長于T-ΔT，則經(jīng)過該弧的所有路線均不長于T-ΔT。根據(jù)命題3，在“用最低的費(fèi)用將總工期從T縮短到T-ΔT”的過程中，這些路線始終不會(huì)長于T-ΔT，因此在求解時(shí)間-費(fèi)用權(quán)衡問題時(shí)，可以通過去掉弧(i,j)，來去掉這些無需考慮的路線。

在上述命題的基礎(chǔ)上，我們就可以只從路長的角度來考慮GPRs網(wǎng)絡(luò)中各弧的取舍，進(jìn)而對(duì)該網(wǎng)絡(luò)以及原問題進(jìn)行等效化簡(jiǎn)。

但是路長問題同樣難度很大，并且是世界性難題。尤其對(duì)于GPRs網(wǎng)絡(luò)，其結(jié)構(gòu)復(fù)雜，回路眾多，還有大量的負(fù)權(quán)弧，若要尋找經(jīng)過任意弧的所有路線，運(yùn)用現(xiàn)有的任何方法都是極其復(fù)雜的，因此如何簡(jiǎn)便有效地尋找路線成為等效化簡(jiǎn)的一大難點(diǎn)，如果不能解決，無疑會(huì)使等效化簡(jiǎn)的效果大打折扣，甚至沒有意義，因?yàn)椤巴ㄟ^等效化簡(jiǎn)降低原問題求解難度”的根本目的無法實(shí)現(xiàn)，甚至適得其反。

為了克服上述難點(diǎn)，我們研究了GPRs網(wǎng)絡(luò)的結(jié)構(gòu)特性，揭示了節(jié)點(diǎn)時(shí)間參數(shù)與路長的關(guān)系，總結(jié)為路長定理(參見節(jié)3.2)，根據(jù)該定理，能夠只利用時(shí)間參數(shù)判斷經(jīng)過任意弧的最長路線，進(jìn)而得知所有路線的狀況，無需復(fù)雜的路長計(jì)算，從而能用很簡(jiǎn)單的方法等效化簡(jiǎn)帶有GPRs的時(shí)間-費(fèi)用權(quán)衡問題。

3GPRs網(wǎng)絡(luò)的節(jié)點(diǎn)時(shí)間參數(shù)和路長定理

3.1節(jié)點(diǎn)時(shí)間參數(shù)

(1)

(2)

由于GPRs網(wǎng)絡(luò)中既有負(fù)權(quán)弧，也有回路，所以需借助Ford算法計(jì)算相應(yīng)的路長。

3.2路長定理

(3)

(4)

所以該路線的路長為

(5)

根據(jù)式(1)，起點(diǎn)(1)到節(jié)點(diǎn)(i)的最長路線的路長為

(6)

再根據(jù)式(2)，節(jié)點(diǎn)(j)到終點(diǎn)(n)的最長路線的路長為

(7)

將式(6)和(7)代入式(5)

所以式(3)成立。

同理可證，式(4)成立。

4等效化簡(jiǎn)帶有GPRs的時(shí)間-費(fèi)用權(quán)衡問題的方法

4.1化簡(jiǎn)方法描述

假設(shè)在GPRs網(wǎng)絡(luò)中，各實(shí)工序的初始工期都是各自的最長工期，且網(wǎng)絡(luò)可行。若要求將總工期縮短ΔT，可按如下步驟等效化簡(jiǎn)該問題：

步驟3去掉剩余節(jié)點(diǎn)中沒有與表示“時(shí)間約束”的弧相連的節(jié)點(diǎn)，并去掉與它們相鄰的弧。

4.2方法的正確性證明

根據(jù)節(jié)2的命題1和2，每步壓縮時(shí)，工序工期的變動(dòng)對(duì)于總工期的縮短必須是有效的。再根據(jù)節(jié)2的命題3和4，若經(jīng)過某弧的最長路線不長于T-ΔT，則在總工期以最低的費(fèi)用從T縮短到T-ΔT的過程中，經(jīng)過該弧的所有路線都不會(huì)長于T-ΔT，因而該弧可以去掉不予考慮。

由于L(μ▽)=T，所以

所以節(jié)4.1算法的步驟1和2正確。

在已去掉的弧中，包括表示時(shí)間約束的弧，可能出現(xiàn)這樣的節(jié)點(diǎn)(j)，在與該節(jié)點(diǎn)相連的弧中，只有表示工序的弧(i,j)和(j,i)，而沒有表示時(shí)間約束的弧，并且由于網(wǎng)絡(luò)起點(diǎn)(1)和終點(diǎn)(n)始終存在，該節(jié)點(diǎn)(j)不會(huì)成為網(wǎng)絡(luò)起點(diǎn)或終點(diǎn)，例如圖3所示。很明顯，在圖3中，縮短工序k的工期不會(huì)影響任何路長，因此無需考慮工序k。去掉工序k就是去掉節(jié)點(diǎn)(j)及其相鄰弧。所以節(jié)4.1算法的步驟3正確。

圖3　示例圖

通過上述分析可知，通過節(jié)4.1的算法，去掉的弧都是在求解帶有GPRs的時(shí)間-費(fèi)用權(quán)衡問題時(shí)不需要考慮的冗余弧，不影響問題的最優(yōu)解，因此該算法能夠?qū)崿F(xiàn)對(duì)原問題的等效化簡(jiǎn)。

4.3方法的復(fù)雜性分析

設(shè)GPRs網(wǎng)絡(luò)中共有n個(gè)節(jié)點(diǎn)，m個(gè)弧，m>n。

所以節(jié)4.1算法的復(fù)雜度為O(m)。

5應(yīng)用舉例

圖4表示工序之間帶有GPRs的工程項(xiàng)目網(wǎng)絡(luò)圖，如果要求將該項(xiàng)目當(dāng)前的總工期以最低的費(fèi)用縮短2天，試對(duì)該問題進(jìn)行等效化簡(jiǎn)。

圖4　GPRs網(wǎng)絡(luò)

步驟3去掉剩余節(jié)點(diǎn)中沒有與表示“時(shí)間約束”的弧相連的節(jié)點(diǎn)(5),(12)，以及與其相鄰的弧。

化簡(jiǎn)后的網(wǎng)絡(luò)如圖5所示，很顯然，該網(wǎng)絡(luò)比圖4所示的原網(wǎng)絡(luò)要簡(jiǎn)單的多，利用該網(wǎng)絡(luò)求解相應(yīng)的時(shí)間-費(fèi)用權(quán)衡問題無疑會(huì)便利許多。

圖5　等效化簡(jiǎn)后的GPRs網(wǎng)絡(luò)

6結(jié)論

對(duì)于工序間帶有GPRs的時(shí)間-費(fèi)用權(quán)衡問題，首先，工序之間以及工序與項(xiàng)目之間的時(shí)間約束無法用CPM網(wǎng)絡(luò)表示，而只能用更為復(fù)雜的GPRs網(wǎng)絡(luò)表示；其次，GPRs網(wǎng)絡(luò)中包含奇異工序，特別是逆關(guān)鍵工序，縮短該工序的工期反而會(huì)使總工期延長，不能再用傳統(tǒng)的思路和方法考慮并求解；再者，GPRs網(wǎng)絡(luò)中存在大量回路，調(diào)整工期時(shí)必須檢驗(yàn)并確保不產(chǎn)生正回路。因此，該問題與經(jīng)典的時(shí)間-費(fèi)用權(quán)衡問題相比，其難度要大得多，目前還沒有足夠簡(jiǎn)便有效的方法可以求解。

針對(duì)該問題，本文研究如何進(jìn)行等效化簡(jiǎn)，找到并去掉求解過程中無需考慮的對(duì)象，包括工序和時(shí)間約束，從而大幅減小問題規(guī)模，降低求解難度。需要強(qiáng)調(diào)的是，由于奇異工序顛覆了人們對(duì)工序特別是關(guān)鍵工序的傳統(tǒng)認(rèn)識(shí)，因此對(duì)待該類工序不能再用已有的思路和方法，否則必然導(dǎo)致錯(cuò)誤的結(jié)果。

本文首先分析了帶有GPRs的時(shí)間-費(fèi)用權(quán)衡問題的特點(diǎn)，將GPRs網(wǎng)絡(luò)中的奇異工序作為重點(diǎn)考慮對(duì)象，給出了等效化簡(jiǎn)該問題的原理；其次，分析了GPRs網(wǎng)絡(luò)中的時(shí)間參數(shù)，揭示了它們與相應(yīng)路線長度之間的關(guān)系，總結(jié)出路長定理；再次，根據(jù)等效化簡(jiǎn)原理和路長定理，設(shè)計(jì)出等效化簡(jiǎn)帶有GPRs的時(shí)間-費(fèi)用權(quán)衡問題的簡(jiǎn)單方法，并分析了方法的正確性和復(fù)雜性，其復(fù)雜度為O(m)，m表示網(wǎng)絡(luò)中弧的數(shù)量；最后，通過應(yīng)用舉例，顯示了該化簡(jiǎn)方法的便捷性和有效性。在未來的研究中，我們將在等效化簡(jiǎn)的基礎(chǔ)上，進(jìn)一步研究如何更有效地求解帶有GPRs的時(shí)間-費(fèi)用權(quán)衡問題。

參考文獻(xiàn)：

[1]Prabuddha D, James D, Jay B G, et al. Complexity of the discrete time-cost tradeoff problem for project networks[J]. Operations Research, 1997, 45(2): 302-306.

[2]Falk J E, Horowitz, J L. Critical path problem with concave cost-time curve[J]. Management Science, 1972, 19(4): 446-455.

[3]Kapur K C. An algorithm for the project cost/duration analysis problem with quadratic and convex cost functions [J]. IIE Transactions, 1973, 5(4): 314-322.

[4]Moder J J, Phillips C R, Davis E W. Project management with CPM, PERT and precedence diagramming(3rd edn)[M] . New York: Van Nostrand Reinhold Company, 1983. 64-81.

[5]張靜文,徐渝,柴國榮.項(xiàng)目進(jìn)度中的離散時(shí)間-費(fèi)用決策問題研究[J].系統(tǒng)工程學(xué)報(bào),2007,22(2):122-127.

[6]張靜文,徐渝,何正文,柴國榮.項(xiàng)目調(diào)度中的時(shí)間-費(fèi)用權(quán)衡問題研究綜述[J].管理工程學(xué)報(bào),2007,22(1):92-97.

[7]Elmaghraby S E, Kamburowski J. The analysis of activity networks under generalized precedence relations(GPR)[R]. Parts Ⅰand Ⅱ. OR Reports, 1989. 231-232.

[8]Elmaghraby S E, Kamburowski J. The analysis of activity networks under generalized precedence relations(GPRs)[J]. Management Science, 1992, 38(9): 1245-1263.

[9]Neumann K, Zhan J. Heuristics for the minimum project-duration problem with minimal and maximal time lags under fixed resource constraints[J]. Intell. Manuf. 1995, 6: 145-154.

[10]Sakellaropoulos S, Chassiakos A P. Project time-cost analysis under generalised precedence relations[J]. Advances in Engineering Software, 2004, 35(10): 715-724.

[11]Chassiakos A P, Sakellaropoulos S. Time-cost optimization of construction projects with generalized activity constraints[J]. Journal of Construction Engineering and Management, 2005, 131(10): 1115-1124.

[12]吳喚群,唐莉,孫相軍,等.搭接施工網(wǎng)絡(luò)工期優(yōu)化研究[J].系統(tǒng)工程,2001,19(4):43-46.

[13]楊冰.網(wǎng)絡(luò)計(jì)劃計(jì)算模型的統(tǒng)一[J].系統(tǒng)工程理論與實(shí)踐,2002,3:51-55.

[14]Akkan C, Drexl A, Kimms A. Network decomposition-based benchmark results for the discrete time-cost tradeoff problem[J]. European Journal of Operational Research, 2005, 165(2): 339-358.

[15]乞建勛,李星梅,王強(qiáng).等效子網(wǎng)絡(luò)構(gòu)建的理論與方法[J].管理科學(xué)學(xué)報(bào),2010,13(1):40-44.

[16]李星梅,乞建勛,蘇志雄.自由時(shí)差定理與k階次關(guān)鍵路線的求法[J].管理科學(xué)學(xué)報(bào),2009,12(2):98-104.

[17]乞建勛,張立輝,李星梅.網(wǎng)絡(luò)計(jì)劃管理中的機(jī)動(dòng)時(shí)間特性及其應(yīng)用[M].北京:科學(xué)出版社,2009.82-112.