約束條件下項目進度關鍵路徑的Petri網建模方法

摘 要：針對軟件開發項目因存在約束條件而不能有效使用關鍵路徑法的問題，利用Petri網并行性和異步性的動態特性，設計時延著色Petri網（TCPN）進度模型，通過將雙代號網絡圖映射成Petri網，構建約束條件下的項目執行模型，用模型仿真得到約束條件下項目運行可能出現的情況，再運用關鍵路徑法進行分析。案例結果表明：TCPN進度模型可使用關鍵路徑法預測軟件開發項目的完工時間，獲得項目關鍵路徑信息和其他潛在的關鍵路徑發生概率，并且完工時間預測準確率為92.41%，具有一定的實用價值。

關鍵詞：Petri網;項目管理;資源約束;關鍵路徑;進度管理

中圖分類號：TP391.9 文獻標志碼：A

0 引言（Introduction）

關鍵路徑法（CPM）和計劃評審技術（PERT）[1]雖然能在不考慮約束的唯一項目場景下有效表達活動自身的時間因素以及不同活動之間的邏輯關系，進而確定項目關鍵路徑的完成時間，但是在實際的軟件開發過程中，由于存在資源限制和活動優先級等[2]情況，項目場景不唯一，使用上述方法得到的結果不準確，因此考慮通過設計仿真模型，根據模型仿真出可能出現的項目場景，再基于關鍵路徑法進行求解分析，從而提高完成時間預測的準確性。

Petri網[3]是一種動態可執行系統模型[4]，適合用于研究并行開發的系統問題，而項目管理的活動具有并行性和異步性的離散性特點，因此適合用Petri網研究項目進度模型。李海凌等[5]用分層賦時著色Petri網（HTCPN）模擬資源約束下的項目實施階段的工作流情況，但只考慮了資源約束對項目的影響，不完全適合軟件開發項目;韓耀軍[6]利用Petri網求解項目關鍵路徑，但是沒有考慮約束條件下的情況。

基于時延著色Petri網（TCPN）的進度模型[7]針對軟件開發的特點，利用Petri網構建項目的約束條件，模擬軟件開發項目的執行過程，在多次仿真結果中運用關鍵路徑法，得出約束條件下的軟件項目工期預測和關鍵路徑信息?；赥CPN的進度模型不僅能將關鍵路徑法運用在約束條件下的軟件項目中，而且具有較強的工期預期能力，并能提供更加全面的進度管理信息。

1TCPN進度模型的構建（Construction of TCPNprogress model）

1.1Petri網及其擴展

Petri網是一種用網狀圖形表示的系統模型。原型Petri網將一個網定義為三元組N =（P，T，F），其中P 為庫所的有限集合，在網中用小圓圈表示;T 為變遷的有限集合，在網中用小矩形表示;P∪T=?，P∩T=?;F?（P×T）∪（T×P）∩T 為有向弧的有限集合，在網中用方向箭頭表示，存在于小圓圈和小矩形之間。

在原型Petri網的基礎上增加弧的權函數W ：F→N+ 和初始標識M0：F→T，則形成一個五元組Σ= （P，T，F，W ，M 0）的經典Petri網。經典Petri網具有良好的擴展性，在此基礎上擴展了著色Petri網（Colored Petri Net，CPN）[8]和時延Petri網（Timed Petri Net，TPN）[9]等高級Petri網，增強了Petri網的系統表達能力。

1.2 時延著色Petri網

時延著色Petri網（Timed Colored Petri Net，TCPN）是在經典Petri網的基礎上，結合了著色Petri網和時延Petri網的特點的高級Petri網。

定義1：時延著色Petri網TCPN是一個十元組，TCPN=（P，T，F，W ，R，C，D，E，M ，I）。其中，（P，T，F，W ）為一個原型Petri網。

R 是非空的有限類型的顏色集合（colored sets），定義了不同類型的庫所;

C 是映射到R 的顏色函數（color function），可對庫所中的標識進行標記，以表示不同類型;

D 是時間延遲函數，定義在變遷T 上，標識在變遷T 觸發函數后，進入后續庫所，必須經歷延遲時間D 后，才會離開后續庫所;

E 是弧表達函數，定義在弧F 上，表示標識流動的規則;

M 是標識函數，定義在庫所P 上，表示庫所的標識數量;

I 是抑制弧的集合，表示不同庫所的觸發優先度。

定義2：設x∈P∪T 是網TCPN的任一元素，x 的前集與后集分別記為·x 與x·，則有

