时间Petri网在项目进度管理建模中的应用

2014-09-15杨旭沈俊鑫

价值工程 2014年22期

杨旭+沈俊鑫

摘要：通过分析现有时延Petri网和时间Petri网在项目进度管理仿真模型的不足，提出基于库所时间约束Petri网的项目进度管理模型，该模型具备全局时钟特性，不仅能体现工序自身时间参数，同时能对外部资源等工序外延时间约束进行建模。实例仿真结果表明该模型的有效性。

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.

关键词：资源约束；进度优化；库所时间约束Petri网

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

中图分类号：TP311.5 文献标识码：A 文章编号：1006-4311（2014）22-0004-04

0 引言

近年来，越来越多的组织面临多项目并行实施，项目间存在资源竞争与共享，资源约束下多项目进度优化调度是近几年来项目管理研究热点和难点。传统网络项目管理技术虽能有效表达工序自身时间因素以及工序间的逻辑关系，但仍然存在网络图过于复杂、工序时间参数及资源需求估算粗放、忽略外部突发事件、缺乏项目实施过程动态控制等缺点，对于复杂多项目缺乏动态管理[1]。Petri网集可视化建模、形式化分析及动态仿真于一体的建模工具，在描述并发、异步、非确定性或者随机性为特征的系统有独特的能力，使得Petri网广泛应用于项目进度管理建模[2]。

本文在研究现有时间Petri网在项目进度管理模型应用基础上，总结现有基于时间Petri网的项目进度管理模型优缺点，提出基于库所时间约束Petri网的项目进度管理模型，该模型能够对项目管理中工序逻辑关系、时间约束及资源约束进行建模，为项目进度管理提供可视化、形式化建模工具。

1 项目进度管理研究现状

1.1 基于网络计划技术的项目管理模型研究现状传统项目进度管理方法主要有横道图和网络计划技术两种。横道图直观便于理解，但不善于表述工序间复杂逻辑关系，使用横道图对大型项目建模后模型庞大，不利于项目控制。网络计划技术则能较好地体现工序间逻辑关系，网络计划技术主要有：关键路径法（Critical Path Method，CPM）、计划评审技术（Project Evaluation and Review Technique，PERT）以及图形评审技术（Graphic Evaluation and Review Technique，GERT）等。CPM可以有效地确定各项工序的机动时间以及整个项目的关键路径和关键工序，PERT基于概率统计思想，采用三点估算法确定工序时间延迟，使得PERT对工序时间参数估算精确度高于CPM方法。GERT在PERT基础上增加决策点，工序逻辑关系存在非确定性，可进行条件和概率处理。传统网络计划技术已成功应用于离线项目进度管理，但存在如下限制：

①传统网络计划技术对项目经理要求较高，要求事前能够准确给出项目工序，以及准确估算各项工序所需时间和资源消耗，同时假设所有工序时间参数需服从β、γ、正态或泊松等标准概率分布；

②传统网络计划技术无法描述外部突发事件，例如资源短缺、设备故障等对项目进度调度的影响，当出现外部突发事件时，该方法不能及时、动态调整项目进度调度方案，缺乏动态性、预测性与实时性；

③采用传统网络计划技术构建的网络图不允许存在回路。

1.2 基于时间Petri网的项目管理模型研究现状项目管理从本质上来说就是一个离散事件动态系统，其特点在于事件发生在离散的时间点上，具有并发、异步和突发性[3]，Petri网具备直观的图形建模、严谨的数学分析、动态灵活仿真等特性，广泛应用于动态离散异步系统建模[4]。为了解决传统网络计划技术在项目管理中的不足，国内外很多学者提出了基于Petri网的项目进度管理模型。罗亚[5]在传统PERT图基础上添加资源库所和活动节点，构建基于Petri网的产品生产模型，KJ LIU[6]将Petri网应用于软件项目计划管理及变更控制，段波[7]将Petri网应用于生产制造系统建模及作业调度，陈翔[8]证明了可以将双代号网络图映射到Petri网模型。

