楊旭+沈俊鑫

摘要： 通過(guò)分析現(xiàn)有時(shí)延Petri網(wǎng)和時(shí)間Petri網(wǎng)在項(xiàng)目進(jìn)度管理仿真模型的不足，提出基于庫(kù)所時(shí)間約束Petri網(wǎng)的項(xiàng)目進(jìn)度管理模型，該模型具備全局時(shí)鐘特性，不僅能體現(xiàn)工序自身時(shí)間參數(shù)，同時(shí)能對(duì)外部資源等工序外延時(shí)間約束進(jìn)行建模。實(shí)例仿真結(jié)果表明該模型的有效性。

Abstract： This paper presents a project schedule management model based on Place Timing Petri nets， by analyzing the shortcomings of existing models based on timed Petri nets or time Petri nets. The schedule management model based on Place Timing Petri net has the feature of global clock， and not only reflects time parameters of process， but also able to model time constraints of external resources.

關(guān)鍵詞： 資源約束；進(jìn)度優(yōu)化；庫(kù)所時(shí)間約束Petri網(wǎng)

Key words： resource constrained；scheduling optimization；Place Timing Petri net

中圖分類(lèi)號(hào)：TP311.5 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1006-4311（2014）22-0004-04

0 引言

近年來(lái)，越來(lái)越多的組織面臨多項(xiàng)目并行實(shí)施，項(xiàng)目間存在資源競(jìng)爭(zhēng)與共享，資源約束下多項(xiàng)目進(jìn)度優(yōu)化調(diào)度是近幾年來(lái)項(xiàng)目管理研究熱點(diǎn)和難點(diǎn)。傳統(tǒng)網(wǎng)絡(luò)項(xiàng)目管理技術(shù)雖能有效表達(dá)工序自身時(shí)間因素以及工序間的邏輯關(guān)系，但仍然存在網(wǎng)絡(luò)圖過(guò)于復(fù)雜、工序時(shí)間參數(shù)及資源需求估算粗放、忽略外部突發(fā)事件、缺乏項(xiàng)目實(shí)施過(guò)程動(dòng)態(tài)控制等缺點(diǎn)，對(duì)于復(fù)雜多項(xiàng)目缺乏動(dòng)態(tài)管理[1]。Petri網(wǎng)集可視化建模、形式化分析及動(dòng)態(tài)仿真于一體的建模工具，在描述并發(fā)、異步、非確定性或者隨機(jī)性為特征的系統(tǒng)有獨(dú)特的能力，使得Petri網(wǎng)廣泛應(yīng)用于項(xiàng)目進(jìn)度管理建模[2]。

本文在研究現(xiàn)有時(shí)間Petri網(wǎng)在項(xiàng)目進(jìn)度管理模型應(yīng)用基礎(chǔ)上，總結(jié)現(xiàn)有基于時(shí)間Petri網(wǎng)的項(xiàng)目進(jìn)度管理模型優(yōu)缺點(diǎn)，提出基于庫(kù)所時(shí)間約束Petri網(wǎng)的項(xiàng)目進(jìn)度管理模型，該模型能夠?qū)?xiàng)目管理中工序邏輯關(guān)系、時(shí)間約束及資源約束進(jìn)行建模，為項(xiàng)目進(jìn)度管理提供可視化、形式化建模工具。

1 項(xiàng)目進(jìn)度管理研究現(xiàn)狀

1.1 基于網(wǎng)絡(luò)計(jì)劃技術(shù)的項(xiàng)目管理模型研究現(xiàn)狀 傳統(tǒng)項(xiàng)目進(jìn)度管理方法主要有橫道圖和網(wǎng)絡(luò)計(jì)劃技術(shù)兩種。橫道圖直觀(guān)便于理解，但不善于表述工序間復(fù)雜邏輯關(guān)系，使用橫道圖對(duì)大型項(xiàng)目建模后模型龐大，不利于項(xiàng)目控制。網(wǎng)絡(luò)計(jì)劃技術(shù)則能較好地體現(xiàn)工序間邏輯關(guān)系，網(wǎng)絡(luò)計(jì)劃技術(shù)主要有：關(guān)鍵路徑法（Critical Path Method，CPM）、計(jì)劃評(píng)審技術(shù)（Project Evaluation and Review Technique，PERT）以及圖形評(píng)審技術(shù)（Graphic Evaluation and Review Technique，GERT）等。CPM可以有效地確定各項(xiàng)工序的機(jī)動(dòng)時(shí)間以及整個(gè)項(xiàng)目的關(guān)鍵路徑和關(guān)鍵工序，PERT基于概率統(tǒng)計(jì)思想，采用三點(diǎn)估算法確定工序時(shí)間延遲，使得PERT對(duì)工序時(shí)間參數(shù)估算精確度高于CPM方法。GERT在PERT基礎(chǔ)上增加決策點(diǎn)，工序邏輯關(guān)系存在非確定性，可進(jìn)行條件和概率處理。傳統(tǒng)網(wǎng)絡(luò)計(jì)劃技術(shù)已成功應(yīng)用于離線(xiàn)項(xiàng)目進(jìn)度管理，但存在如下限制：

①傳統(tǒng)網(wǎng)絡(luò)計(jì)劃技術(shù)對(duì)項(xiàng)目經(jīng)理要求較高，要求事前能夠準(zhǔn)確給出項(xiàng)目工序，以及準(zhǔn)確估算各項(xiàng)工序所需時(shí)間和資源消耗，同時(shí)假設(shè)所有工序時(shí)間參數(shù)需服從β、γ、正態(tài)或泊松等標(biāo)準(zhǔn)概率分布；