·x={y|（y∈P∪T）∩（y，x）∈F）} （1）

x·={z|（z∈P∪T）∩（x，z）∈F）} （2）

定義3：TCPN具有以下變遷引發規則。t∈T，若?p∈·x：M （p）≥1，則變遷t 在標識M 下使能，記作M [tgt;。

若M [tgt;，則在標識M 下t 能夠觸發，并且觸發后產生新標識M'，記作M [tgt;M'，其中[10]

1.3 雙代號網絡圖向基于TCPN的進度模型的映射

1.3.1 活動網絡映射

雙代號網絡圖是由代表節點的圓圈和代表活動的有向弧連接形成的邏輯關系圖。

在基于TCPN的進度模型中定義節點庫所PN，用于映射雙代號網絡圖中的圓圈節點，記PN={P1，P2，…，Pm}（mgt;0）。

定義活動庫所PS 表示具體的活動本身，記PS={S1，S2，…，Sn}（ngt;0）;定義啟動活動變遷TS 帶有時間延遲函數，記TS={t1s，t2s，…，tns}（ngt;0）;定義結束活動變遷TE，記TE={t1e，t2e，…，tne}（ngt;0）。將由活動庫所PS、啟動活動變遷TS 和結束活動變遷TE 組成的活動單元用于映射雙代號網絡圖中代表活動的有向弧。

過渡變遷Tr 用于連接節點庫所，記Tr={tr1，tr2，…，trn}（ngt;0）。

用有向弧將節點庫所PN 、活動單元和過渡變遷Tr 連接起來，得到基于TCPN的進度模型的網絡圖。雙代號網絡圖向基于TCPN的進度模型的映射關系如圖1所示。

1.3.2 活動的持續時間映射

活動單元的持續時間由啟動活動變遷上的時間延遲函數D 決定。PERT的活動持續時間是根據概率分布發生的，是一種非固定持續時間，通過將D 定義為非固定持續時間函數，可以將PERT的思想運用在基于TCPN的進度模型中。

基于TCPN 的進度模型的持續時間確定方法借鑒了PERT的三點估算方法，定義了期望完成時間、樂觀估計時間和悲觀完成時間3種完成時間，活動單元的持續時間將在由以上3個時間點所構成的時間區間中隨機取值，非固定時間延遲函數的分布函數u（x）如下[11]：

其中：a 是期望完成時間，b 是樂觀估計時間，c 是悲觀完成時間。

1.3.3 活動之間邏輯關系映射

雙代號網絡圖中定義了4種活動之間的邏輯關系[12]，分別為完成-開始（FS）、開始-開始（SS）、完成-完成（FF）和開始-完成（SF），映射到基于TCPN 的進度模型中的關系如圖2所示。

基于TCPN的進度模型通過將活動單元按邏輯關系連接起來形成進度網絡模型?；赥CPN的進度模型中的各活動單元是經過WBS（Work Breakdown Structure）分解后的最小工作單元。

2 基于TCPN 的進度模型約束條件的構建（Construction of constraint conditions forTCPN schedule model）

2.1 資源數量約束關系的構建

通過構建資源庫所對資源數量約束關系進行構建。

定義資源庫所PR，記PR={r1，r2，…，rm}（mgt;0），資源庫所PR 中的初始標識數代表項目所有可分配的人力資源，一類資源庫所代表一類資源。從資源庫所出來的有向弧連接到相應的啟動活動變遷上，對于變遷t∈TS，?PN ∈·x：M （p）≥1和?PR∈x：M （r）≥1時，啟動活動變遷使能。啟動活動變遷觸發后產生新標識進入活動庫所，表示任務處于執行狀態?；顒訋焖械臉俗R經過函數D 的滯留時間后，觸發結束活動變遷，產生保留時間信息的人力資源標識和進度標識的2種標識，其中人力資源標識會回到資源庫所，表示資源重新進入待機狀態。進度標識會進入后集的節點庫所，表示活動單元已完成。資源數量約束關系的構建規則如圖3所示。

2.2 活動優先級約束關系的構建

在存在資源約束的情況下，優先級約束會改變活動的執行順序，從而進一步影響關鍵路徑的確定。通過約束弧映射活動優先級約束關系。

約束弧在圖形上使用帶有空心圓環的無向弧表示。約束弧空心圓環的一端連接啟動活動變遷，另一端連接節點庫所[13]。只有當約束弧所連接的庫所為空時，即?PN ∈·x：M（p）∈I→M （p）=0，空心圓環所連接的變遷才會被觸發。啟動活動變遷上所連接的約束弧數量即代表活動的優先級關系，啟動活動變遷上的約束弧數量越少，活動優先級越高。圖4表示的優先級關系為活動S1gt;活動S2gt;活動S3。

3 基于TCPN 的進度模型關鍵路徑信息的確定（Critical path information determinationfor TCPN-based schedule models）

3.1 固定持續時間的關鍵路徑信息

CPN Tools是一套針對著色Petri網的編輯、仿真和分析工具[14-15]，在支持CPN圖形化建模的同時，還可以作為模型仿真和監控等分析工具使用[16]。通過CPN Tools中Monitoring功能模塊的Mark Size組件，監控活動單元獲得的日志信息。MarkSize日志信息中time列對應的項目進度信息如表1所示。

根據日志信息可以確定項目的關鍵路徑完成時間和對應關鍵路徑鏈信息。

（1）活動單元的活動總時差TF：

TF=Tlf -Tef （5）

（2）關鍵活動路徑：所有TF=0的活動單元，即關鍵路徑。

（3）關鍵路徑完成時間：日志信息的第四行數據時間。

3.2 非固定持續時間下的關鍵路徑信息

引入非固定持續時間函數，每次仿真的活動單元持續時間結果不同，相應的活動進度信息也會有所變化，因此收集仿真得出的所有數據，通過統計的方式確定非固定持續時間下的關鍵路徑信息如下。

（1）活動單元的活動平均總時差ATF：

（2）關鍵活動路徑：統計仿真的各種關鍵路徑的出現概率，根據概率大小確定主要關鍵路徑和潛在關鍵路徑。

（3）關鍵路徑完成時間：統計仿真的關鍵路徑完成時間頻數，確定各種完成時間和相應的出現概率。

4 案例分析（Case analysis）

4.1 案例TCPN進度模型的建立

某軟件開發項目的功能開發活動工時信息如表2所示，項目組的人員構成信息如表3所示。

基于表2的信息，構建軟件開發項目的雙代號網絡圖（圖5）。使用CPN Tools對此雙代號網絡進行基于TCPN的進度模型建模映射。

CPN Tools建模過程中顏色集和變量的定義如下：

closet PN =productINT*STRING timed;

closet PR=productINT*STRING timed;

closet PS=productINT*STRING timed;

var p：PN ;

var r：PR;

var m：PN ;

var j：PR;

起始節點庫所上的初始標識為（0，“x”），數量為1，表示項目的進度情況;各資源庫所上的初始標識為（n，“string”），表示具體的資源，其中n 為資源編號，“string”為資源名稱，標識數量等同于資源數量。

圖6為建模后的基于TCPN的進度模型，模型中各庫所的含義如表4所示，變遷的含義如表5所示。

4.2 某軟件開發項目關鍵路徑信息的確定

對基于TCPN的進度模型進行110次仿真實驗后，整理活動單元的日志數據得到軟件開發項目的關鍵路徑信息（表6）。

由表6可以看出軟件開發項目可能出現的關鍵路徑有6條，其中關鍵路徑2的出現概率最高，達71.8%，是項目的主要關鍵路徑，其余為潛在的關鍵路徑。

表7為主關鍵路徑完成時間概率分布。

主關鍵路徑活動平均總時差如表8所示，是非關鍵活動在仿真過程中自身所有總時差情況的平均值，表示非關鍵活動即使延遲也不會影響進度的可延遲天數。

本文采用基于TCPN的進度模型計算約束條件限制下，項目關鍵路徑的完成時間及相應的發生概率，結合傳統關鍵路徑法和PERT技術的優勢。若用關鍵鏈技術計算本文列舉案例的完成時間，采用根差法[17]計算緩沖區大小，則可得到本文列舉案例的完成時間為34 d，在基于TCPN的進度模型的計算結果中，項目完成時間為34 d的概率為92.41%。此結果基本可以說明模型在約束條件下的軟件項目完成時間的預測能力，基于TCPN的進度模型能夠得到與傳統關鍵鏈技術接近的結果。

5 結論（Conclusion）

基于TCPN的進度管理模型具有的可執行性建模的特點，使得進度管理可及時響應由環境變化帶來的影響，解決了關鍵路徑法不能有效運用于存在約束條件的軟件開發項目的問題，擴大了關鍵路徑法的應用范圍。與關鍵鏈法相比，基于TCPN的進度管理模型不僅實現了約束條件下的完成時間預測，還實現了關鍵路徑信息的獲取;與傳統的關鍵路徑法相比，擴展了關鍵路徑法的分析維度，可分析得出項目的潛在關鍵路徑信息，為項目進度決策分析增加了風險分析維度，幫助項目管理人員明確軟件項目進度管理的重點，實現約束條件下的有效進度管理，適應敏捷開發的要求。

在后續的研究工作中，將會增加模型中的約束條件類型，使得進度模型能為進度管理決策提供更具有現實意義的信息輸入。

參考文獻（References）

[1] FIGUEROA-GARCíA J C，HERNáNDEZ-PéREZ G，RAMOSCUESTAJ S. Uncertain project network analysis with fuzzy-PERT and Interval Type-2 fuzzy activity durations[J]. Heliyon，2023，9（4）：e14833.

[2] BAO Z K，CHEN L，QIU K J. An aircraft final assemblyline balancing problem considering resource constraints andparallel task scheduling[J]. Computers amp; industrial engineering，2023，182：109436.

[3] SOURAVLAS S，ANASTASIADOU S，KOSTOGLOU I.A novel method for general hierarchical system modelingvia colored petri nets based on transition extractions fromreal datasets[J]. Applied sciences，2022，13（1）：339.

[4] MEJíA G，NI?O K，MONTOYA C，et al. A Petri Netbasedframework for realistic project management andscheduling[J]. Computers and operations research，2016，66（C）：190-198.

[5] 李海凌，劉克劍，施浩然. 基于Petri 網工作流技術的工程項目群管理研究[M]. 北京：機械工業出版社，2018：11.

[6] 韓耀軍. 基于帶標記的并發可達標識圖的關鍵路徑的求解方法[J]. 計算機科學，2016，43（11）：121-125，141.

[7] 鐘賢欣，倪楓，劉姜，等. 基于ROADS的面向場景業務架構建模方法[J]. 上海理工大學學報，2023，45（4）：415-424.

[8] YU W Y，JIA M H，FANG X W，et al. Modeling and analysisof medical resource allocation based on Timed ColoredPetri net[J]. Future generation computer systems，2020，111：368-374.

[9] 吳亞麗，何淑婷，楊延西，等. 基于時延Petri網與BSO的鋁擠壓線排產調度優化[J]. 系統仿真學報，2023，35（1）：178-189.

[10] ZHONG W J，ZHOU J T，SUN T. Concurrent softwarefine-coarse-grained automatic modelling by Coloured PetriNets for model checking[J]. IET software，2023，17（1）：55-75.

[11] 田啟華，祝威，梅月媛，等. 基于模糊理論的并行耦合設計任務工期優化[J]. 制造技術與機床，2018（11）：132-136.

[12] BEVILACQUA M，CIARAPICA F E，GIOVANNI M.Timed coloured petri nets for modelling and managingprocesses and projects[J]. Procedia CIRP，2018，67：58-62.

[13] 張瑋，夏傳良. 基于帶抑制弧的Petri網表示的嵌入式系統模型的子網化簡[J]. 計算機應用與軟件，2022，39（3）：213-217，301.

[14] 黃鳳蘭，倪楓，劉姜，等. 基于ROAD-CPN業務架構的可執行建模方法[J]. 上海理工大學學報，2023，45（5）：534-542.

[15] 王新康，倪楓，劉姜，等. 基于擴展BPMN的“家園互動”式兒童健康管理系統架構[J]. 智能計算機與應用，2022，12（10）：189-199，202.

[16] 喬嘉林，黃向東，楊義繁，等. 基于著色Petri網的HDFS數據一致性建模與分析[J]. 軟件學報，2021，32（10）：2993-3013.

[17] 張向睿，董雄報，向華. 基于Z-number模糊數的管理信息系統開發項目緩沖區研究[J]. 科技管理研究，2019，39（23）：188-195.

作者簡介：

李 鴻（1997-），男，碩士生。研究領域：信息系統項目管理。

倪 楓（1982-），男，博士，副教授。研究領域：系統科學，系統分析與集成。本文通信作者。

劉文誠（2000-），男，碩士生。研究領域：系統建模與仿真，大數據分析。

劉 姜（1983-），女，博士，副教授。研究領域：復雜系統理論與方法，符號代數計算。

陳年年（2003-），女，本科生。研究領域：管理科學與工程。

周興郡（2003-），女，本科生。研究領域：管理科學與工程。

基金項目：國家自然科學基金資助項目（12371508）;教育部產學合作協同育人項目（220603760210846）;上海市“大學生創新創業訓練計劃”資助項目（SH2022072）