基于CPN的求解关键路径的新方法  

A New Method for Finding the Critical Paths Based on Colored Petri Nets

作　　者：郑文艳[1] 

机构地区：[1]德州学院计算机系,德州253023

出　　处：《计算机系统应用》2013年第8期9-13,53,共6页Computer Systems & Applications

摘　　要：在证明转换规则正确性的基础上,首先利用转换规则对AOE网进行转换,然后从两个方面对转换后的CPN(Colored Petri Nets)模型不合理的地方进行合理性的修改.再利用编写的函数求出从源点到汇点的所有的可达路径,在获得所有可达路径的同时也获取了所有可达路径所花费的时间,那么时间最大的就是关键路径.该方法不仅简便直观,而且能够在保证正确性合理性的前提下提高执行效率,减小时间复杂度.Under the circumstances of the correctness of conversion rules has already been proved, The first things is conversion the AOE system using transformation rules, and then to do reasonable modifications about the CPN model＇s unreasonable aspects from two ways. Using these function that acquired by ourselves to get all the reachable paths from the source to sink. In the meantime, we get all the time that all reachable paths have consumed, and the biggest time is the critical path. The method is not only simple and intuitive, but also can improving the execution efficiency under the premise of correctness and rationality, and can reduce the time complexity.

关 键 词：关键路径 颜色PETRI网 消息序列图 时间复杂度 状态空间 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]