②傳統(tǒng)網(wǎng)絡(luò)計(jì)劃技術(shù)無(wú)法描述外部突發(fā)事件，例如資源短缺、設(shè)備故障等對(duì)項(xiàng)目進(jìn)度調(diào)度的影響，當(dāng)出現(xiàn)外部突發(fā)事件時(shí)，該方法不能及時(shí)、動(dòng)態(tài)調(diào)整項(xiàng)目進(jìn)度調(diào)度方案，缺乏動(dòng)態(tài)性、預(yù)測(cè)性與實(shí)時(shí)性；

③采用傳統(tǒng)網(wǎng)絡(luò)計(jì)劃技術(shù)構(gòu)建的網(wǎng)絡(luò)圖不允許存在回路。

1.2 基于時(shí)間Petri網(wǎng)的項(xiàng)目管理模型研究現(xiàn)狀 項(xiàng)目管理從本質(zhì)上來(lái)說(shuō)就是一個(gè)離散事件動(dòng)態(tài)系統(tǒng)，其特點(diǎn)在于事件發(fā)生在離散的時(shí)間點(diǎn)上，具有并發(fā)、異步和突發(fā)性[3]，Petri網(wǎng)具備直觀(guān)的圖形建模、嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)分析、動(dòng)態(tài)靈活仿真等特性，廣泛應(yīng)用于動(dòng)態(tài)離散異步系統(tǒng)建模[4]。為了解決傳統(tǒng)網(wǎng)絡(luò)計(jì)劃技術(shù)在項(xiàng)目管理中的不足，國(guó)內(nèi)外很多學(xué)者提出了基于Petri網(wǎng)的項(xiàng)目進(jìn)度管理模型。羅亞[5]在傳統(tǒng)PERT圖基礎(chǔ)上添加資源庫(kù)所和活動(dòng)節(jié)點(diǎn)，構(gòu)建基于Petri網(wǎng)的產(chǎn)品生產(chǎn)模型，KJ LIU[6]將Petri網(wǎng)應(yīng)用于軟件項(xiàng)目計(jì)劃管理及變更控制，段波[7]將Petri網(wǎng)應(yīng)用于生產(chǎn)制造系統(tǒng)建模及作業(yè)調(diào)度，陳翔[8]證明了可以將雙代號(hào)網(wǎng)絡(luò)圖映射到Petri網(wǎng)模型。

為了對(duì)傳統(tǒng)網(wǎng)絡(luò)計(jì)劃技術(shù)工序持續(xù)時(shí)間進(jìn)行建模，馬俊等[9]對(duì)傳統(tǒng)Petri工序時(shí)間參數(shù)估算及其分布進(jìn)行改進(jìn)，提出基于時(shí)延Petri網(wǎng)（Timed Petri Net， TdPN）的進(jìn)度管理模型，應(yīng)用于房地產(chǎn)開(kāi)發(fā)進(jìn)度管理。時(shí)延Petri網(wǎng)變遷激發(fā)不是瞬間完成，而是需要經(jīng)過(guò)一個(gè)時(shí)間延遲di。為了允許工序持續(xù)時(shí)間是一個(gè)隨機(jī)變量，沈俊鑫[4，10]在變遷持續(xù)時(shí)間引入隨機(jī)變量，提出基于隨機(jī)Petri網(wǎng)（Stochastic Petri Net， SPN）的項(xiàng)目進(jìn)度管理模型，該模型允許工序持續(xù)時(shí)間di為任意隨機(jī)分布，并證明了當(dāng)di服從λ分布時(shí)，該模型狀態(tài)轉(zhuǎn)移具備馬爾科夫特性。為了表示傳統(tǒng)網(wǎng)絡(luò)計(jì)劃技術(shù)工序最早開(kāi)始時(shí)間ES和最遲開(kāi)始時(shí)間LS，國(guó)內(nèi)外學(xué)者對(duì)時(shí)延Petri網(wǎng)進(jìn)行改進(jìn)，即施加在時(shí)延Petri網(wǎng)變遷上的時(shí)間延遲di為時(shí)延區(qū)間（Tmin，Tmax），提出基于時(shí)間Petri網(wǎng)（Time Petri Net， TPN）的項(xiàng)目進(jìn)度管理模型。宋巍[11]、Berthomieu[12]構(gòu)建基于時(shí)間Petri網(wǎng)的項(xiàng)目進(jìn)度計(jì)劃優(yōu)化模型，宋巍[11]則將時(shí)間Petri網(wǎng)應(yīng)用于項(xiàng)目關(guān)鍵路徑、最短工期求解。為了降低基于時(shí)延Petri網(wǎng)的項(xiàng)目進(jìn)度管理模型復(fù)雜度，實(shí)現(xiàn)大型復(fù)雜項(xiàng)目建模，國(guó)內(nèi)外學(xué)者引入了分層Petri網(wǎng)模型，如滿(mǎn)慶鵬等[13]通過(guò)構(gòu)建基于分層時(shí)間Petri網(wǎng)的分級(jí)施工網(wǎng)絡(luò)計(jì)劃模型，將時(shí)間Petri網(wǎng)應(yīng)用于施工項(xiàng)目網(wǎng)絡(luò)計(jì)劃優(yōu)化。李海凌[14]、FF Cheng[16]、張紹陽(yáng)[1]通過(guò)構(gòu)建基于分層Petri網(wǎng)的資源管理模型，該模型很好地描述了工程建設(shè)項(xiàng)目工序持續(xù)時(shí)間、資源配置及信息傳遞，解決了建設(shè)工程項(xiàng)目實(shí)施階段進(jìn)度、資源優(yōu)化問(wèn)題；該模型采用仿真工序時(shí)間參數(shù)計(jì)算方法，解決了仿真技術(shù)進(jìn)行進(jìn)度計(jì)劃時(shí)不能給出工序時(shí)間參數(shù)的弊端。