为了对传统网络计划技术工序持续时间进行建模，马俊等[9]对传统Petri工序时间参数估算及其分布进行改进，提出基于时延Petri网（Timed Petri Net， TdPN）的进度管理模型，应用于房地产开发进度管理。时延Petri网变迁激发不是瞬间完成，而是需要经过一个时间延迟di。为了允许工序持续时间是一个随机变量，沈俊鑫[4，10]在变迁持续时间引入随机变量，提出基于随机Petri网（Stochastic Petri Net， SPN）的项目进度管理模型，该模型允许工序持续时间di为任意随机分布，并证明了当di服从λ分布时，该模型状态转移具备马尔科夫特性。为了表示传统网络计划技术工序最早开始时间ES和最迟开始时间LS，国内外学者对时延Petri网进行改进，即施加在时延Petri网变迁上的时间延迟di为时延区间（Tmin，Tmax），提出基于时间Petri网（Time Petri Net， TPN）的项目进度管理模型。宋巍[11]、Berthomieu[12]构建基于时间Petri网的项目进度计划优化模型，宋巍[11]则将时间Petri网应用于项目关键路径、最短工期求解。为了降低基于时延Petri网的项目进度管理模型复杂度，实现大型复杂项目建模，国内外学者引入了分层Petri网模型，如满庆鹏等[13]通过构建基于分层时间Petri网的分级施工网络计划模型，将时间Petri网应用于施工项目网络计划优化。李海凌[14]、FF Cheng[16]、张绍阳[1]通过构建基于分层Petri网的资源管理模型，该模型很好地描述了工程建设项目工序持续时间、资源配置及信息传递，解决了建设工程项目实施阶段进度、资源优化问题；该模型采用仿真工序时间参数计算方法，解决了仿真技术进行进度计划时不能给出工序时间参数的弊端。

大量研究结果表明，时间Petri网已广泛应用项目进度管理建模，吴哲辉[17]证明了时间Petri网的模拟能力比传统Petri网要强，而且时间Petri网的模拟能力与图灵机相等。基于时间Petri网的项目进度管理模型不仅能够将网络图映射到时间Petri网模型，实现传统网络计划技术所有功能。这类模型不仅可以使项目管理者实时掌控项目进展，控制项目工期，还可以根据项目实际执行情况对现有的项目计划调度实施动态调整。但仍存在以下问题：

①现有基于时间Petri网的项目进度管理模型不具备全局时钟特性。TdPN时间延时di表示库所中标识的消耗和变迁的执行需要经过di完成，此时间延迟，只赋予工序i，不具备全局时钟特许。在项目管理模型中，若T0时刻第i道工序（变迁ti）外部条件准备就绪，且工序i在T0时刻执行，则T0+di工序i执行完毕。但在变迁ti激发的di这段时间内，变迁ti前集库所集ti中的标记在ti激发时消耗掉，但是变迁ti后集库所集ti却需等待di才能得到相应标记，此时该Petri网模型处于无状态，由此产生悖论[11]。②现有基于时间Petri网的项目进度管理模型仍然比较复杂。现有时间Petri网在对工序的逻辑关系进行建模时，不仅增加了符号，而且在现有时间Petri网中，工序的逻辑关系中的时间冗余，需要借助虚工序来实现。③基于时间Petri网的项目进度管理模型不能体现项目资源对工序执行的时间约束。不论是TdPN、SPN还是TPN模型，时间参数只引入到变迁本身，即只对工序自身时间参数建模，无法对工序外延，例如资源约束进行时间建模。

2 基于库所时间约束Petri网项目进度管理模型

2.1 库所时间约束Petri网

定义1时间约束Petri网（Place Timing constraint Petri Net， PTcPN）是一个七元组∑=（P，T；F，W，M0，D，Ip），如图1所示，其中：

