支持并行調(diào)度的多項(xiàng)目資源管理CPN建模

李海凌，劉克劍2，陶學(xué)明

(1.西華大學(xué)建筑與土木工程學(xué)院，四川 成都 610039；2.西華大學(xué)數(shù)學(xué)與計(jì)算機(jī)學(xué)院，四川 成都 610039)

·建筑與土木工程·

支持并行調(diào)度的多項(xiàng)目資源管理CPN建模

李海凌1，劉克劍2，陶學(xué)明1

(1.西華大學(xué)建筑與土木工程學(xué)院，四川 成都 610039；2.西華大學(xué)數(shù)學(xué)與計(jì)算機(jī)學(xué)院，四川 成都 610039)

構(gòu)建良好的多項(xiàng)目資源調(diào)度模型已成為項(xiàng)目型企業(yè)多項(xiàng)目管理計(jì)劃與控制的關(guān)鍵性基礎(chǔ)工作。在分析多項(xiàng)目并行調(diào)度特點(diǎn)的基礎(chǔ)上，基于Petri網(wǎng)擅長描述隨機(jī)性、任務(wù)間并發(fā)、同步、并行等系統(tǒng)特征的優(yōu)勢，克服當(dāng)前已有的多項(xiàng)目并行調(diào)度模型的不足，構(gòu)建了基于CPN的多項(xiàng)目并行調(diào)度模型。通過建模實(shí)例闡述了模型的仿真分析方法，證明了基于著色Petri網(wǎng)構(gòu)建多項(xiàng)目并行調(diào)度模型的可行性和有效性。

并行調(diào)度；多項(xiàng)目；資源管理；CPN

項(xiàng)目型企業(yè)在同一時(shí)間內(nèi)實(shí)施多個(gè)項(xiàng)目的情況越來越普遍，將并行項(xiàng)目視作一個(gè)整體的多項(xiàng)目調(diào)度問題已得到了越來越多企業(yè)的重視。遵循先進(jìn)有效的項(xiàng)目管理模式，并在管理模式基礎(chǔ)上構(gòu)建良好的多項(xiàng)目調(diào)度模型作為指導(dǎo)以輔助管理，成為多項(xiàng)目管理成敗的關(guān)鍵。

多項(xiàng)目并行調(diào)度建模就是企業(yè)基于集成協(xié)同理論，在多項(xiàng)目環(huán)境下，建立多項(xiàng)目并行實(shí)施的調(diào)度管理模型。通過該模型模擬、分析、優(yōu)化、監(jiān)控多項(xiàng)目進(jìn)度計(jì)劃，找出實(shí)施多項(xiàng)目的資源沖突或瓶頸，優(yōu)化企業(yè)資源配置，支持各項(xiàng)目建設(shè)團(tuán)隊(duì)的協(xié)作，最終實(shí)現(xiàn)企業(yè)組織價(jià)值的最大化。

本文從全面分析多項(xiàng)目并行調(diào)度的特點(diǎn)出發(fā)，在比較已有建模方法的基礎(chǔ)上，提出了基于著色Petri網(wǎng)(colored petri net，CPN)的調(diào)度模型。該模型能夠表達(dá)多項(xiàng)目調(diào)度的靜態(tài)屬性和動(dòng)態(tài)特性，為多項(xiàng)目環(huán)境下的管理人員的控制及決策提供向?qū)А?/p>

1 多項(xiàng)目并行調(diào)度的特點(diǎn)分析

項(xiàng)目型企業(yè)的多項(xiàng)目管理以項(xiàng)目為中心，關(guān)注整體項(xiàng)目的順利完成，這其中就包括多項(xiàng)目調(diào)度的分析和優(yōu)化[1]。項(xiàng)目建設(shè)模式將直接決定多項(xiàng)目調(diào)度的特點(diǎn)。并行工程是項(xiàng)目及其相關(guān)過程一體化實(shí)施的一種系統(tǒng)化的建設(shè)模式，其執(zhí)行可組建項(xiàng)目群集成管理團(tuán)隊(duì)(integrated programme team，IPT)來完成[2]，具有層次性、并行性和開放性的特點(diǎn)。這些特點(diǎn)決定了項(xiàng)目型企業(yè)具有多項(xiàng)目調(diào)度的特點(diǎn)。

1)層次性：進(jìn)行物理或邏輯的分解以體現(xiàn)多項(xiàng)目實(shí)施的層次性。多項(xiàng)目實(shí)施物理上的層次性可表現(xiàn)為各個(gè)項(xiàng)目的并行、同一項(xiàng)目的分標(biāo)段實(shí)施，或者流水實(shí)施中的分區(qū)實(shí)施。邏輯上的層次性則可以表現(xiàn)為依據(jù)WBS進(jìn)行的項(xiàng)目分解。多項(xiàng)目的并行可表現(xiàn)為經(jīng)過層次分解后多個(gè)任務(wù)子集的并行。

