Petri网结合Dijkstra算法的并行测试任务调度方法研究  

Research on the parallel test task scheduling method with Petri nets and Dijkstra algorithm

作　　者：周强[1] 司丰炜 修言彬 

机构地区：[1]北京航空航天大学自动化科学与电气工程学院,北京100191

出　　处：《电子测量与仪器学报》2015年第6期920-927,共8页Journal of Electronic Measurement and Instrumentation

摘　　要：针对测试系统中的并行任务调度方法复杂且难以优化的问题,提出并实现了一种利用Petri网并结合Dijkstra算法的并行测试任务调度方法,从而减少了搜索算法的复杂度。该方法通过对Petri网可达数分析工具的充分利用,省去了传统方法在得到任务调度结果过程中的一些步骤。首先建立测试系统的Petri网模型并生成其可达树;然后对可达树模型进行加工和改进,添加状态节点间的联接关系;进而在加工、改进后的可达树模型基础上应用Dijkstra算法得到并行测试任务最佳的任务调度策略。针对一个工程实例应用任务调度方法进行了仿真实验与分析,仿真实验结果证明了该方法的有效性和正确性。Aiming at the complexity of the parallel task scheduling method in test system, a parallel test task sched- uling method is proposed and implemented using Petri network and Dijkstra algorithm, accordingly the complexity of the computation is reduced accordingly. Through fully utilizing the reachability trees of Petri nets, some necessary steps in traditional arithmetic can be skipped. Firstly, the method establishes Petri nets model of the test system and generates its reachability tree. Then the reachability tree is processed and improved, and the connection state between nodes is added. Further the best parallel test task scheduling strategy is got by the application of Dijkstra algorithm based on the processing and improved reachability tree model. The experiment and analysis are performed for an example of application engineering task scheduling method, and the simulation result demonstrates the effec- tiveness and correctness of the method.

关 键 词：并行测试 PETRI网 可达树 DIJKSTRA算法 

分 类 号：TP206[自动化与计算机技术—检测技术与自动化装置]