大量研究結(jié)果表明，時(shí)間Petri網(wǎng)已廣泛應(yīng)用項(xiàng)目進(jìn)度管理建模，吳哲輝[17]證明了時(shí)間Petri網(wǎng)的模擬能力比傳統(tǒng)Petri網(wǎng)要強(qiáng)，而且時(shí)間Petri網(wǎng)的模擬能力與圖靈機(jī)相等?；跁r(shí)間Petri網(wǎng)的項(xiàng)目進(jìn)度管理模型不僅能夠?qū)⒕W(wǎng)絡(luò)圖映射到時(shí)間Petri網(wǎng)模型，實(shí)現(xiàn)傳統(tǒng)網(wǎng)絡(luò)計(jì)劃技術(shù)所有功能。這類(lèi)模型不僅可以使項(xiàng)目管理者實(shí)時(shí)掌控項(xiàng)目進(jìn)展，控制項(xiàng)目工期，還可以根據(jù)項(xiàng)目實(shí)際執(zhí)行情況對(duì)現(xiàn)有的項(xiàng)目計(jì)劃調(diào)度實(shí)施動(dòng)態(tài)調(diào)整。但仍存在以下問(wèn)題：

①現(xiàn)有基于時(shí)間Petri網(wǎng)的項(xiàng)目進(jìn)度管理模型不具備全局時(shí)鐘特性。TdPN時(shí)間延時(shí)di表示庫(kù)所中標(biāo)識(shí)的消耗和變遷的執(zhí)行需要經(jīng)過(guò)di完成，此時(shí)間延遲，只賦予工序i，不具備全局時(shí)鐘特許。在項(xiàng)目管理模型中，若T0時(shí)刻第i道工序（變遷ti）外部條件準(zhǔn)備就緒，且工序i在T0時(shí)刻執(zhí)行，則T0+di工序i執(zhí)行完畢。但在變遷ti激發(fā)的di這段時(shí)間內(nèi)，變遷ti前集庫(kù)所集ti中的標(biāo)記在ti激發(fā)時(shí)消耗掉，但是變遷ti后集庫(kù)所集ti卻需等待di才能得到相應(yīng)標(biāo)記，此時(shí)該P(yáng)etri網(wǎng)模型處于無(wú)狀態(tài)，由此產(chǎn)生悖論[11]。②現(xiàn)有基于時(shí)間Petri網(wǎng)的項(xiàng)目進(jìn)度管理模型仍然比較復(fù)雜。現(xiàn)有時(shí)間Petri網(wǎng)在對(duì)工序的邏輯關(guān)系進(jìn)行建模時(shí)，不僅增加了符號(hào)，而且在現(xiàn)有時(shí)間Petri網(wǎng)中，工序的邏輯關(guān)系中的時(shí)間冗余，需要借助虛工序來(lái)實(shí)現(xiàn)。③基于時(shí)間Petri網(wǎng)的項(xiàng)目進(jìn)度管理模型不能體現(xiàn)項(xiàng)目資源對(duì)工序執(zhí)行的時(shí)間約束。不論是TdPN、SPN還是TPN模型，時(shí)間參數(shù)只引入到變遷本身，即只對(duì)工序自身時(shí)間參數(shù)建模，無(wú)法對(duì)工序外延，例如資源約束進(jìn)行時(shí)間建模。

2 基于庫(kù)所時(shí)間約束Petri網(wǎng)項(xiàng)目進(jìn)度管理模型

2.1 庫(kù)所時(shí)間約束Petri網(wǎng)

定義1時(shí)間約束Petri網(wǎng)（Place Timing constraint Petri Net， PTcPN）是一個(gè)七元組∑=（P，T；F，W，M0，D，Ip），如圖1所示，其中：

①∑=（P，T；F，W，M0）是一個(gè)Petri網(wǎng)，但此時(shí)弧T×P上的權(quán)重w不再表示任務(wù)變遷ti所產(chǎn)生的標(biāo)記，而僅說(shuō)明庫(kù)所在狀態(tài)持續(xù)階段所需要的資源；

②D：T→R+是變遷的延時(shí)函數(shù)，圖1中指td（ti）；

③Ip為關(guān)聯(lián)庫(kù)所的實(shí)數(shù)對(duì)[Tmin，Tmax]的集合，圖1中，Ip指（tmin（pi），tmax（pi））。

圖1中，用圓圈“○”表示庫(kù)所Place，用“●”黑點(diǎn)表示庫(kù)所中的標(biāo)記Token，標(biāo)記顏色表示項(xiàng)目資源類(lèi)別，用矩形方塊“？薺”表示變遷Transaction，即工序，從庫(kù)所到變遷或是從變遷到庫(kù)所的關(guān)系用有向弧“→”表示，上述三個(gè)元素表示了系統(tǒng)的靜態(tài)模型。

PTcPN增加了事件發(fā)生條件的時(shí)間要求，在庫(kù)所和變遷都有時(shí)間約束，庫(kù)所時(shí)間約束借鑒TPN思路，而變遷時(shí)間約束借鑒TdPN思路。為了克服TdPN模型可能是整個(gè)Petri網(wǎng)模型處于無(wú)狀態(tài)中以及TPN模型變遷時(shí)延區(qū)間（tmin（ti），tmax（ti））對(duì)變遷的時(shí)間約束為局部時(shí)鐘而非全局時(shí)鐘，PTcPN引入全局時(shí)鐘概念，Ip所關(guān)聯(lián)的實(shí)數(shù)對(duì)[Tmin，Tmax]中Tmin、Tmax分別為全局時(shí)鐘下庫(kù)所最早/最遲進(jìn)入時(shí)延。圖1中，設(shè)全局時(shí)鐘以T0為起點(diǎn)，變遷t1和t2激發(fā)后，使得庫(kù)所p2和p3最早可以在全局時(shí)鐘分別為：tmin（t1）+td（t1）和tmin（t2）+td（t2）獲得標(biāo)記Token。