2)沖突性：指項(xiàng)目資源的共用性和獨(dú)占性引起的資源沖突。共用性是指并行任務(wù)的實(shí)施需要同一類資源；獨(dú)占性是指同類資源中某一確定資源在同一時(shí)間只能被一個(gè)任務(wù)所使用：因此，資源的共用性和獨(dú)占性在資源有限時(shí)會(huì)導(dǎo)致沖突。企業(yè)資源大多是有限的，并行展開的多項(xiàng)目很難避免沖突。

3)迭代性：通常是指由于技術(shù)關(guān)聯(lián)引起的技術(shù)借鑒以迭代方式進(jìn)行的任務(wù)間反復(fù)。在多項(xiàng)目的實(shí)施過程中，也指質(zhì)量導(dǎo)致的返工修復(fù)。

4)開放性：在多項(xiàng)目環(huán)境下，企業(yè)隨時(shí)可能有新項(xiàng)目加入或己有項(xiàng)目完成退出，一個(gè)高優(yōu)先級(jí)項(xiàng)目的加入會(huì)引起計(jì)劃的重排[1]；所以，多項(xiàng)目管理是動(dòng)態(tài)開放的。

2 建模方法選擇

傳統(tǒng)網(wǎng)絡(luò)計(jì)劃模型是基于CPM或PERT，將多個(gè)項(xiàng)目通過添加首尾虛任務(wù)整合成一個(gè)“大項(xiàng)目”的網(wǎng)絡(luò)圖[1]。它能夠表達(dá)項(xiàng)目間的先后實(shí)施順序，但只能描述發(fā)生一次的活動(dòng)，不能表達(dá)多項(xiàng)目的迭代性和資源沖突性，缺乏有效的方法進(jìn)行多項(xiàng)目動(dòng)態(tài)調(diào)度。

循環(huán)運(yùn)行網(wǎng)絡(luò)(cycle operation network，CYCLONE)是在網(wǎng)絡(luò)計(jì)劃中引入排隊(duì)論和仿真技術(shù)，對具有隨機(jī)時(shí)間的循環(huán)施工過程進(jìn)行仿真[3]。CYCLONE可以很好地表達(dá)實(shí)施過程的隨機(jī)性，卻對任務(wù)同步、沖突、并發(fā)的描述無能為力[4]。

數(shù)學(xué)規(guī)劃是一種常用的多項(xiàng)目資源優(yōu)化模型，通過假設(shè)定義，將多項(xiàng)目轉(zhuǎn)化成單項(xiàng)目問題進(jìn)行優(yōu)化求解，其解決問題的路徑存在理論局限：資源在多個(gè)項(xiàng)目之間的分配和在一個(gè)項(xiàng)目內(nèi)的分配并不完全一致，單個(gè)項(xiàng)目實(shí)施的實(shí)質(zhì)是其內(nèi)部各個(gè)活動(dòng)依照內(nèi)在規(guī)律的先后執(zhí)行，這樣的實(shí)施規(guī)律在多個(gè)項(xiàng)目之間卻并不存在[5]，也不能體現(xiàn)上述多項(xiàng)目的層次性和開放性。兩層決策模型對數(shù)學(xué)規(guī)劃進(jìn)行了改進(jìn)：將資源按照項(xiàng)目的不同進(jìn)行分配，降低乃至停止資源切換。但兩層決策求解所需要的初始可行解很難確定，且最終得到的不是最優(yōu)解只是可行解[6]。

Petri網(wǎng)是一種集嚴(yán)格的形式化定義、易懂的圖形表達(dá)、直觀的仿真運(yùn)行、成熟的數(shù)學(xué)分析等特點(diǎn)為一體的建模技術(shù)。它可以動(dòng)態(tài)地進(jìn)行系統(tǒng)描述，適合于活動(dòng)的即時(shí)監(jiān)控，是一種完全基于過程的針對復(fù)雜系統(tǒng)的有效建模工具[7]。Petri網(wǎng)不僅具備CYCLONE描述系統(tǒng)隨機(jī)性的優(yōu)勢，還擅長描述任務(wù)間并發(fā)、同步、并行等系統(tǒng)特征[8]。在大型復(fù)雜系統(tǒng)建模中，原型Petri網(wǎng)狀態(tài)維數(shù)會(huì)急劇增加，建立的模型將非常龐大，系統(tǒng)結(jié)構(gòu)缺乏柔性[1]。賦予原型Petri網(wǎng)顏色概念所形成的CPN增強(qiáng)了Petri網(wǎng)的描述能力，有利于解決狀態(tài)空間爆炸的問題。CPN與其他建模方法相比，能更好地描述多項(xiàng)目調(diào)度的特點(diǎn)，適合于多項(xiàng)目并行調(diào)度建模。

