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

第 43卷 第 11期 计 算 机 科 学 Vo1．43No．11 2016年 l1月 Computer Science NOV2016 基于带标记的并发可达标识图的关键路径的求解方法 韩耀军 (上海外国语大学国际工商管理学院信息管理系 上海 200083) 摘 要 将A0E网转换成有色时延Petri网模型，在模型转换过程中同时计算出各位置所对应的事件的最早开始时 间，给出了模拟 A0E网的有色时延Petri网模型的带标记的并发可达标识 图的构建算法；利用并发可达标识图中的 标记序列直接得到关键路径并计算出完成所有活动所需的最短时间。实例与仿真实验结果表明，当AOE网中平均 存在 3个以上的并发活动时，所提方法执行效率优于传统的求解关键路径的算法，并发活动越 多，所提算法效率越高。 关键词 有色时延Petri网，并发可达标识图，AOE网，关键路径 中图法分类号 TP301 文献标识码 A DOI 10．11896／j．issn．1002-137X．2016．11．023 M ethodforFindingCriticalPathsBasedonConcurrentReachableM arkingGraphwithTags HANYao-jun (DepartmentofInformationManagement，SchoolofBusinessandManagement，ShanghaiInternationalStudiesUniversity，Shanghai200083，China) Abstract ThecolortimedPetrinetmodelwasgottenbytransformingAOE network inthispaper．Theearliestevent starttimewascalculatedwhileconstructingPetrinetmode1．Thealgorithm ofconstructingconcurrentreachablemar- kinggraphwithtagsforcolortimedPetrinetmodelingAOEnetworkwasgiven．Thecriticalpathsweregottenandthe shortesttimeofcompletingallactivitieswascalculatedfrom tagsofconcurrentreachablemarkinggraph．Theexample andsimulationshow thattheexecutionefficiencyofthealgorithm isbetterthantraditionalalgorithm forfindingcritical pathswhentherearemorethanthreeconcurrentactivitiesinAOEnetwork．Themoretheconcurrentactivitiesare，the highertheefficiencyis． Keywords ColortimedPetrinet，Co ncurrentreachablemarkinggraph，AOE network，Criticalpaths 延Petri网计算出各库所对应工序的最早和最晚开工时间，进 1 引言 而求得关键工序 ，并利用时延 Petri网的可达标识图求解出合 A0E网(ActivityOnEdge，边表示活动的网)是一个带 理的工序。由于这种方法需要计算各工序的最早和最晚开工 权的有向无环图，其中顶点表示事件 (Event)，弧表示活动，权 时间，因此在执行效率方面与传统的关键路径的求解算法相 表示活动