2.2 基于PTcPN的項(xiàng)目進(jìn)度管理模型

2.2.1 模型含義 基于PTcPN的項(xiàng)目進(jìn)度管理模型建模過(guò)程中， PTcPN模型的狀態(tài)標(biāo)識(shí)表示項(xiàng)目執(zhí)行過(guò)程中資源狀況，初始標(biāo)識(shí)M0表示項(xiàng)目未開(kāi)始實(shí)施的計(jì)劃模型，其他狀態(tài)標(biāo)識(shí)M=（M（p1），M（p2），…，M（pi））表示項(xiàng)目執(zhí)行過(guò)程中項(xiàng)目的某個(gè)狀態(tài)，即項(xiàng)目快照。模型的狀態(tài)空間則是項(xiàng)目執(zhí)行過(guò)程中所有可能狀態(tài)的集合，隨著變遷的激發(fā)、庫(kù)所標(biāo)記的移動(dòng)體現(xiàn)了模型狀態(tài)的變化，即項(xiàng)目的執(zhí)行，模型標(biāo)識(shí)的轉(zhuǎn)化體現(xiàn)系統(tǒng)的動(dòng)態(tài)行為。

2.2.2 模型狀態(tài)空間 PTcPN模型狀態(tài)空間指模型可達(dá)圖所有狀態(tài)的集合，模型狀態(tài)空間反應(yīng)了項(xiàng)目執(zhí)行過(guò)程中項(xiàng)目可能出現(xiàn)的狀態(tài)（工序執(zhí)行狀態(tài)及資源分配狀態(tài)）的集合，模型的狀態(tài)轉(zhuǎn)移序列δ=（M0t1M1…tiMi…tnMn）表示項(xiàng)目從初始狀態(tài)M0經(jīng)過(guò)若干個(gè)任務(wù)序列的執(zhí)行轉(zhuǎn)變成狀態(tài)Mn，即項(xiàng)目可能出現(xiàn)的任意兩個(gè)狀態(tài)之間所需經(jīng)歷的活動(dòng)執(zhí)行序列。模型可達(dá)圖構(gòu)造算法如下：

①T（∑）的初值只有根節(jié)點(diǎn)r，Mr=M0，即Mr為初始標(biāo)識(shí)；

②令x為T(mén)（∑）的葉子節(jié)點(diǎn)，若？坌t∈T，在Mr狀態(tài)下均有權(quán)發(fā)生，x為真節(jié)點(diǎn)；若從根節(jié)點(diǎn)r到x的路徑上有另一個(gè)節(jié)點(diǎn)y，y≠x，但是My=Mx，則x也是真葉節(jié)點(diǎn)，若T（∑）所有的葉節(jié)點(diǎn)均為真葉節(jié)點(diǎn)，則算法結(jié)束。否則執(zhí)行③；

③若T（∑）有葉節(jié)點(diǎn)x，但是x不是真葉節(jié)點(diǎn)，那么在Mx至少有一個(gè)變遷t可以發(fā)生。對(duì)Mx授權(quán)發(fā)生的每個(gè)變遷t∈T，在T（∑）上添加一個(gè)新節(jié)點(diǎn)y，y是x的子節(jié)點(diǎn)，從x到y(tǒng)的有向弧用變遷t標(biāo)記，節(jié)點(diǎn)y的標(biāo)記My按下定義：首先計(jì)算出Mx的后繼M′，即對(duì)所有s∈S，M′（s）=Mx（S）-W（s，t）+W（t，s），然后計(jì)算My，對(duì)所有s∈S，有：

My（s）=

ω，若從r到y(tǒng)的路徑上有節(jié)點(diǎn)z，使得Mz

④回到步驟②。

2.2.3 項(xiàng)目時(shí)間計(jì)算 在PTcPN模型中，庫(kù)所的時(shí)間約束[tmin（pi），tmax（pi）]需要通過(guò)計(jì)算獲得。庫(kù)所pi的最早全局時(shí)鐘為其前繼變遷集中變遷的最早全局時(shí)間與變遷持續(xù)時(shí)間之和的最大值。

tmin（pi）=max{tmin（tj）+td（tj）} 其中？坌tj∈·pi （1）

庫(kù)所pi的最遲全局時(shí)鐘為其后繼變遷集中變遷的最遲全局時(shí)間與變遷持續(xù)時(shí)間之差的最小值。

tmax（pi）=min{tmax（tj）-td（tj）} 其中？坌tj∈■ （2）

在PTcPN模型中庫(kù)所時(shí)差為0的庫(kù)所為關(guān)鍵庫(kù)所，所有關(guān)鍵庫(kù)所及其對(duì)應(yīng)變遷組成項(xiàng)目的關(guān)鍵路徑。pi為關(guān)鍵庫(kù)所，當(dāng)且僅當(dāng)：tmin（pi）-tmax（pi）=0。 （3）

3 實(shí)例分析

3.1 項(xiàng)目描述 為了說(shuō)明PTcPN在項(xiàng)目進(jìn)度管理中的應(yīng)用，本文以某軟件開(kāi)發(fā)項(xiàng)目為例，著重對(duì)軟件開(kāi)發(fā)過(guò)程進(jìn)度管理進(jìn)行分析。項(xiàng)目工序邏輯關(guān)系、工期、資源要求如表1所示。

3.2 項(xiàng)目PTcPN建模 根據(jù)PTcPN定義，以及表1項(xiàng)目信息，構(gòu)建基于PTcPN的項(xiàng)目進(jìn)度模型如圖2所示，其中庫(kù)所p0和p15為輔助庫(kù)所，無(wú)實(shí)際含義。

3.3 項(xiàng)目狀態(tài)空間分析 根據(jù)可達(dá)圖構(gòu)造算法，求得圖2對(duì)應(yīng)的可達(dá)圖如圖3所示。