3 基于CPN的多項(xiàng)目并行調(diào)度建模

3.1 多項(xiàng)目并行調(diào)度模型的形式化定義

定義1 多項(xiàng)目并行調(diào)度模型可以用一個(gè)九元組的CPN=(P,T：F,N,R,C,G,E,M0)[9]來描述，其中：

1)(P,T：F)為一個(gè)原型Petri網(wǎng)，P、T、F分別表示庫所(place)、變遷(transition)、弧(arc)的有限集合；

2)N：節(jié)點(diǎn)函數(shù)(node function)，是定義F到P×T∪T×P的函數(shù)。相同順序的節(jié)點(diǎn)對(如從節(jié)點(diǎn)1到節(jié)點(diǎn)2)容許多個(gè)不同的弧，因此需要通過N進(jìn)行區(qū)分；

3)R：非空有限類型的顏色集合(colored sets)；

4)C：顏色函數(shù)(color function)，將庫所P映射到非空有限類型顏色集合R，描述庫所的資源類別及數(shù)量等信息；

5)G：布爾型函數(shù)，T映射到?t∈T：[Type (G(t))=B∧Type(Var(g(t)))?R]的守衛(wèi)函數(shù)(guard function)，函數(shù)中的變量類型屬于R，省略時(shí)默認(rèn)為true；

6)E：F映射到?f∈F：[Type(E(f))=C(P(f))MS∧Type(Var(E(f))?R]的弧表達(dá)式函數(shù)(arc expression function)，函數(shù)值為弧相應(yīng)庫所顏色集上的多重集，函數(shù)中的變量類型屬于R；

7)M0：庫所P映射到?p∈P：[Type(M(p))=C(P)MS]的初始化函數(shù)(initialization function)，函數(shù)值是庫所顏色集上的多重集。

3.2 多項(xiàng)目并行調(diào)度CPN顏色定義

1)colset P = int timed；聲明一個(gè)帶時(shí)間戳的整數(shù)顏色集，表示子項(xiàng)目的狀態(tài)。

2)colset INT = int；聲明一個(gè)整數(shù)顏色集。

3)colset req = record n：INT*m：INT*tim：INT*rn：INT；表示資源請求。其中，n為子項(xiàng)目編號(hào)，m為子項(xiàng)目分解任務(wù)編號(hào)，tim為發(fā)出資源請求的時(shí)間，rn為資源的需求數(shù)量。

4)colest res = int；表示項(xiàng)目的資源分類。

5)colset ress = list res；表示項(xiàng)目的資源列表。

6)colset mtres = record m：INT*t：INT*r：ress；表示第m個(gè)分解任務(wù)在t時(shí)間獲得的資源列表。

3.3 多項(xiàng)目并行調(diào)度特點(diǎn)的建模

根據(jù)上述分析與定義進(jìn)行多項(xiàng)目并行調(diào)度特點(diǎn)建模。

3.3.1 層次性

通過替代變遷實(shí)現(xiàn)多項(xiàng)目實(shí)施的層次性描述，如圖1所示。T1為多項(xiàng)目中某子項(xiàng)目的實(shí)施，為替代變遷，其所在頁為上層父網(wǎng)。T1分別與Reqres(資源請求庫所)、Res(資源分配庫所)、Retres(資源存放庫所)相關(guān)聯(lián)。T1具體實(shí)施見下層子網(wǎng)虛線框內(nèi)。T11、T12和T13表示T1項(xiàng)目中分解任務(wù)的實(shí)施，它們均需在Reqres、Retres、Res中獲得資源支持。父網(wǎng)和子網(wǎng)間的資源信息數(shù)據(jù)通過關(guān)聯(lián)的資源庫所實(shí)現(xiàn)分層傳遞。

圖1 項(xiàng)目分層建模

3.3.2 沖突性

同類屬性的資源形成一個(gè)資源集合，即資源池pool。圖2中R3為資源分配變遷，進(jìn)行pool1、pool2、pool3中資源數(shù)量能否滿足Reqres中資源(有可能是資源請求隊(duì)列)需求的判斷。如果滿足，R3將相應(yīng)數(shù)量資源分配到對應(yīng)的任務(wù)庫所Res1、Res2、Res3、Res4中供其使用；如果不滿足，則產(chǎn)生資源沖突。

