《资源多约束进度网络的风险评估》-工学论文，软件工程论文-论文范文参考-科学狗论文网

标题

资源多约束进度网络的风险评估

范文

蔡永勇++桑笑楠++张周磊++徐永红

摘要：在项目管理中由于项目庞大、持续周期长、影响因素繁多，不可避免地会面对潜在的风险。本文对项目潜在的风险进行评估，让项目的管理者对项目有一个长远的认识，防范风险于未然。本文应用资源多约束下项目进度调度（resource-constrained project scheduling problem，RCPSP）问题模型，对进度风险评估系统进行了需求分析和模块划分，设计了系统的框架层次、数据库、资源多约束下的蒙式仿真算法，给出了依据仿真结果计算进度风险和成本风险的统计思路。

关键词：进度风险评估；蒙式仿真；成本风险；资源多约束

中图分类号：TP391. 41

文献标识码：A

DOI： 10.3969/j.issn.1003-6970.2015.07.008

0 引言

项目管理是通过项目经理和项目组织的努力，运用系统理论和方法对项目及其资源进行计划、组织、协调、控制，旨在实现项目特定目标的管理方法体系。项目管理的对象是项目，即一系列的临时任务，它的目的是通过运用科学的项目管理技术，更好地实现项目目标。项目管理的职能与其它管理的职能是完全一致的，即是对组织的资源进行计划、组织、指挥、控制。资源是指项目所在的组织中可得到的、为项目所需要的那些资源，包括人员、资金、技术、设备等，在项目的管理中，时间是一种特殊的资源。项目管理的任务是对项目及其资源的计划、组织、协调、控制。

任何项目的策划和执行都包含大量不同的活动及各种人力、物力资源。资源是项目执行过程中不可缺少的重要组成部分，而这些资源的有效的可用量往往是有限的。有的资源是可循环利用的，而有些则是一次性的。如何以最佳方式安排执行项目中的各个活动，以使其顺利完成，就构成了资源受限下项目进度调度问题的基本概念。

资源约束下项目调度问题（resource-constrained project scheduling problem，RCPSP）是一类应用范围十分广泛的组合优化问题，它研究在资源稀缺的情况下满足资源的约束，合理安排任务的开始时间和结束时间，从而在资源最优利用的同时实现既定目标的最优化。它被证明是一种强NP难题。资源约束下项目调度问题模型丰富，根据资源类型和项目结构的不同可以分为众多种类，许多组合优化问题是RCPSP的特殊情形。例如作业车间（job shop）调度，流水车间（flow shop）调度等。此外RCPSP广泛存在于建筑工程，软件开发，飞机和轮船制造等单件或小批量生产方式的企业中。因此研究RCPSP具有重要的理论和现实意义，可以广泛应用于实际。

近年来，RCPSP得到了许多扩充。鉴于应用背景和目标函数的不同，RCPSP可扩展为时间/费用权衡问题（TCTP），资源水平问题（RLP）和净现值（NPV）问题等。进一步考虑不确定因素，又产生了随机调度问题。作为项目调度的有效工具，甘特图、关键路径法和计划评审技术已广泛应用于各种项目调度问题。在算法方面，尤其是求解算法（包括智能算法）得到了广泛而深入的讨论，同时得到了许多成功应用。

1 系统需求分析与设计

本文在功能方面，针对管理者的日常需求，将资源多约束下进度风险评估系统功能分为：项目管理，资源管理，项目网络图（任务属性设置），项目仿真，项目仿真版本管理等项功能。

项目管理：对项目的任务节点信息和节点之间的约束关系等进行记录和管理，并可以对项目进行资源分配。

资源管理：对资源的属性和数量等进行记录和管理。

项目网络图：展示项目各个任务节点之间的约束关系，形成网络图。可以对每个非概要任务节点进行任务属性的设置和资源需求的设置，为仿真进行准备。

项目仿真：对设置好任务节点属性的项目进行带资源约束的仿真或不带资源约束的仿真。

项目仿真版本管理：管理所有项目仿真好的版本.可以选择某个版本进行查看，也可以删除某个版本。