項(xiàng)目狀態(tài)空間反應(yīng)了整個(gè)項(xiàng)目可能存在的調(diào)度方案，狀態(tài)Si指項(xiàng)目執(zhí)行過(guò)程可能處于的狀態(tài)，狀態(tài)Si到狀態(tài)Sj箭頭序列表明了項(xiàng)目從狀態(tài)Si到狀態(tài)Sj需經(jīng)歷的工序調(diào)度序列。項(xiàng)目管理者可以根此預(yù)測(cè)項(xiàng)目狀態(tài)空間預(yù)測(cè)項(xiàng)目當(dāng)前狀態(tài)下可能出現(xiàn)的各種調(diào)度方案以及特定調(diào)度方案下項(xiàng)目所處的下一個(gè)狀態(tài)，使得項(xiàng)目調(diào)度與執(zhí)行具有可預(yù)測(cè)性。

3.4 項(xiàng)目時(shí)間計(jì)算 根據(jù)式（1）和式（2）分別求解模型各庫(kù)所時(shí)間約束，根據(jù)式（3）確定項(xiàng)目關(guān)鍵路徑，如表2所示。

由表2可得項(xiàng)目關(guān)鍵路徑為：A→B→C→F→J→M→N，總工期為26。

4 結(jié)語(yǔ)

本文在綜合比較網(wǎng)絡(luò)計(jì)劃技術(shù)以及現(xiàn)有時(shí)間Petri網(wǎng)在項(xiàng)目進(jìn)度管理建模優(yōu)缺點(diǎn)基礎(chǔ)上，針對(duì)現(xiàn)有時(shí)間Petri網(wǎng)在項(xiàng)目進(jìn)度管理建模不具備全局時(shí)鐘、模型相對(duì)復(fù)雜以及無(wú)法體現(xiàn)資源約束等不足，提出了基于庫(kù)所時(shí)間約束Petri網(wǎng)，將時(shí)間約束擴(kuò)展至庫(kù)所。實(shí)例分析說(shuō)明，基于庫(kù)所時(shí)間約束Petri網(wǎng)的項(xiàng)目進(jìn)度管理模型更好了體現(xiàn)了資源的時(shí)間約束，該模型不僅能夠替代傳統(tǒng)網(wǎng)絡(luò)計(jì)劃技術(shù)，實(shí)現(xiàn)工序的邏輯關(guān)系建模，簡(jiǎn)化項(xiàng)目網(wǎng)絡(luò)圖，實(shí)現(xiàn)項(xiàng)目時(shí)間管理，模型狀態(tài)空間也為項(xiàng)目管理者提供了更多決策信息。限于篇幅，本文未對(duì)非肯定型項(xiàng)目實(shí)現(xiàn)案例應(yīng)用及仿真。

參考文獻(xiàn)：

[1]張紹陽(yáng).基于Petri網(wǎng)的公路施工進(jìn)度計(jì)劃及資源優(yōu)化研究[D].長(zhǎng)安大學(xué)博士學(xué)位論文，2006.

[2]李海凌，史本山，劉克劍.基于Petri網(wǎng)的建設(shè)工程項(xiàng)目實(shí)施階段資源建模與仿真[J].計(jì)算機(jī)應(yīng)用研究，2011，28（12）：4593-4596.

[3]Fay A.A Fuzzy Knowledge-based System for Railway Traffic Control. Engineering Applications of Artificial Intelligence，2000（13）：719-729.

[4]沈俊鑫.基于擴(kuò)展Petri網(wǎng)的經(jīng)營(yíng)性公共基礎(chǔ)設(shè)施TOT特許期決策研究[D].昆明理工大學(xué)博士學(xué)位論文，2012.

[5]羅亞.一種基于PERT圖的Petri網(wǎng)模型構(gòu)建方法[J].系統(tǒng)仿真學(xué)報(bào)，2005，17（7）：1560-1562.

[6]Kejian LIU， Hailing LI， Caihong GUO， Lian YAN， Fei CHEN. Research on Modeling of Programme Management Based on Petri Net[J]. Journal of Computational Information Systems，2012，20（8）： 8629-8635.

[7]段波，趙穩(wěn)莊，仉樹(shù)軍.Petri網(wǎng)在制造系統(tǒng)建模與仿真中的應(yīng)用[J].航空精密制造技術(shù)，2008，44（5）：52-56.

[8]陳翔.基于Petri網(wǎng)及矩母函數(shù)的計(jì)劃評(píng)審技術(shù)[J].北京理工大學(xué)學(xué)報(bào)，2010，30（9）：1121-1125.

[9]馬俊，廖偉志，李書(shū)舉，羅錦坤.基于時(shí)延Petri網(wǎng)的房地產(chǎn)業(yè)工期計(jì)劃管理[J].廣西師范學(xué)院學(xué)報(bào)：自然科學(xué)版，2012，29（1）：66-71.

[10]沈俊鑫，王松江.基于隨機(jī)Petri網(wǎng)的TOT特許期風(fēng)險(xiǎn)分析模型[J].項(xiàng)目管理技術(shù)，2010（12）：87-91.

[11]宋巍，于瑞強(qiáng).利用時(shí)間約束Petri網(wǎng)進(jìn)行項(xiàng)目績(jī)效分析[J].小型微型計(jì)算機(jī)系統(tǒng)，2010，31（2）：276-280.

[12]Bernard Berthomieu， Florent Peres，F(xiàn)rancois Vernadat. Abstract state spaces for time Petri nets analysis[C]. Proceeding of the 11th IEEE Symposium on Object Oriented Real-Time Distributed Computing，2008：298-304.

[13]滿(mǎn)慶鵬，王要武，李曉東.基于Petri網(wǎng)的施工進(jìn)度建模及優(yōu)化方法[J].系統(tǒng)管理學(xué)報(bào)，2009，18（2）：193-198.