3.3.3 迭代性

傳統(tǒng)網(wǎng)絡(luò)計(jì)劃模型只表達(dá)了任務(wù)間信息的單向傳遞、順序進(jìn)展，任務(wù)間的迭代實(shí)施特性卻被忽略；因此只是項(xiàng)目實(shí)施的靜態(tài)描述。CPN可以通過函數(shù)聲明、相關(guān)庫所及變遷進(jìn)行迭代的清晰表達(dá)。

圖3 迭代的CPN表示

3.3.4 開放性

CPN可以通過增減庫所或變量表示項(xiàng)目的加入或退出。若并行項(xiàng)目不多，模型增加P庫所代表新項(xiàng)目；若并行項(xiàng)目較多，模型通過在多項(xiàng)目庫所中加入表示新項(xiàng)目的托肯，將有利于降低Petri網(wǎng)的狀態(tài)維數(shù)。

依據(jù)上述項(xiàng)目實(shí)施的層次性、沖突性、迭代性、開放性的Petri網(wǎng)建模描述，多項(xiàng)目并行調(diào)度模型是一個(gè)分層模型，其模型特性與其資源管理需求有相似之處。資源的類別、沖突與否及資源消耗反映在并行調(diào)度模型中就是托肯的著色、變遷使能及托肯的移動(dòng)和變化。通過并行調(diào)度模型中非空顏色集合的定義，借助托肯顏色表達(dá)資源的分類及組合，可以準(zhǔn)確地描述項(xiàng)目群各級(jí)任務(wù)的資源需求、任務(wù)間資源流動(dòng)、任務(wù)持續(xù)時(shí)間等資源管理相關(guān)信息。

4 建模實(shí)例和仿真

以某房地產(chǎn)開發(fā)小區(qū)的建設(shè)項(xiàng)目群實(shí)施階段為例，該小區(qū)中2個(gè)標(biāo)段(各3個(gè)單項(xiàng)工程)的并行實(shí)施項(xiàng)目(p1和p2)，基于CPN Tools建模仿真平臺(tái)[10]構(gòu)建模型(如圖4—5所示)。圖4中描述2個(gè)項(xiàng)目的實(shí)施邏輯關(guān)系為并行，在t3實(shí)現(xiàn)同步。t1和t2為替代變遷，其具體的子網(wǎng)描述見圖5。

圖4 CPN Tools建模實(shí)例(父網(wǎng))

圖5 CPN Tools建模實(shí)例(子網(wǎng))

結(jié)合模型可以進(jìn)行以下的仿真分析：

1)資源的沖突發(fā)現(xiàn)。在多項(xiàng)目的實(shí)施中，由于資源的共用性和獨(dú)占性，當(dāng)并行任務(wù)需要同類資源，而此類資源數(shù)量不足時(shí)，模型中相應(yīng)變遷獲得資源分配的時(shí)間戳比發(fā)出資源請求的時(shí)間戳后延，以此可判斷資源沖突的出現(xiàn)。

2)項(xiàng)目進(jìn)度分析。通過“@+”賦予變遷時(shí)間延遲描述各任務(wù)的執(zhí)行時(shí)間。由于資源沖突的資源優(yōu)先準(zhǔn)則(通過任務(wù)優(yōu)先權(quán)或任務(wù)變遷使能發(fā)生幾率的設(shè)定)及迭代的不確定性，多次仿真試驗(yàn)，擬合多項(xiàng)目的完工概率曲線或工期風(fēng)險(xiǎn)度曲線圖，進(jìn)行多項(xiàng)目進(jìn)度分析。

3)網(wǎng)性質(zhì)分析。使用CPN Tools的State space對建立的模型實(shí)例進(jìn)行系統(tǒng)語法檢驗(yàn)和結(jié)構(gòu)分析，主要是可達(dá)性、有界性和活性等網(wǎng)性質(zhì)分析，由此預(yù)測多項(xiàng)目之間是否存在死鎖現(xiàn)象，以便確定模型結(jié)構(gòu)上的正確性。

5 結(jié)束語

本文分析了多項(xiàng)目并行調(diào)度的特點(diǎn)，提出了基于著色Petri網(wǎng)構(gòu)建多項(xiàng)目并行調(diào)度模型的形式化定義和具體思路?；贑PN的多項(xiàng)目并行調(diào)度模型能更好地表達(dá)多項(xiàng)目并行實(shí)施的特點(diǎn)，描述資源的共享，滿足多項(xiàng)目建模的要求，輔助多項(xiàng)目管理者決策。

