基于图染色理论的并行测试任务调度算法  

Algorithms of tasks scheduling in parallel test based on graph coloring theory

作　　者：李昕[1] 沈士团[1] 路辉[1] 

机构地区：[1]北京航空航天大学电子信息工程学院,北京100083

出　　处：《北京航空航天大学学报》2007年第9期1068-1071,共4页Journal of Beijing University of Aeronautics and Astronautics

摘　　要：目前的自动测试系统大多数采用串行测试的工作方式,测试效率很低.针对这个问题,建立了基于图论的测试任务关系模型,用"图"来描述测试任务占用仪器资源的情况,将测试任务调度的工程问题转化为图论中的数学问题.在测试任务关系模型的基础上,提出了两个任务调度算法:CTG算法和CTG-T算法.对于多个测试任务,利用这两个算法可以得到并行度最大或者测试时间最短的任务分组方案,能有效地实现并行测试.这两个算法是基于图的染色理论得到的,对其正确性进行了理论分析和实例仿真.两个算法已经在实际系统中得到了实验验证,结果表明能够大大提高自动测试系统的测试效率.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.

关 键 词：自动测试 图论 模型 调度 算法 

分 类 号：TP206.1[自动化与计算机技术—检测技术与自动化装置] TP301.6[自动化与计算机技术—控制科学与工程]