因此，本系统包括项目管理模块、项目网络图模块、仿真版本和新仿真模块、仿真结果模块、资源管理模块。

项目管理模块：提供了必要的项目管理及资源分配功能。用户可以对项目进行管理，例如，通过读人XML配置文件添加项目、修改项目描述、查看项目XML文件等功能。用户也可以将已经存在的资源分配给某一个具体项目，以便为有资源约束的仿真做准备。

项目网络图模块：展示项目的任务节点信息和它们的相互关系，以网络图的形式表示出来。用户可以通过点击某个具体节点设置它的属性（统计学分布、期望、方差等）和需求资源的情况，为带资源的仿真和不带资源的仿真做进一步准备。

仿真版本和新仿真模块：管理和显示已经存在的仿真版本和新建一个版本开始仿真。用户可以选择一个已经存在的仿真版本进行查看或者删除，也可以新建某个项目的一个版本，进行一定次数的带资源的仿真或不带资源的仿真。

仿真结果模块：展示某个版本的仿真结果，以图表的方式展现如关键路径、平均工期、任务关键路径概率、总工期区间分布、进度风险、成本风险、进度成本联合风险等信息。用户可以通过浏览这些图表形式的仿真结果，直观地了解系统对于项目的风险评估信息，方便地做出最有利的决策。

资源管理模块：管理和显示资源的相关信息，用户可以创建、修改、删除某个资源。也可以设置资源的相关属性（名称、数量、是非为消耗性资源等）。

2 大数据多约束进度风险评估算法

本算法的核心类似银行家算法，运用到了拓扑排序和队列的相关知识，其思路是：枚举出所有可能的全拓扑资源分配序列（按优先级剔除部分），然后对其逐一进行模拟比较，算出最优分配序列。在分配资源和计算节点工期的过程中，按照银行家算法的思想，节点在申请资源的时候直接申明所需的最大资源，而且项目尽量满足节点的申明，除非超过拥有资源的最大数量。这样使得至少有一个节点是出于就绪状态的，避免死锁。

具体步骤：

A.输入项目基本信息和结构（输入项目XML）。

B.输入项目资源信息

C.输入项目每个节点的统计学属性、优先级关系和资源需求。

D.按照优先级计算项目节点的全拓扑排序资源分配序列。

E.按顺序选择一个资源分配序列进行模拟。

F.将所有人度为零的节点加入等待队列。

G.按顺序给等待队列节点分配资源，如果节点资源满足则把它改为加入就绪队列并将其所有后继节点人

度减一。

H.如果就绪队列不为空，则计算节点工期，按最小工期的节点推进项目。否则说明没有就绪节点，本资

源分配序列无法完成，返回E。

I.计算在等待队列的节点的等待资源时间。

J.计算完成节点的成本。

K.回收完成节点的资源，将其剔除就绪队列。

L.如果所有节点都已经完成则本资源分配序列结束，计算总工期。否则返回F。

M.如果所有资源分配序列都已经模拟过则算法结束，否则返回E。

N.输出任务等待的时间和等待的资源。

0.输出项目总工期和总成本。

算法流程图如图2所示。

设Sequence_List为资源分配序列数组，Sequence为资源分配序列，Wait List为等待队列，Ready_List为就绪队列，Task_List为节点列表。算法的伪代码可以表示为：

Foreach Sequence in Sequence_List

Foreach task in Task_ List

If （task.InDegree=0）then

Wait_List.Add（task） For i=l to Sequence.length do

Forj=l to Wait_List.count do

If（Wait_List.count[j].id！=Sequence[i]）

Continue

If（allocateResource（Wait_List.count[j]）=OK）

Ready_List.Add（task）

For k=l to task.succeed.lengh do

task.succeed[k]-

Wait_List.Remove（task）

If（Ready_List！=null）

minValue←Findmin（Ready_List）

Duration+=minValue；

Foreach task in Wait_List

Task.waittime+=minValue

For i=l to Ready_List.count do

If（Ready_List[i].Value<=minValue）

