支持并行调度的多项目资源管理CPN建模

李海凌，刘克剑2，陶学明

(1.西华大学建筑与土木工程学院，四川 成都 610039；2.西华大学数学与计算机学院，四川 成都 610039)

·建筑与土木工程·

支持并行调度的多项目资源管理CPN建模

李海凌1，刘克剑2，陶学明1

(1.西华大学建筑与土木工程学院，四川 成都 610039；2.西华大学数学与计算机学院，四川 成都 610039)

构建良好的多项目资源调度模型已成为项目型企业多项目管理计划与控制的关键性基础工作。在分析多项目并行调度特点的基础上，基于Petri网擅长描述随机性、任务间并发、同步、并行等系统特征的优势，克服当前已有的多项目并行调度模型的不足，构建了基于CPN的多项目并行调度模型。通过建模实例阐述了模型的仿真分析方法，证明了基于着色Petri网构建多项目并行调度模型的可行性和有效性。

并行调度；多项目；资源管理；CPN

项目型企业在同一时间内实施多个项目的情况越来越普遍，将并行项目视作一个整体的多项目调度问题已得到了越来越多企业的重视。遵循先进有效的项目管理模式，并在管理模式基础上构建良好的多项目调度模型作为指导以辅助管理，成为多项目管理成败的关键。

多项目并行调度建模就是企业基于集成协同理论，在多项目环境下，建立多项目并行实施的调度管理模型。通过该模型模拟、分析、优化、监控多项目进度计划，找出实施多项目的资源冲突或瓶颈，优化企业资源配置，支持各项目建设团队的协作，最终实现企业组织价值的最大化。

本文从全面分析多项目并行调度的特点出发，在比较已有建模方法的基础上，提出了基于着色Petri网(colored petri net，CPN)的调度模型。该模型能够表达多项目调度的静态属性和动态特性，为多项目环境下的管理人员的控制及决策提供向导。

1 多项目并行调度的特点分析

项目型企业的多项目管理以项目为中心，关注整体项目的顺利完成，这其中就包括多项目调度的分析和优化[1]。项目建设模式将直接决定多项目调度的特点。并行工程是项目及其相关过程一体化实施的一种系统化的建设模式，其执行可组建项目群集成管理团队(integrated programme team，IPT)来完成[2]，具有层次性、并行性和开放性的特点。这些特点决定了项目型企业具有多项目调度的特点。

1)层次性：进行物理或逻辑的分解以体现多项目实施的层次性。多项目实施物理上的层次性可表现为各个项目的并行、同一项目的分标段实施，或者流水实施中的分区实施。逻辑上的层次性则可以表现为依据WBS进行的项目分解。多项目的并行可表现为经过层次分解后多个任务子集的并行。

2)冲突性：指项目资源的共用性和独占性引起的资源冲突。共用性是指并行任务的实施需要同一类资源；独占性是指同类资源中某一确定资源在同一时间只能被一个任务所使用：因此，资源的共用性和独占性在资源有限时会导致冲突。企业资源大多是有限的，并行展开的多项目很难避免冲突。

3)迭代性：通常是指由于技术关联引起的技术借鉴以迭代方式进行的任务间反复。在多项目的实施过程中，也指质量导致的返工修复。

4)开放性：在多项目环境下，企业随时可能有新项目加入或己有项目完成退出，一个高优先级项目的加入会引起计划的重排[1]；所以，多项目管理是动态开放的。

2 建模方法选择

传统网络计划模型是基于CPM或PERT，将多个项目通过添加首尾虚任务整合成一个“大项目”的网络图[1]。它能够表达项目间的先后实施顺序，但只能描述发生一次的活动，不能表达多项目的迭代性和资源冲突性，缺乏有效的方法进行多项目动态调度。

循环运行网络(cycle operation network，CYCLONE)是在网络计划中引入排队论和仿真技术，对具有随机时间的循环施工过程进行仿真[3]。CYCLONE可以很好地表达实施过程的随机性，却对任务同步、冲突、并发的描述无能为力[4]。

