Algorithms of tasks scheduling in parallel test based on graph coloring theory
-
摘要: 目前的自动测试系统大多数采用串行测试的工作方式,测试效率很低.针对这个问题,建立了基于图论的测试任务关系模型,用"图"来描述测试任务占用仪器资源的情况,将测试任务调度的工程问题转化为图论中的数学问题.在测试任务关系模型的基础上,提出了两个任务调度算法:CTG算法和CTG-T算法.对于多个测试任务,利用这两个算法可以得到并行度最大或者测试时间最短的任务分组方案,能有效地实现并行测试.这两个算法是基于图的染色理论得到的,对其正确性进行了理论分析和实例仿真.两个算法已经在实际系统中得到了实验验证,结果表明能够大大提高自动测试系统的测试效率.Abstract: The test method of most automatic test systems is serial at present, so test efficiency is very low. For this problem, a relation model of test tasks was established based on graph theory. The relation between test tasks and instruments was described by "graph", so the project problem of test tasks scheduling was transformed into mathematics problem about graph theory. Based on the relation model, two algorithms named CTG and CTG-T about tasks scheduling were proposed. By using these algorithms the tasks grouping scheme that has the maximal parallel degree or the shortest test time was found, and parallel test was achieved effectively. The two algorithms were based on graph coloring theory and their correctness and feasibility were approved by both theory and emulator. These algorithms were validated by experiment in actual system and the result shows that test efficiency of system is enhanced greatly.
-
Key words:
- automatic testing /
- graph theory /
- models /
- scheduling /
- algorithms
-
[1] Ross W A. The impact of next generation test technology on aviation maintenance AUTOTESTCON 2003 IEEE Systems Readiness Technology Conference Proceedings. Anaheim:IEEE Instrumentation and Measurement Society,2003:2-9 [2] 肖明清,朱小平,夏锐.并行测试技术综述[J].空军工程大学学报(自然科学版),2005,6(3):22-25 Xiao Mingqing, Zhu Xiaoping, Xia Rui. Summary of parallel test technology[J]. Journal of Air Force Engineering University (Natural Science Edition), 2005, 6(3):22-25(in Chinese) [3] Hou E S H, Ansali N, Ren H. A genetic algorithm for multi-processor scheduling [J]. IEEE Transaction on Parallel and Distributed Systems, 1994,5:113-120 [4] 胡瑜.基于有色Petri网理论的并行自动测试系统建模研究 .成都:电子科技大学自动化学院,2003 Hu Yu. Colored Petri net based modeling of parallel automatic test systems . Chengdu:School of Automation, University of Electronic Science and Technology of China, 2003(in Chinese) [5] 徐俊明.图论及其应用[M].第2版.合肥:中国科学技术大学出版社,2004:171-238 Xu Junming. Graph theory and its application[M]. 2nd ed. Hefei:University of Science and Technology of China Press, 2004:171-238(in Chinese)
点击查看大图
计量
- 文章访问数: 3066
- HTML全文浏览量: 217
- PDF下载量: 1235
- 被引次数: 0