关键词: 串行测试任务调度算法, 分枝定界法, 图论, 自动测试, 建模

Abstract:

In automatic test system the test approach is usually based on the whole task for serial test tasks at present. Sometimes the same state has to be set and the same process has to be run repeatedly for two different tasks. So the test efficiency is very low. For this problem, a time sequence model of serial test tasks based on graph theory is established. The relation of test time and test sequence is described by “graph”, so the project problem is transformed into mathematics problem. Based on the time sequence model, a scheduling algorithm named STTS for serial test tasks is proposed. For many serial test tasks, the task sequence that has the shortest test time can be found by using the algorithm. The algorithm is achieved with branch and bound algorithm and its correctness and complexity is analyzed with correlative theory and practical example. The algorithm is validated by experiment in actual system and the results show the test efficiency of given tasks is enhanced more than 40%.

Key words: serial , test , tasks , scheduling , algorithm,  , branch , and , bound , algorithm ,  , graph , theory,  , automatic , testing,  , modeling