基于带标记的并发可达标识图的关键路径的求解方法  

Method for Finding Critical Paths Based on Concurrent Reachable Marking Graph with Tags

作　　者：韩耀军[1] 

机构地区：[1]上海外国语大学国际工商管理学院信息管理系,上海200083

出　　处：《计算机科学》2016年第11期121-125,141,共6页Computer Science

基　　金：上海市哲学社会科学规划一般课题(2010BTQ001);上海外国语大学校级重大科研项目(2013114ZD004);上海外国语大学国际工商管理学院高层次培育项目资助

摘　　要：将AOE网转换成有色时延Petri网模型,在模型转换过程中同时计算出各位置所对应的事件的最早开始时间,给出了模拟AOE网的有色时延Petri网模型的带标记的并发可达标识图的构建算法;利用并发可达标识图中的标记序列直接得到关键路径并计算出完成所有活动所需的最短时间。实例与仿真实验结果表明,当AOE网中平均存在3个以上的并发活动时,所提方法执行效率优于传统的求解关键路径的算法,并发活动越多,所提算法效率越高。The color timed Petri net model was gotten by transforming AOE network in this paper.The earliest event start time was calculated while constructing Petri net model.The algorithm of constructing concurrent reachable marking graph with tags for color timed Petri net modeling AOE network was given.The critical paths were gotten and the shortest time of completing all activities was calculated from tags of concurrent reachable marking graph.The example and simulation show that the execution efficiency of the algorithm is better than traditional algorithm for finding critical paths when there are more than three concurrent activities in AOE network.The more the concurrent activities are,the higher the efficiency is.

关 键 词：有色时延Petri网 并发可达标识图 AOE网 关键路径 

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