孔祥星 合作者：张玄、侯振挺 中 南 大 学 2012年5月27日 2012年“随机图与复杂网络” 学术研讨会 马尔可夫骨架过程在PERT网络中的应用 孔祥星 合作者：张玄、侯振挺 中 南 大 学 2012年5月27日

统筹方法 想泡壶茶喝。当时的情况是：没有开水，开水壶要洗，茶壶茶杯要洗，茶叶没有拿，怎么办？ b s t c d 1 2 3 4 5 活动1（洗茶壶）需要1分钟，活动2（烧开水）需要15分钟，活动3（洗茶壶）需要1分钟，活动4（洗茶杯）需要1分钟，活动5（拿茶叶）需要2分钟。

PERT网络 在华罗庚先生所提的统筹方法中，项目中每个活动的持续时间是固定的，只要安排好工序就可以求出项目的完工时间。后来有人假设项目中每个活动的持续时间是相互独立服从负指数分布的随机变量，可用马氏链来研究项目的完工时间分布。我们进一步把每个活动的持续时间推广为相互独立服从一般分布的随机变量，把每个活动已实施的时间作为补充变量，从而构建一个带有吸收态的马尔可夫骨架过程，通过其向后方程得到了PERT网络完工时间分布的解析表达式。

PERT网络 用 表示一个具有一个源点s和一个汇点t 的有向非循环网络，其中， 表示节点 （事件）集， 表示弧（活动）的集 的有向非循环网络，其中， 表示节点 （事件）集， 表示弧（活动）的集 合，对于任意个一个活动 ，其持续时间是服 从一般分布的随机变量。令 表示弧 的起点， 表示弧 的终点，一条 有向路径是一个弧 序列 且弧序列满足如下的条件 ， 且 。

PERT网络 定义1 令 和 分别表示以节点 为起点和终点 的弧的全体，分别可以表示如下： 定义2 设 ， ，则 割集定 义为 定义1 令 和 分别表示以节点 为起点和终点 的弧的全体，分别可以表示如下： 定义2 设 ， ，则 割集定 义为 如果一个 割集 是空集，则称 为一致 有向割集。

PERT网络 定义3 在项目的实施过程中，在时刻每个活动都 会处于活动、休眠的或空闲的三种状态之一： 称该活动处于活动的状态。 （2）休眠：如果某个活动 已经完工，但是 中的活动没有都完工，此时 中的活动 不能开始施工，称 处于休眠的状态。 （3）空闲：如果某个活动既不是活动的也不 是不活动的，则称为空闲的。

PERT网络 设 是PERT网络 的一条路径，路 径 的完工时间很明显不一定等于各个活动 的完工时间之和。为了计算路径 的完工 径 的完工时间很明显不一定等于各个活动 的完工时间之和。为了计算路径 的完工 时间分布，可采用如下的方法，令 从而包含 所有活动的子图 的完工时间等于路径 的完工时间。

PERT网络 如图（a）所示，设路径 ，则 ，从而 。则子图 如图（b）所示，路径 的完工时间与子图 的 完工时间相等。

马氏骨架过程 如上令 和 表示所有UDC中活动的和休眠的 在图(b)中所有的UDC为(1,2), (2,3), (1,4), (3,4), *表示该活动处于休眠状态。 表1 如上令 和 表示所有UDC中活动的和休眠的 活动。对 ，令 表示活动已实施的时间， 令 表示活动 的持续时间分布。则剩余

马氏骨架过程 时间的分布 可表示为 以活动的已实施的时间 作为补充变量则表1 的状态变为 表2

马氏骨架过程 令 则 是一个状态空间为 的马尔科夫骨架过程。 令 表示 的不连续时间点（在时刻 有一个活动完工），则 是马氏骨架过 则 是一个状态空间为 的马尔科夫骨架过程。 令 表示 的不连续时间点（在时刻 有一个活动完工），则 是马氏骨架过 程 的骨架时序列。 为了表述的方便，把表2中10个状态分别用 1,2，……，10来表示，马尔科夫骨架过程 在 完成状态1后转移到状态2或4或6，完成某项活动

马氏骨架过程 后继续向后转移，最终到达状态10，从而整个项 目完成。马尔科夫骨架过程的状态转移示意图如 下所示：

马氏骨架过程 令 表示PERT网络的完工时间，则 可以通过马尔科夫骨架过程的向后方程计算项目 工期 的分布。 工期 的分布。 令 表示从状态9转移到状态10的完工时间分 布，其中活动5已实施的时间长度为 ，则

马氏骨架过程 令 表示从状态8转移到状态10的完工时间分 布，其中活动3已实施的时间长度为 ，则

马氏骨架过程 令 表示从状态1转移到状态10的完工时间分布，其 中活动1和2已实施的时间长度分别为 和 则

马氏骨架过程 路径 的完工时间等于子图 的完工时间， 即马尔科夫骨架过程从状态1转移到状态10的时间。

例子 为了说明本章所得解析结果的有效性，给出一个 具体的例子，设活动5的持续时间服从参数 的 -分布，则其密度函数和剩余时间分布为 的 -分布，则其密度函数和剩余时间分布为 设活动1,2,3,4,6的持续时间分布分别服从参数为 1,2,3,4,6的负指数分布。

例子 路径 的完工时间等于子图 的完工时 间，即马氏骨架过程 从初始状态1到达吸收态 10的时间。完工时间的分布、期望与方差如下：

参考文献 [1] Kulkarni V., Adlakha V. Markov and Markov-Regenerative PERT networks. Operations Research, 1986, 34:769~781 [2] Azaron A., Katagiri H., Sakawa M., et al. Multi-objective resource allocation problem in PERT networks. European Journal of Operational Research, 2006, 172:838~854 [3] Azaron A., Tavakkoli-Moghaddam R.. A multi-objective resource allocation problem in dynamic PERT networks. Applied Mathematics and Computation, 2006, 181:163~174 [4] Azaron A, Katagiri H, Kato K, etal. Longest path analysis in network of queues. European Journal of Operational Research, 2006, 174:132~149 [5] Kong X. X., Zhang X., and Hou Z. T., Markov skeleton process in PERT networks. Acta Mathematica Scientia, 2010, 30B(5): 1440~1448

2012年“随机图与复杂网络” 学术研讨会 谢谢各位专家老师！