Mo ney+= getMo ney（Ready_List [i]）

recycleRe source （Ready_List[i]）

Ready_List[i].Remove（task）

Else

Ready_List[i].Value-=minValue

Else

Finish（）

本系统的资源约束仿真算法还运用到了关键路径算法，它为资源约束仿真算法的子过程。其算法步骤如下：

A. 拓扑排序，将所有人度为零的点压人堆栈

B. 计算栈顶节点最早开始工期Ve并将其所有后继节点人度

减一

C. 弹出堆栈。

D. 如果堆栈不为空则返回B。

E. 如果还有节点未完成则返回A

F. 逆拓扑排序，将所有出度为零的点压人堆栈

G. 计算栈顶节点最迟开始工期Vl并将其所有前驱节点出度减

H 如果Vl=Ve，将节点标记为关键路径上的节点。

I. 弹出堆栈。

J. 如果堆栈不为空则返回G。

K. 如果还有节点未完成则返回F

L 算法结束

算法的流程图如图3所示。

3 系统仿真及验证

蒙式仿真（Monte Carlo）方法是通过大量的计算机模拟来检验系统的动态特性并归纳出统计结果的一种随机分析方法，也称为统计模拟法或随机采样技术。它包括伪随机数的产生，蒙式仿真设计以及结果解释等内容，其作用在于用数学方法模拟真实物理环境，并验证系统的可靠性与可行性。它不仅适用于处理随机型问题，如存储系统、排队系统、质量检验问题、社会救急系统问题、生态竞争问题和传染病蔓延问题等；也可处理确定型问题，如计算多重积分、解积分方程及微分方程、解整数规划（特别是非线形整数规划）等。

蒙式仿真解决问题的基本思想是：首先建立与描述该问题相似的概率模型，然后对模型进行随机模拟或统计抽样，在利用所得到的结果求出特征的统计估计值作为原问题的近似解，并对解的精度做出某些估计。蒙式仿真方法的主要理论依据是大数定理，其主要手段为随机变量的抽样分析。

本系统运用了蒙式仿真的基本思想，也就是说按照一定的数学分布用多次模拟取随机数的办法去估计实际的值，模拟的次数越多则越贴合实际。由统计结果可以很容易地获得项目进度和成本的区间分布（进度包括了工期和等待资源的时间，成本包括了直接成本和间接成本），从而知道项目进度和成本大于某个阈值的概率是多少，也就是发生风险的概率是多少。如进度风险图4，成本风险图5，进度成本联合风险图6。

进度风险的统计思路：假设仿真次数为N，N次仿真结果中最大工期为Dmax，最小工期为Dmin。则依次取基准点Sn=（Dmax-Dmin）/lO*n+Dmin，即将区间十等分。后统计工期大于基准点Sn的结果数量Nn则进度风险概率Pn=Nn/N。（n=l，2，3…10）

成本风险的统计思路：同理，假设仿真次数为N，N次仿真结果中最大成本为Cmax，最小成本为Cmin。则依次取基准点Sn=（Cmax-Cmin）/lO*n+Cmin，即将区间十等分。后统计成本大于基准点Sn的结果数量Nn则成本风险概率Pn=Nn/N。（n=l，2，3…10）

进度成本联合风险是将进度风险和成本风险两个二维图统计结果结合，进而生成的三维散点图统计结果。散点的坐标可以表示为（Sx，Sy，P）。Sx对应工期X轴上的某个点，Sy对应成本Y轴上的某个点，P为风险概率。则散点所表示的意义是工期大于Sx，成本大于Sy的联合风险概率为P。

4 结论

本文对项目潜在的风险进行评估，让项目的管理者对项目有一个长远的认识，防范风险于未然。本文应用资源多约束下项目进度调度（resource-constrained project scheduling problem，RCPSP）问题模型，对进度风险评估系统进行了需求分析和模块划分，设计了系统的框架层次、数据库、资源多约束下的蒙式仿真算法，给出了依据仿真结果计算进度风险和成本风险的统计思路。

随便看

科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。