数学规划是一种常用的多项目资源优化模型，通过假设定义，将多项目转化成单项目问题进行优化求解，其解决问题的路径存在理论局限：资源在多个项目之间的分配和在一个项目内的分配并不完全一致，单个项目实施的实质是其内部各个活动依照内在规律的先后执行，这样的实施规律在多个项目之间却并不存在[5]，也不能体现上述多项目的层次性和开放性。两层决策模型对数学规划进行了改进：将资源按照项目的不同进行分配，降低乃至停止资源切换。但两层决策求解所需要的初始可行解很难确定，且最终得到的不是最优解只是可行解[6]。

Petri网是一种集严格的形式化定义、易懂的图形表达、直观的仿真运行、成熟的数学分析等特点为一体的建模技术。它可以动态地进行系统描述，适合于活动的即时监控，是一种完全基于过程的针对复杂系统的有效建模工具[7]。Petri网不仅具备CYCLONE描述系统随机性的优势，还擅长描述任务间并发、同步、并行等系统特征[8]。在大型复杂系统建模中，原型Petri网状态维数会急剧增加，建立的模型将非常庞大，系统结构缺乏柔性[1]。赋予原型Petri网颜色概念所形成的CPN增强了Petri网的描述能力，有利于解决状态空间爆炸的问题。CPN与其他建模方法相比，能更好地描述多项目调度的特点，适合于多项目并行调度建模。

3 基于CPN的多项目并行调度建模

3.1 多项目并行调度模型的形式化定义

定义1 多项目并行调度模型可以用一个九元组的CPN=(P,T：F,N,R,C,G,E,M0)[9]来描述，其中：

1)(P,T：F)为一个原型Petri网，P、T、F分别表示库所(place)、变迁(transition)、弧(arc)的有限集合；

2)N：节点函数(node function)，是定义F到P×T∪T×P的函数。相同顺序的节点对(如从节点1到节点2)容许多个不同的弧，因此需要通过N进行区分；

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

4)C：颜色函数(color function)，将库所P映射到非空有限类型颜色集合R，描述库所的资源类别及数量等信息；

5)G：布尔型函数，T映射到∀t∈T：[Type (G(t))=B∧Type(Var(g(t)))⊆R]的守卫函数(guard function)，函数中的变量类型属于R，省略时默认为true；

6)E：F映射到∀f∈F：[Type(E(f))=C(P(f))MS∧Type(Var(E(f))⊆R]的弧表达式函数(arc expression function)，函数值为弧相应库所颜色集上的多重集，函数中的变量类型属于R；

7)M0：库所P映射到∀p∈P：[Type(M(p))=C(P)MS]的初始化函数(initialization function)，函数值是库所颜色集上的多重集。

3.2 多项目并行调度CPN颜色定义

1)colset P = int timed；声明一个带时间戳的整数颜色集，表示子项目的状态。

2)colset INT = int；声明一个整数颜色集。

3)colset req = record n：INT*m：INT*tim：INT*rn：INT；表示资源请求。其中，n为子项目编号，m为子项目分解任务编号，tim为发出资源请求的时间，rn为资源的需求数量。

4)colest res = int；表示项目的资源分类。

5)colset ress = list res；表示项目的资源列表。

6)colset mtres = record m：INT*t：INT*r：ress；表示第m个分解任务在t时间获得的资源列表。

3.3 多项目并行调度特点的建模

根据上述分析与定义进行多项目并行调度特点建模。

3.3.1 层次性

通过替代变迁实现多项目实施的层次性描述，如图1所示。T1为多项目中某子项目的实施，为替代变迁，其所在页为上层父网。T1分别与Reqres(资源请求库所)、Res(资源分配库所)、Retres(资源存放库所)相关联。T1具体实施见下层子网虚线框内。T11、T12和T13表示T1项目中分解任务的实施，它们均需在Reqres、Retres、Res中获得资源支持。父网和子网间的资源信息数据通过关联的资源库所实现分层传递。

图1 项目分层建模

3.3.2 冲突性

同类属性的资源形成一个资源集合，即资源池pool。图2中R3为资源分配变迁，进行pool1、pool2、pool3中资源数量能否满足Reqres中资源(有可能是资源请求队列)需求的判断。如果满足，R3将相应数量资源分配到对应的任务库所Res1、Res2、Res3、Res4中供其使用；如果不满足，则产生资源冲突。

3.3.3 迭代性

传统网络计划模型只表达了任务间信息的单向传递、顺序进展，任务间的迭代实施特性却被忽略；因此只是项目实施的静态描述。CPN可以通过函数声明、相关库所及变迁进行迭代的清晰表达。