①∑=（P，T；F，W，M0）是一个Petri网，但此时弧T×P上的权重w不再表示任务变迁ti所产生的标记，而仅说明库所在状态持续阶段所需要的资源；

②D：T→R+是变迁的延时函数，图1中指td（ti）；

③Ip为关联库所的实数对[Tmin，Tmax]的集合，图1中，Ip指（tmin（pi），tmax（pi））。

图1中，用圆圈“○”表示库所Place，用“●”黑点表示库所中的标记Token，标记颜色表示项目资源类别，用矩形方块“？荠”表示变迁Transaction，即工序，从库所到变迁或是从变迁到库所的关系用有向弧“→”表示，上述三个元素表示了系统的静态模型。

PTcPN增加了事件发生条件的时间要求，在库所和变迁都有时间约束，库所时间约束借鉴TPN思路，而变迁时间约束借鉴TdPN思路。为了克服TdPN模型可能是整个Petri网模型处于无状态中以及TPN模型变迁时延区间（tmin（ti），tmax（ti））对变迁的时间约束为局部时钟而非全局时钟，PTcPN引入全局时钟概念，Ip所关联的实数对[Tmin，Tmax]中Tmin、Tmax分别为全局时钟下库所最早/最迟进入时延。图1中，设全局时钟以T0为起点，变迁t1和t2激发后，使得库所p2和p3最早可以在全局时钟分别为：tmin（t1）+td（t1）和tmin（t2）+td（t2）获得标记Token。

2.2 基于PTcPN的项目进度管理模型

2.2.1 模型含义基于PTcPN的项目进度管理模型建模过程中， PTcPN模型的状态标识表示项目执行过程中资源状况，初始标识M0表示项目未开始实施的计划模型，其他状态标识M=（M（p1），M（p2），…，M（pi））表示项目执行过程中项目的某个状态，即项目快照。模型的状态空间则是项目执行过程中所有可能状态的集合，随着变迁的激发、库所标记的移动体现了模型状态的变化，即项目的执行，模型标识的转化体现系统的动态行为。

2.2.2 模型状态空间 PTcPN模型状态空间指模型可达图所有状态的集合，模型状态空间反应了项目执行过程中项目可能出现的状态（工序执行状态及资源分配状态）的集合，模型的状态转移序列δ=（M0t1M1…tiMi…tnMn）表示项目从初始状态M0经过若干个任务序列的执行转变成状态Mn，即项目可能出现的任意两个状态之间所需经历的活动执行序列。模型可达图构造算法如下：

①T（∑）的初值只有根节点r，Mr=M0，即Mr为初始标识；

②令x为T（∑）的叶子节点，若？坌t∈T，在Mr状态下均有权发生，x为真节点；若从根节点r到x的路径上有另一个节点y，y≠x，但是My=Mx，则x也是真叶节点，若T（∑）所有的叶节点均为真叶节点，则算法结束。否则执行③；

③若T（∑）有叶节点x，但是x不是真叶节点，那么在Mx至少有一个变迁t可以发生。对Mx授权发生的每个变迁t∈T，在T（∑）上添加一个新节点y，y是x的子节点，从x到y的有向弧用变迁t标记，节点y的标记My按下定义：首先计算出Mx的后继M′，即对所有s∈S，M′（s）=Mx（S）-W（s，t）+W（t，s），然后计算My，对所有s∈S，有：

My（s）=

ω，若从r到y的路径上有节点z，使得Mz

④回到步骤②。

2.2.3 项目时间计算在PTcPN模型中，库所的时间约束[tmin（pi），tmax（pi）]需要通过计算获得。库所pi的最早全局时钟为其前继变迁集中变迁的最早全局时间与变迁持续时间之和的最大值。

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

库所pi的最迟全局时钟为其后继变迁集中变迁的最迟全局时间与变迁持续时间之差的最小值。

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

