基于时延Petri网的肯定型工程关键工序的求解.pdfVIP

2008年第7期 福 建 电 脑 157 基于时延Petri网的肯定型工程关键工序的求解 郑怡文 (浙江艺术职业学院 浙江杭州 310053) 【摘 要】：针对工程施工安排问题中关键工序的求解，传统的通过时延Petri网确定肯定型工程关键工序的算法既要 正向计算每个工序的最早开工时间。也要逆向计算每个工序的最晚开工时间，然后进行比较，计算量比较大。本文对传统的 通过时延P 网确定肯定型工程~：~t-r-序的算法进行改进．只需正向计算各工序的最早开工时间和进行简单的比较，对于 比较大型、工序比较繁多的工程项目。计算变得更加简单容易。 【关键词】：肯定型工程关键工序时延Petri网 l、引言 r0， 若si--sO 随着国民经济和技术的飞速发展．工程的数量和规模都增 E(si) 长的很快。因此。工程的施工安排问题在工程技术中显得越来越 [max{~sj)+w(sj)l sj e-(。so} 其他 突出 解决此类问题的方法大致有统筹方法和含时间因素的 Pe 网方法。由于Petri网作为图形化建模工具。具有直观、易懂 和易用的优点。对描述和分析此类问题有其独到之处，所以对工 r TE， 若s_sc 程建立Pe 网模型可以使对此类问题的求解变得更加容易和 si) 直观。一项工程可以划分为若干道工序，根据各工序的工期是不 ~．min{LOj)+W(6)l sj∈(si．)．卜W(si)，其他 是一个确定值．可把该工程划分为肯定型工程和非肯定型工程。 通过以上公式计算每道工序的最早开工时间和最晚开工时 对于肯定型工程适于时延Petri网．而后者则要用时间Petri网。 间E(si)， i)(i=o，l…n)。满足E(si)= i)的工序即为主工序，把 本文只对肯定型工程关键工序传统的求解算法进行改进。改进 整个工程中的所有主工序都找到了．也就找到了该工程的关键 后的算法．使得基于时延Petri网肯定型工程关键工序的求解变 工序。 得更加简单容易 3．2对传统基于时延Pe 网模型工程施工安排问题中关键工序 2、基本概念 的求解算法进行改进 Pe 网是对离散并行系统的数学表示。适合于描述异步的、 以上可以看出传统基于时延Pe 网模型工程施工安排问 并发的计算机系统模型。Pe 网既有严格的数学表述方式。也有 题中关键工序的求解从sO开始逐个向前推进求出各工序最早 直观的图形表达方式．既有丰富的系统描述手段和系统行为分 可能开工时间E(si)。一直到求出E(se)。然后从se开始，逐个向 析技术，又为计算机科学提供坚实的概念基础。在这里我们仅给 后追溯求出每个工序的最晚必须开工时间L(8i)。最后找出E 出几个与本文密切相关的概念．其它 Petri网术语可参见文献 fsi)= i)的工序即为关键工序。所以这样比较复杂，尤其对于比 【1-2】 较大型的工程项目．工序比较繁多的情况。因此。应该尽量减少 定义l满足下列条件的三元组N=(S，T；F)称为一个网 计算来保证正确性。现仍假设E(si)表示工序si的最早开工时 l1 ST≠ 间，即 rO， ~si=sO 2)S r_