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

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

将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.