[14]施國(guó)強(qiáng)，李伯虎，柴旭東.基于著色Petri網(wǎng)的復(fù)雜產(chǎn)品開(kāi)發(fā)多項(xiàng)目調(diào)度建模研究[J].系統(tǒng)仿真學(xué)報(bào)，2007，19（17）：3869-3873.

[15]李海凌，史本山，劉克劍.基于Petri網(wǎng)的建設(shè)工程項(xiàng)目實(shí)施階段工作流建模與仿真[J].計(jì)算機(jī)應(yīng)用，2011，31（10）：2828-2831.

[16]Cheng Feifei， Li， Heng.Modeling resource management in the building design process by information constraint Petri nets[J]. Automation in Construction， 2013，29：92-99.

[17]于汪洋，吳哲輝.時(shí)延Petri網(wǎng)模擬能力研究[J].微計(jì)算機(jī)應(yīng)用，2009（8）：32-37.

tmax（pi）=min{tmax（tj）-td（tj）} 其中？坌tj∈■ （2）

在PTcPN模型中庫(kù)所時(shí)差為0的庫(kù)所為關(guān)鍵庫(kù)所，所有關(guān)鍵庫(kù)所及其對(duì)應(yīng)變遷組成項(xiàng)目的關(guān)鍵路徑。pi為關(guān)鍵庫(kù)所，當(dāng)且僅當(dāng)：tmin（pi）-tmax（pi）=0。 （3）

3 實(shí)例分析

3.1 項(xiàng)目描述 為了說(shuō)明PTcPN在項(xiàng)目進(jìn)度管理中的應(yīng)用，本文以某軟件開(kāi)發(fā)項(xiàng)目為例，著重對(duì)軟件開(kāi)發(fā)過(guò)程進(jìn)度管理進(jìn)行分析。項(xiàng)目工序邏輯關(guān)系、工期、資源要求如表1所示。

3.2 項(xiàng)目PTcPN建模 根據(jù)PTcPN定義，以及表1項(xiàng)目信息，構(gòu)建基于PTcPN的項(xiàng)目進(jìn)度模型如圖2所示，其中庫(kù)所p0和p15為輔助庫(kù)所，無(wú)實(shí)際含義。

3.3 項(xiàng)目狀態(tài)空間分析 根據(jù)可達(dá)圖構(gòu)造算法，求得圖2對(duì)應(yīng)的可達(dá)圖如圖3所示。

項(xiàng)目狀態(tài)空間反應(yīng)了整個(gè)項(xiàng)目可能存在的調(diào)度方案，狀態(tài)Si指項(xiàng)目執(zhí)行過(guò)程可能處于的狀態(tài)，狀態(tài)Si到狀態(tài)Sj箭頭序列表明了項(xiàng)目從狀態(tài)Si到狀態(tài)Sj需經(jīng)歷的工序調(diào)度序列。項(xiàng)目管理者可以根此預(yù)測(cè)項(xiàng)目狀態(tài)空間預(yù)測(cè)項(xiàng)目當(dāng)前狀態(tài)下可能出現(xiàn)的各種調(diào)度方案以及特定調(diào)度方案下項(xiàng)目所處的下一個(gè)狀態(tài)，使得項(xiàng)目調(diào)度與執(zhí)行具有可預(yù)測(cè)性。

3.4 項(xiàng)目時(shí)間計(jì)算 根據(jù)式（1）和式（2）分別求解模型各庫(kù)所時(shí)間約束，根據(jù)式（3）確定項(xiàng)目關(guān)鍵路徑，如表2所示。

由表2可得項(xiàng)目關(guān)鍵路徑為：A→B→C→F→J→M→N，總工期為26。

4 結(jié)語(yǔ)

本文在綜合比較網(wǎng)絡(luò)計(jì)劃技術(shù)以及現(xiàn)有時(shí)間Petri網(wǎng)在項(xiàng)目進(jìn)度管理建模優(yōu)缺點(diǎn)基礎(chǔ)上，針對(duì)現(xiàn)有時(shí)間Petri網(wǎng)在項(xiàng)目進(jìn)度管理建模不具備全局時(shí)鐘、模型相對(duì)復(fù)雜以及無(wú)法體現(xiàn)資源約束等不足，提出了基于庫(kù)所時(shí)間約束Petri網(wǎng)，將時(shí)間約束擴(kuò)展至庫(kù)所。實(shí)例分析說(shuō)明，基于庫(kù)所時(shí)間約束Petri網(wǎng)的項(xiàng)目進(jìn)度管理模型更好了體現(xiàn)了資源的時(shí)間約束，該模型不僅能夠替代傳統(tǒng)網(wǎng)絡(luò)計(jì)劃技術(shù)，實(shí)現(xiàn)工序的邏輯關(guān)系建模，簡(jiǎn)化項(xiàng)目網(wǎng)絡(luò)圖，實(shí)現(xiàn)項(xiàng)目時(shí)間管理，模型狀態(tài)空間也為項(xiàng)目管理者提供了更多決策信息。限于篇幅，本文未對(duì)非肯定型項(xiàng)目實(shí)現(xiàn)案例應(yīng)用及仿真。

參考文獻(xiàn)：

[1]張紹陽(yáng).基于Petri網(wǎng)的公路施工進(jìn)度計(jì)劃及資源優(yōu)化研究[D].長(zhǎng)安大學(xué)博士學(xué)位論文，2006.

[2]李海凌，史本山，劉克劍.基于Petri網(wǎng)的建設(shè)工程項(xiàng)目實(shí)施階段資源建模與仿真[J].計(jì)算機(jī)應(yīng)用研究，2011，28（12）：4593-4596.

[3]Fay A.A Fuzzy Knowledge-based System for Railway Traffic Control. Engineering Applications of Artificial Intelligence，2000（13）：719-729.

