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

将AOE网转换成有色时延Petri网模型,在模型转换过程中同时计算出各位置所对应的事件的最早开始时间,给出了模拟AOE网的有色时延Petri网模型的带标记的并发可达标识图的构建算法;利用并发可达标识图中的标记序列直接得到关键路径并计算出完成所有活动所需的最短时间。实例与仿真实验结果表明,当AOE网中平均存在3个以上的并发活动时,所提方法执行效率优于传统的求解关键路径的算法,并发活动越多,所提算法效率越高。

主从任务调度的T-时间Petri网

任务调度是一个NP-hard问题,并且是并行与分布式计算必不可少的组成部分.本文首先提出了适合描述异构环境下独立、等尺寸的大规模任务调度问题的T-时间Petri网模型,然后给出了刻画该模型运行的并发可达图的构造算法,最后,在并发可达图中得到了最优调度策略,该策略实现了稳定状态的最优调度,有效地缩短了调度的初始化及清除阶段的时间.