歐立雄，陳照魯

(西北工業(yè)大學管理學院，西安710129)

引言

區(qū)間算法最早由摩爾(R.E.Moore)于20世紀50年代末提出，區(qū)間算法主要通過定義一系列在區(qū)間上的運算法則如區(qū)間加法、區(qū)間減法、求最大、最小值等運算來進行區(qū)間上的運算，其初衷是為了提高計算結(jié)果的可靠性。一開始主要運用于取代浮點算法運用于計算機的數(shù)字存儲方面。例如一個實數(shù)x，在計算機中實際上是用一個區(qū)間［］來表達的。區(qū)間算法與傳統(tǒng)的算法有著不同的性質(zhì)，區(qū)間算法的加減法是不可逆的即:A+B-B≠A。區(qū)間本身具有集合的屬性，區(qū)間之間可以進行集合運算，而且實踐中許多參數(shù)也只能用區(qū)間來表示。許多基于區(qū)間算法的新的計算方法能夠可靠地解決一些傳統(tǒng)方法難以解決的問題。如:求解非線性方程組在指定區(qū)域內(nèi)的所有數(shù)值解。

對于研發(fā)型項目，由于其工序工期具有很大的不確定性，有些工序只能大概知道一個可能的工期區(qū)間。面對這樣的問題，有學者提出模糊關(guān)鍵路徑法［1］來對這一類型的項目進行計劃和控制。這種方法在計算各工序的最早開始時間、最遲時間和松弛時間時，使用了模糊減法運算［1］，很好地解決了研發(fā)型項目中工序時間不確定性較大的問題，但這樣的模糊減法運算在某些情況下，其減法的結(jié)果可能為負值，這一現(xiàn)象的存在使模糊運算失去了意義。為了解決這一難題，學者Chanas在其論文中［3～5］給出了區(qū)間工期的網(wǎng)絡圖關(guān)鍵路徑和關(guān)鍵工序的定義及判定定理，并進一步證明了判定某一工序的可能關(guān)鍵性是一個NP完全問題，計算給定工序的浮動時間界限是NP難的(和求解 NP完全問題一樣困難)。另外，Dubois在其論文中［6］提出了計算區(qū)間工期的串—并網(wǎng)絡圖的時間參數(shù)啟發(fā)式算法，并將其推廣到模糊計劃網(wǎng)絡中。Zielinki也在其論文中［7］給出了區(qū)間工期的一般性網(wǎng)絡圖中計算時間參數(shù)的算法，并提出通過浮動時間的值來判別工序是否關(guān)鍵的思想。該類方法一定程度解決了研發(fā)型項目面對工序工期不確定時的計劃制定問題，但目前仍存在著算法復雜度高，浮動時間計算不精確等問題。

目前存在的區(qū)間算法里其基本思想是在定義了相應的區(qū)間算法后，類比傳統(tǒng)的CPM的方法來計算項目網(wǎng)絡圖中各個工序及節(jié)點最早開始時間、最遲開始時間。在用逆推法求取工序的最遲開始時間時，因為對項目工序的取值區(qū)間沒有必要的限定，這樣如果某一個或幾個工序的工期取值區(qū)間過大，就很有可能會出現(xiàn)運算結(jié)果為負值的情況。而且過大的工序工期取值區(qū)間會使最終求得的項目完工時間區(qū)間也變得非常大，這樣運算結(jié)果也就相應的沒有什么意義。因此本文同樣在已有的區(qū)間算法的基礎上進一步增加限定條件，要求網(wǎng)絡圖中每一個工序其工期的估計區(qū)間的跨度不超過其區(qū)間的下界。即對工序工期的估計要求一定的精度。如工序區(qū)間［3 6］在本方法中是可以接受的估計精度。而工序區(qū)間［3 7］是不可以接受的估計精度。并在用逆向遞推法計算工序最遲開始時間下界時進行必要的修正，來抵消因為區(qū)間減法的一直進行而使運算結(jié)果不斷變小甚至變成負值的趨勢，這樣再通過增強條件要求就可以有效地避免在用逆推法求取工序最遲開始時間區(qū)間時出現(xiàn)的令整個算法失效的負值。

一、算法的基本思想