图3 迭代的CPN表示

3.3.4 开放性

CPN可以通过增减库所或变量表示项目的加入或退出。若并行项目不多，模型增加P库所代表新项目；若并行项目较多，模型通过在多项目库所中加入表示新项目的托肯，将有利于降低Petri网的状态维数。

依据上述项目实施的层次性、冲突性、迭代性、开放性的Petri网建模描述，多项目并行调度模型是一个分层模型，其模型特性与其资源管理需求有相似之处。资源的类别、冲突与否及资源消耗反映在并行调度模型中就是托肯的着色、变迁使能及托肯的移动和变化。通过并行调度模型中非空颜色集合的定义，借助托肯颜色表达资源的分类及组合，可以准确地描述项目群各级任务的资源需求、任务间资源流动、任务持续时间等资源管理相关信息。

4 建模实例和仿真

以某房地产开发小区的建设项目群实施阶段为例，该小区中2个标段(各3个单项工程)的并行实施项目(p1和p2)，基于CPN Tools建模仿真平台[10]构建模型(如图4—5所示)。图4中描述2个项目的实施逻辑关系为并行，在t3实现同步。t1和t2为替代变迁，其具体的子网描述见图5。

图4 CPN Tools建模实例(父网)

图5 CPN Tools建模实例(子网)

结合模型可以进行以下的仿真分析：

1)资源的冲突发现。在多项目的实施中，由于资源的共用性和独占性，当并行任务需要同类资源，而此类资源数量不足时，模型中相应变迁获得资源分配的时间戳比发出资源请求的时间戳后延，以此可判断资源冲突的出现。

2)项目进度分析。通过“@+”赋予变迁时间延迟描述各任务的执行时间。由于资源冲突的资源优先准则(通过任务优先权或任务变迁使能发生几率的设定)及迭代的不确定性，多次仿真试验，拟合多项目的完工概率曲线或工期风险度曲线图，进行多项目进度分析。

3)网性质分析。使用CPN Tools的State space对建立的模型实例进行系统语法检验和结构分析，主要是可达性、有界性和活性等网性质分析，由此预测多项目之间是否存在死锁现象，以便确定模型结构上的正确性。

5 结束语

本文分析了多项目并行调度的特点，提出了基于着色Petri网构建多项目并行调度模型的形式化定义和具体思路。基于CPN的多项目并行调度模型能更好地表达多项目并行实施的特点，描述资源的共享，满足多项目建模的要求，辅助多项目管理者决策。

基于CPN的多项目并行调度模型是分层模型，最底层子网中库所和变迁对应的参数可依据全国各专业消耗量定额或企业定额进行设定。最底层子网参数一旦设定，运行该模型，则时间、资源等运行数据会通过替代变迁及端口结点库所进行传递。模型上层子网中替代变迁关联的执行时间均为下层子网的仿真运行时间，克服了传统工程项目网络模型任务时间的估计过于粗略、资源的估计不够准确的局限。

各类工程的差异(例如建筑工程和机械工程)对于这个模型的影响需要进一步探讨。文中主要针对建筑工程项目群建模与仿真，其他专业类别工程的差异将体现为变迁、库所、托肯及相互间关系(顺序、并行、并发等)的重新定义，但Petri网的建模技术与仿真分析方法的运用可以实现统一。

[1]施国强,李伯虎,柴旭东.基于着色Petri网的复杂产品开发多项目调度建模研究[J].系统仿真学报,2007,19(17):3869-3872,3948.

[2]罗福周,韩言虎,李松涛.大型复杂项目战略联盟合作伙伴选择：基于组合赋权的灰色关联度评价[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]陆虎进.动态多项目资源配置及其改进方法[D].南京：东南大学,2005,05.

[6]陈永森.企业项目群资源配置优化方法及其应用研究[D].长春：吉林大学,2009.

[7]吴哲辉.Petri网导论[M].北京：机械工业出版社,2006.

[8]杨学红,胡志根.基于Petri网隧洞施工过程的系统建模[J].水电能源科学,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

国家自然科学基金项目(60872089)；西华大学重点科研基金项目(z1320607)

李海凌(1976—)，女，副教授，博士，硕士生导师，主要研究方向为技术经济与项目管理。

TB114.2

：A

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

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