基于CPN的多項(xiàng)目并行調(diào)度模型是分層模型，最底層子網(wǎng)中庫所和變遷對應(yīng)的參數(shù)可依據(jù)全國各專業(yè)消耗量定額或企業(yè)定額進(jìn)行設(shè)定。最底層子網(wǎng)參數(shù)一旦設(shè)定，運(yùn)行該模型，則時(shí)間、資源等運(yùn)行數(shù)據(jù)會(huì)通過替代變遷及端口結(jié)點(diǎn)庫所進(jìn)行傳遞。模型上層子網(wǎng)中替代變遷關(guān)聯(lián)的執(zhí)行時(shí)間均為下層子網(wǎng)的仿真運(yùn)行時(shí)間，克服了傳統(tǒng)工程項(xiàng)目網(wǎng)絡(luò)模型任務(wù)時(shí)間的估計(jì)過于粗略、資源的估計(jì)不夠準(zhǔn)確的局限。

各類工程的差異(例如建筑工程和機(jī)械工程)對于這個(gè)模型的影響需要進(jìn)一步探討。文中主要針對建筑工程項(xiàng)目群建模與仿真，其他專業(yè)類別工程的差異將體現(xiàn)為變遷、庫所、托肯及相互間關(guān)系(順序、并行、并發(fā)等)的重新定義，但Petri網(wǎng)的建模技術(shù)與仿真分析方法的運(yùn)用可以實(shí)現(xiàn)統(tǒng)一。

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

[2]羅福周,韓言虎,李松濤.大型復(fù)雜項(xiàng)目戰(zhàn)略聯(lián)盟合作伙伴選擇：基于組合賦權(quán)的灰色關(guān)聯(lián)度評價(jià)[J]. 技術(shù)經(jīng)濟(jì)與管理研究,2013(4):8-11

[3]Halpin D W, Riggs L S. Planning and Analysis of Construction Operation [M]. New York： John Wiley & Sons Inc ,1992.

[4]Kara S, Kayis B, Kaebernick H. Concurrent Resource Allocation (CRA):A Heuristic for Multi-Project Scheduling with Resource Constraints in Concurrent Engineering[J]. Concurrent Engineering, 2001,9(1):64-73

[5]陸虎進(jìn).動(dòng)態(tài)多項(xiàng)目資源配置及其改進(jìn)方法[D].南京：東南大學(xué),2005,05.

[6]陳永森.企業(yè)項(xiàng)目群資源配置優(yōu)化方法及其應(yīng)用研究[D].長春：吉林大學(xué),2009.

[7]吳哲輝.Petri網(wǎng)導(dǎo)論[M].北京：機(jī)械工業(yè)出版社,2006.

[8]楊學(xué)紅,胡志根.基于Petri網(wǎng)隧洞施工過程的系統(tǒng)建模[J].水電能源科學(xué),2001,19(4):33-36.

[9]Jensen K.An Introduction to the Theoretical Aspects of Colored Petri Nets[J]. Computer Science,1994,8(3):230-272

[10]University of Aarhus. Online CPN Tools [EB/OL].(2012-10-25). [2014-1-21].http：//cpntools.org/start.

(編校：葉超)

ResourceManagementModelingofParallelSchedulingforMulti-projectBasedonCPN

LI Hai-ling1，LIU Ke-jian2，TAO Xue-ming1

(1.SchoolofArchitectureandCivilEngiheering,XihuaUniversity,Chengdu610039China；2.SchoolofMathematicsandComputerEngiheering,XihuaUniversity,Chengdu610039China))

The modeling of parallel scheduling for multi-project is one of the most important parts to plan and control multi-project management. The characteristics of the parallel scheduling for multi-project are analyzed. Petri net is good at describing the random, inter task concurrency, synchronization and parallel, so it can express the characteristics of the parallel scheduling of the multi-project well. It overcomes the failings of current parallel scheduling model for multi- project modeling. The typical example and analysis method are introduced and the feasibility and effectiveness of the model to parallel schedule for multi-project based on CPN are proved.

parallel scheduling；multi-project；resource management；CPN

2014-05-14

國家自然科學(xué)基金項(xiàng)目(60872089)；西華大學(xué)重點(diǎn)科研基金項(xiàng)目(z1320607)

李海凌(1976—)，女，副教授，博士，碩士生導(dǎo)師，主要研究方向?yàn)榧夹g(shù)經(jīng)濟(jì)與項(xiàng)目管理。

TB114.2

：A

：1673-159X(2015)01-0103-04

10.3969/j.issn.1673-159X.2015.01.019