[4]沈俊鑫.基于擴(kuò)展Petri網(wǎng)的經(jīng)營(yíng)性公共基礎(chǔ)設(shè)施TOT特許期決策研究[D].昆明理工大學(xué)博士學(xué)位論文，2012.

[5]羅亞.一種基于PERT圖的Petri網(wǎng)模型構(gòu)建方法[J].系統(tǒng)仿真學(xué)報(bào)，2005，17（7）：1560-1562.

[6]Kejian LIU， Hailing LI， Caihong GUO， Lian YAN， Fei CHEN. Research on Modeling of Programme Management Based on Petri Net[J]. Journal of Computational Information Systems，2012，20（8）： 8629-8635.

[7]段波，趙穩(wěn)莊，仉樹(shù)軍.Petri網(wǎng)在制造系統(tǒng)建模與仿真中的應(yīng)用[J].航空精密制造技術(shù)，2008，44（5）：52-56.

[8]陳翔.基于Petri網(wǎng)及矩母函數(shù)的計(jì)劃評(píng)審技術(shù)[J].北京理工大學(xué)學(xué)報(bào)，2010，30（9）：1121-1125.

[9]馬俊，廖偉志，李書(shū)舉，羅錦坤.基于時(shí)延Petri網(wǎng)的房地產(chǎn)業(yè)工期計(jì)劃管理[J].廣西師范學(xué)院學(xué)報(bào)：自然科學(xué)版，2012，29（1）：66-71.

[10]沈俊鑫，王松江.基于隨機(jī)Petri網(wǎng)的TOT特許期風(fēng)險(xiǎn)分析模型[J].項(xiàng)目管理技術(shù)，2010（12）：87-91.

[11]宋巍，于瑞強(qiáng).利用時(shí)間約束Petri網(wǎng)進(jìn)行項(xiàng)目績(jī)效分析[J].小型微型計(jì)算機(jī)系統(tǒng)，2010，31（2）：276-280.

[12]Bernard Berthomieu， Florent Peres，F(xiàn)rancois Vernadat. Abstract state spaces for time Petri nets analysis[C]. Proceeding of the 11th IEEE Symposium on Object Oriented Real-Time Distributed Computing，2008：298-304.

[13]滿(mǎn)慶鵬，王要武，李曉東.基于Petri網(wǎng)的施工進(jìn)度建模及優(yōu)化方法[J].系統(tǒng)管理學(xué)報(bào)，2009，18（2）：193-198.

[14]施國(guó)強(qiáng)，李伯虎，柴旭東.基于著色Petri網(wǎng)的復(fù)雜產(chǎn)品開(kāi)發(fā)多項(xiàng)目調(diào)度建模研究[J].系統(tǒng)仿真學(xué)報(bào)，2007，19（17）：3869-3873.

[15]李海凌，史本山，劉克劍.基于Petri網(wǎng)的建設(shè)工程項(xiàng)目實(shí)施階段工作流建模與仿真[J].計(jì)算機(jī)應(yīng)用，2011，31（10）：2828-2831.

[16]Cheng Feifei， Li， Heng.Modeling resource management in the building design process by information constraint Petri nets[J]. Automation in Construction， 2013，29：92-99.

[17]于汪洋，吳哲輝.時(shí)延Petri網(wǎng)模擬能力研究[J].微計(jì)算機(jī)應(yīng)用，2009（8）：32-37.

tmax（pi）=min{tmax（tj）-td（tj）} 其中？坌tj∈■ （2）

在PTcPN模型中庫(kù)所時(shí)差為0的庫(kù)所為關(guān)鍵庫(kù)所，所有關(guān)鍵庫(kù)所及其對(duì)應(yīng)變遷組成項(xiàng)目的關(guān)鍵路徑。pi為關(guān)鍵庫(kù)所，當(dāng)且僅當(dāng)：tmin（pi）-tmax（pi）=0。 （3）

3 實(shí)例分析

3.1 項(xiàng)目描述 為了說(shuō)明PTcPN在項(xiàng)目進(jìn)度管理中的應(yīng)用，本文以某軟件開(kāi)發(fā)項(xiàng)目為例，著重對(duì)軟件開(kāi)發(fā)過(guò)程進(jìn)度管理進(jìn)行分析。項(xiàng)目工序邏輯關(guān)系、工期、資源要求如表1所示。

3.2 項(xiàng)目PTcPN建模 根據(jù)PTcPN定義，以及表1項(xiàng)目信息，構(gòu)建基于PTcPN的項(xiàng)目進(jìn)度模型如圖2所示，其中庫(kù)所p0和p15為輔助庫(kù)所，無(wú)實(shí)際含義。

3.3 項(xiàng)目狀態(tài)空間分析 根據(jù)可達(dá)圖構(gòu)造算法，求得圖2對(duì)應(yīng)的可達(dá)圖如圖3所示。

項(xiàng)目狀態(tài)空間反應(yīng)了整個(gè)項(xiàng)目可能存在的調(diào)度方案，狀態(tài)Si指項(xiàng)目執(zhí)行過(guò)程可能處于的狀態(tài)，狀態(tài)Si到狀態(tài)Sj箭頭序列表明了項(xiàng)目從狀態(tài)Si到狀態(tài)Sj需經(jīng)歷的工序調(diào)度序列。項(xiàng)目管理者可以根此預(yù)測(cè)項(xiàng)目狀態(tài)空間預(yù)測(cè)項(xiàng)目當(dāng)前狀態(tài)下可能出現(xiàn)的各種調(diào)度方案以及特定調(diào)度方案下項(xiàng)目所處的下一個(gè)狀態(tài)，使得項(xiàng)目調(diào)度與執(zhí)行具有可預(yù)測(cè)性。