本算法主要是在傳統(tǒng)的關(guān)鍵路徑法的思想基礎上發(fā)展而來，類比傳統(tǒng)關(guān)鍵路徑法求取網(wǎng)絡圖中各工序及節(jié)點的最早開始時間、最遲開始時間的思想，通過定義一系列在區(qū)間上的加減法、求取最大值最小值的運算，來求取網(wǎng)絡圖中各工序和節(jié)點的最早和最遲開始時間區(qū)間。本算法也是采用從前向后遞推的方式求取網(wǎng)絡圖中各工序和節(jié)點的最早開始時間區(qū)間，然后網(wǎng)絡圖中終點的最遲開始時間區(qū)間等于其最早開始時間區(qū)間，則該項目的結(jié)束時間區(qū)間就是其終點的最早開始時間區(qū)間。再由后向前遞推，求取網(wǎng)絡圖中各工序和節(jié)點的最遲開始時間區(qū)間。然后，由工序的最早開始時間區(qū)間和最遲開始時間區(qū)間來求取網(wǎng)絡圖中各個工序的松弛時間的上限和下限，再由各個工序的松弛時間的上限和下限是否為零來判斷該工序的可能關(guān)鍵性。當找到一條從始點到終點的路徑，該路徑上所有的工序都為關(guān)鍵的，則該路徑就是關(guān)鍵路徑。

二、基于區(qū)間算法的進度計劃方法的定義

本方法研究的研發(fā)型項目其網(wǎng)絡圖也必須是一個有向、緊湊、無環(huán)的網(wǎng)絡圖。且只有一個起點和終點。且該網(wǎng)絡圖中各個工序的工期具有區(qū)間活動周期。記網(wǎng)絡的開始點為O，結(jié)束點為V，網(wǎng)絡中的節(jié)點數(shù)為n。記字母i、j、k分別表示網(wǎng)絡圖中任意一個節(jié)點。因為對于網(wǎng)絡圖其始點和終點的最早開始時間和最遲開始時間是相等的。因此在下面的討論中不再討論始點和終點的情況，即:

本方法研究的具有區(qū)間活動周期的項目可以表示為一個有向無環(huán)圖S=(A，D).其中，N={l，2，…，n)為結(jié)點集合，A=N X N 是有向弧(工序)集合，S中只有一個始結(jié)點O和一個終結(jié)點V.對于活動(i，j)∈A，有i＜j。每個活動(i，j)∈A的工序工期區(qū)間為(i，j)≥0。

B(i)表示節(jié)點i的緊前節(jié)點的集合(before);

S(i)表示節(jié)點i的緊后節(jié)點的集合(successor event);

d表示工序某一工期t(i，j)∈T(i，j)的一個環(huán)境，tij(d)表示活動(i，j)在環(huán)境d下的精確活動周期;

R是工序的所有可能工期的環(huán)境集合，為區(qū)間數(shù)T(i，j)的笛卡爾積;

Cij為從結(jié)點i到結(jié)點j的所有路徑的集合(鏈條:chain);

Tc(d)表示某一路徑c在配置d下的路徑長度;

用ES(i，j)表示工序(i，j)的最早開始時間區(qū)間;

用LS(i，j)表示工序(i，j)的最遲開始時間區(qū)間;

定義圖形●為區(qū)間上的加法運算，定義圖形▲為區(qū)間上的減法運算，定義MAX以及MIN在此處表示為區(qū)間數(shù)的取最大值和最小值的運算(完全不同于原來實數(shù)域上的運算)。

三、基于區(qū)間算法的進度計劃方法

類比傳統(tǒng)的網(wǎng)絡圖中工序最早開始時間和最遲結(jié)束時間的求法可知:采用從前向后的遞推方式可求得各活動和結(jié)點的最早開始以及最早結(jié)束時間區(qū)間。采用從后向前的逆推方式可求得各活動和結(jié)點的最遲開始以及最遲結(jié)束時間區(qū)間。

具有區(qū)間活動周期的網(wǎng)絡圖中對于任意一個節(jié)點i，其最早開始時間ES(i)為:

其中k∈B(i)。

具有區(qū)間活動周期的網(wǎng)絡圖中任意一個節(jié)點i最早開始時間區(qū)間計算公式為:

其中k∈B(i)。

具有區(qū)間活動周期的任意一個工序(i，j)最早開始時間區(qū)間計算公式為:

其中k∈B(i)。

具有區(qū)間活動周期的工序(i，j)最遲開始時間區(qū)間計算公式為:

記在某一環(huán)境下活動(i，j)的最遲開始時間為 ls(i，j):

1.對于任意一工序(i，j))的最遲開始時間的上界為:

其中此處的MAXR運算為新定義的一種算法。MAX(A-B)表示分別從區(qū)間A和B中任取兩個數(shù)x、y，然后對x和y的全部可能性差值的求最大運算，其中A、B表示兩個區(qū)間。

3.如果對于任意一工序(i，j))的最遲開始時時間的下界為:S(i，j)，那么對于節(jié)點i的最遲開始時時間的下界為:

4.如果對于任意一個節(jié)點i，記其最遲開始時間的下界為 L-S(i)=X，最早開始時間下界S(k)=Z，工序(k，i)的工期周期的上界i)=y那么對于工序(k，i)其最遲開始時間的下界為:

5.如果工序(i，j)的最遲開始時間為LS(i，j)，記所有以節(jié)點i為起點的工序的集合為M，記所有以節(jié)點i為起點的工序的最遲開始時間區(qū)間的集合為X，則對于節(jié)點i，其最遲開始時間的上界為:

其中內(nèi)層的MIN表示對所有過i節(jié)點的工序的最遲開始時間區(qū)間的求最小值運算。外面的max表示對區(qū)間{MI N(ij)∈M{X}}的求最大值。

7.一個工序(i j)為關(guān)鍵工序當且僅當其松弛時間的上界界(i，j)=0。

9.一個工序(i j)為可能關(guān)鍵工序當且僅當其松弛時間的下界T(i，j)=0。

通過上面判定1到10為基礎，本算法的步驟可表述如下:

步驟一:根據(jù)工序間的邏輯關(guān)系畫出項目的網(wǎng)絡圖，并估計各個工序的工序取值區(qū)間。

步驟二:根據(jù)公式(6)、公式(7)由前往后遞推各個節(jié)點和工序的最早開始時間的區(qū)間。

步驟三:列出網(wǎng)絡圖中所有從始點到終點的路徑。

步驟四:根據(jù)判定1、判定4和判定3、判定5以及公式(8)、公式(9)、由后向前遞推網(wǎng)絡圖中各節(jié)點和工序的最遲開始時間區(qū)間。

步驟五:根據(jù)判定2計算出各個工序松弛時間的上界。

步驟六:根據(jù)判定6計算出各個工序松弛時間的下界。

步驟七:判斷各個工序和始點到終點的路徑的可能關(guān)鍵性，并給出項目的結(jié)束時間區(qū)間。

四、模型驗證

筆者將以某一具體的項目為例通過利用本算法求取該項目網(wǎng)絡圖的完工時間區(qū)間以及可能關(guān)鍵路線來驗證該算法的有效性。

已知該項目的工序工期區(qū)間以及工序的緊前、緊后關(guān)系如表1所示:

表1 工序工期及其相互間的邏輯關(guān)系

步驟一:記項目始點為O，終點為V。根據(jù)項目工序關(guān)系表畫出項目網(wǎng)絡圖，如圖1所示:

圖1 項目網(wǎng)絡圖

步驟二:類比工期固定的網(wǎng)絡圖中求解節(jié)點最早開始時間的方法(CPM)運用公式(6)求解網(wǎng)絡圖中各節(jié)點的最早開始時間區(qū)間(以下為了簡便起見，不再給出具體的運算過程，僅僅為了驗證算法的需要給出最后的計算結(jié)果)。網(wǎng)絡圖中各節(jié)點的最早開始時間區(qū)間為:

網(wǎng)絡圖中各工序的最早開始時間區(qū)間為:

步驟三:網(wǎng)絡圖中所有從始點到終點的路徑有

a-c-e a-d-f b-f三條路徑。

步驟四:網(wǎng)絡圖中各個節(jié)點的最遲開始時間區(qū)間為:

網(wǎng)絡圖中各個工序的最遲開始時間區(qū)間為:

步驟五:計算各個工序的松弛時間下界，根據(jù)判定六可知:本網(wǎng)絡圖中所有工序的松弛時間的下界全為0。

根據(jù)判定2求各個工序的松弛時間上界為:

步驟六:

根據(jù)判定7可知工序a、b為關(guān)鍵工序。

根據(jù)判定8可知該網(wǎng)絡圖不存在關(guān)鍵路徑。

根據(jù)判定9可知該網(wǎng)絡圖的可能關(guān)鍵工序為c、d、e、f。

根據(jù)判定10可知該網(wǎng)絡圖的可能關(guān)鍵鏈為:a-c-e a-d-f b-f三條可能關(guān)鍵路徑。該項目的完工時間區(qū)間為［12 18］。

五、結(jié)論

通過實例計算，可以看出該文提出的基于區(qū)間算法的項目進度計劃方法可以較好地解決工序工期為區(qū)間類型的不確定型的項目的網(wǎng)絡進度計劃的制定問題。對于一些較為簡單的工序工期不確定型的網(wǎng)絡圖，該方法求解效率很高，對于項目規(guī)模較大的此類問題，可根據(jù)上述算法步驟編制相應的計算機程序進行求解，由于本文提出的算法主要利用工序間的緊前緊后關(guān)系，采用了層層遞推的算法，對于層層遞推的算法，用計算機編程是很容易實現(xiàn)的。綜上所述，本文提出的基于區(qū)間算法的項目計劃方法能夠有效求解實際中項目工序工期為區(qū)間類型的不確定性的項目計劃調(diào)度問題，具有一定的理論與實際應用價值。

［1］伊長生.不確定環(huán)境下研發(fā)項目的決策分析［D］.天津:天津大學2006.12.

［2］張宏國，徐曉飛，戰(zhàn)德臣.具有不精確活動周期的網(wǎng)絡計劃方法［J］自動化學報，2008，34(9):1178-1184.

［3］Chanas S，Zielinki P，Critical path analysis in the network with fuzzy activity times［J］.Fuzzy Sets and Systems，2001，122(2):195-204.

［4］Chanas S，Zielinki P，On the hardness of evaluating criticality of activities in a plannar network with duration intervals［J］.Operations Research Letters，2003，31(1):53-59.

［5］Chanas S，Dubois D，Zielinki P.On the sure criticality of tasks in activity networks with imprecise durations［J］.IEEE Transactions on Systems，Man，and Cybernetics，Part B:Cybernetics，2002，32(4):393-399.

［6］Dubois D，F(xiàn)addier H，Galvagnon V，On the latest starting times and floats in activity networks with ill-known duration［J］.European Journal of Operational Research，2003，147(2):266-280.

［7］Ziizika P.On computing the latest starting times and floats of activities in a network with imprecise durations［J］.Fuzzy Sets and Systems，2005，150(1):53-76.

［8］A.F.Carazo，Trinidad Gómez，Julián Molina，Alfredo G.Hernández-D íaza， FlorM.Guerreroa， Rafael Caballerob.Solving a comprehensive model for multiobjective project portfolio selection18［J］.Computers ＆Operations Research，2010，37:630-639.

［9］JoséAlberto Araúzo，Javier Pajares，Adolfo Lopez-Paredes Simulating the dynamic scheduling of project portfolios.Simulation Modelling Practice and Theory［J］.Simulation Modelling Practice and Theory.2010，18:1428-1441.

［10］Senay Solak ，John-Paul B.Clarke ，，Ellis L.Johnson，Earl R.Barnes.Decision Support Optimization of R＆Dproject portfolios under endogenous uncertainty［J］.European Journal of Operational Research.2010，207:420-433.

［11］Qi Hao ，Weiming Shen，Yunjiao Xue，Shuying Wang.Task network-based project dynamic scheduling and schedule coordination.Advanced Engineering Informatics.2010，24:417-427.

［12］Moore R，Yang C.Interval Analysis［R］，Technical Document，Lockheed Missiles and Space Division，Number LM SD-285875，1959.

［13］Moore R.Methods and Applications of Interval Analysis［M］. Society for industrial and Applied Mathematics，1979.