在PTcPN模型中库所时差为0的库所为关键库所，所有关键库所及其对应变迁组成项目的关键路径。pi为关键库所，当且仅当：tmin（pi）-tmax（pi）=0。（3）

3 实例分析

3.1 项目描述为了说明PTcPN在项目进度管理中的应用，本文以某软件开发项目为例，着重对软件开发过程进度管理进行分析。项目工序逻辑关系、工期、资源要求如表1所示。

3.2 项目PTcPN建模根据PTcPN定义，以及表1项目信息，构建基于PTcPN的项目进度模型如图2所示，其中库所p0和p15为辅助库所，无实际含义。

3.3 项目状态空间分析根据可达图构造算法，求得图2对应的可达图如图3所示。

项目状态空间反应了整个项目可能存在的调度方案，状态Si指项目执行过程可能处于的状态，状态Si到状态Sj箭头序列表明了项目从状态Si到状态Sj需经历的工序调度序列。项目管理者可以根此预测项目状态空间预测项目当前状态下可能出现的各种调度方案以及特定调度方案下项目所处的下一个状态，使得项目调度与执行具有可预测性。

3.4 项目时间计算根据式（1）和式（2）分别求解模型各库所时间约束，根据式（3）确定项目关键路径，如表2所示。

由表2可得项目关键路径为：A→B→C→F→J→M→N，总工期为26。

4 结语

本文在综合比较网络计划技术以及现有时间Petri网在项目进度管理建模优缺点基础上，针对现有时间Petri网在项目进度管理建模不具备全局时钟、模型相对复杂以及无法体现资源约束等不足，提出了基于库所时间约束Petri网，将时间约束扩展至库所。实例分析说明，基于库所时间约束Petri网的项目进度管理模型更好了体现了资源的时间约束，该模型不仅能够替代传统网络计划技术，实现工序的逻辑关系建模，简化项目网络图，实现项目时间管理，模型状态空间也为项目管理者提供了更多决策信息。限于篇幅，本文未对非肯定型项目实现案例应用及仿真。

参考文献：

[1]张绍阳.基于Petri网的公路施工进度计划及资源优化研究[D].长安大学博士学位论文，2006.

[2]李海凌，史本山，刘克剑.基于Petri网的建设工程项目实施阶段资源建模与仿真[J].计算机应用研究，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]沈俊鑫.基于扩展Petri网的经营性公共基础设施TOT特许期决策研究[D].昆明理工大学博士学位论文，2012.

[5]罗亚.一种基于PERT图的Petri网模型构建方法[J].系统仿真学报，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]段波，赵稳庄，仉树军.Petri网在制造系统建模与仿真中的应用[J].航空精密制造技术，2008，44（5）：52-56.

[8]陈翔.基于Petri网及矩母函数的计划评审技术[J].北京理工大学学报，2010，30（9）：1121-1125.

[9]马俊，廖伟志，李书举，罗锦坤.基于时延Petri网的房地产业工期计划管理[J].广西师范学院学报：自然科学版，2012，29（1）：66-71.

[10]沈俊鑫，王松江.基于随机Petri网的TOT特许期风险分析模型[J].项目管理技术，2010（12）：87-91.

[11]宋巍，于瑞强.利用时间约束Petri网进行项目绩效分析[J].小型微型计算机系统，2010，31（2）：276-280.

[12]Bernard Berthomieu， Florent Peres，Francois 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]满庆鹏，王要武，李晓东.基于Petri网的施工进度建模及优化方法[J].系统管理学报，2009，18（2）：193-198.

[14]施国强，李伯虎，柴旭东.基于着色Petri网的复杂产品开发多项目调度建模研究[J].系统仿真学报，2007，19（17）：3869-3873.

[15]李海凌，史本山，刘克剑.基于Petri网的建设工程项目实施阶段工作流建模与仿真[J].计算机应用，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]于汪洋，吴哲辉.时延Petri网模拟能力研究[J].微计算机应用，2009（8）：32-37.