3.4 項(xiàng)目時(shí)間計(jì)算 根據(jù)式（1）和式（2）分別求解模型各庫(kù)所時(shí)間約束，根據(jù)式（3）確定項(xiàng)目關(guān)鍵路徑，如表2所示。

由表2可得項(xiàng)目關(guān)鍵路徑為：A→B→C→F→J→M→N，總工期為26。

4 結(jié)語(yǔ)

本文在綜合比較網(wǎng)絡(luò)計(jì)劃技術(shù)以及現(xiàn)有時(shí)間Petri網(wǎng)在項(xiàng)目進(jìn)度管理建模優(yōu)缺點(diǎn)基礎(chǔ)上，針對(duì)現(xiàn)有時(shí)間Petri網(wǎng)在項(xiàng)目進(jìn)度管理建模不具備全局時(shí)鐘、模型相對(duì)復(fù)雜以及無(wú)法體現(xiàn)資源約束等不足，提出了基于庫(kù)所時(shí)間約束Petri網(wǎng)，將時(shí)間約束擴(kuò)展至庫(kù)所。實(shí)例分析說(shuō)明，基于庫(kù)所時(shí)間約束Petri網(wǎng)的項(xiàng)目進(jìn)度管理模型更好了體現(xiàn)了資源的時(shí)間約束，該模型不僅能夠替代傳統(tǒng)網(wǎng)絡(luò)計(jì)劃技術(shù)，實(shí)現(xiàn)工序的邏輯關(guān)系建模，簡(jiǎn)化項(xiàng)目網(wǎng)絡(luò)圖，實(shí)現(xiàn)項(xiàng)目時(shí)間管理，模型狀態(tài)空間也為項(xiàng)目管理者提供了更多決策信息。限于篇幅，本文未對(duì)非肯定型項(xiàng)目實(shí)現(xiàn)案例應(yīng)用及仿真。

參考文獻(xiàn)：

[1]張紹陽(yáng).基于Petri網(wǎng)的公路施工進(jìn)度計(jì)劃及資源優(yōu)化研究[D].長(zhǎng)安大學(xué)博士學(xué)位論文，2006.

[2]李海凌，史本山，劉克劍.基于Petri網(wǎng)的建設(shè)工程項(xiàng)目實(shí)施階段資源建模與仿真[J].計(jì)算機(jī)應(yīng)用研究，2011，28（12）：4593-4596.

[3]Fay A.A Fuzzy Knowledge-based System for Railway Traffic Control. Engineering Applications of Artificial Intelligence，2000（13）：719-729.

[4]沈俊鑫.基于擴(kuò)展Petri網(wǎng)的經(jīng)營(yíng)性公共基礎(chǔ)設(shè)施TOT特許期決策研究[D].昆明理工大學(xué)博士學(xué)位論文，2012.

[5]羅亞.一種基于PERT圖的Petri網(wǎng)模型構(gòu)建方法[J].系統(tǒng)仿真學(xué)報(bào)，2005，17（7）：1560-1562.

[6]Kejian LIU， Hailing LI， Caihong GUO， Lian YAN， Fei CHEN. Research on Modeling of Programme Management Based on Petri Net[J]. Journal of Computational Information Systems，2012，20（8）： 8629-8635.

[7]段波，趙穩(wěn)莊，仉樹(shù)軍.Petri網(wǎng)在制造系統(tǒng)建模與仿真中的應(yīng)用[J].航空精密制造技術(shù)，2008，44（5）：52-56.

[8]陳翔.基于Petri網(wǎng)及矩母函數(shù)的計(jì)劃評(píng)審技術(shù)[J].北京理工大學(xué)學(xué)報(bào)，2010，30（9）：1121-1125.

[9]馬俊，廖偉志，李書(shū)舉，羅錦坤.基于時(shí)延Petri網(wǎng)的房地產(chǎn)業(yè)工期計(jì)劃管理[J].廣西師范學(xué)院學(xué)報(bào)：自然科學(xué)版，2012，29（1）：66-71.

[10]沈俊鑫，王松江.基于隨機(jī)Petri網(wǎng)的TOT特許期風(fēng)險(xiǎn)分析模型[J].項(xiàng)目管理技術(shù)，2010（12）：87-91.

[11]宋巍，于瑞強(qiáng).利用時(shí)間約束Petri網(wǎng)進(jìn)行項(xiàng)目績(jī)效分析[J].小型微型計(jì)算機(jī)系統(tǒng)，2010，31（2）：276-280.

[12]Bernard Berthomieu， Florent Peres，F(xiàn)rancois Vernadat. Abstract state spaces for time Petri nets analysis[C]. Proceeding of the 11th IEEE Symposium on Object Oriented Real-Time Distributed Computing，2008：298-304.

[13]滿(mǎn)慶鵬，王要武，李曉東.基于Petri網(wǎng)的施工進(jìn)度建模及優(yōu)化方法[J].系統(tǒng)管理學(xué)報(bào)，2009，18（2）：193-198.

[14]施國(guó)強(qiáng)，李伯虎，柴旭東.基于著色Petri網(wǎng)的復(fù)雜產(chǎn)品開(kāi)發(fā)多項(xiàng)目調(diào)度建模研究[J].系統(tǒng)仿真學(xué)報(bào)，2007，19（17）：3869-3873.

[15]李海凌，史本山，劉克劍.基于Petri網(wǎng)的建設(shè)工程項(xiàng)目實(shí)施階段工作流建模與仿真[J].計(jì)算機(jī)應(yīng)用，2011，31（10）：2828-2831.

[16]Cheng Feifei， Li， Heng.Modeling resource management in the building design process by information constraint Petri nets[J]. Automation in Construction， 2013，29：92-99.

[17]于汪洋，吳哲輝.時(shí)延Petri網(wǎng)模擬能力研究[J].微計(jì)算機(jī)應(yīng)用，2009（8）：32-37.