一种基于分枝定界法的串行测试任务调度算法

 目前的自动测试系统中，对于串行任务的测试一般是以整个任务为粒度，这就导致两个任务可能需要重复设置相同的状态或重复测试相同的内容，延长了测试时间，降低了测试效率。针对这个问题，建立了基于图论的串行测试任务时序模型，用“图”来描述串行任务的测试时间与测试顺序的关系，将实际工程问题转化为图论中的数学问题。在任务时序模型的基础上，提出了一个串行测试任务调度算法。对于多个需要串行测试的任务，利用该算法可以得到测试时间最短的串行任务序列。该算法是借助整数规划问题中分枝定界法的思想实现的，通过相关理论和具体实例对算法的正确性和复杂性进行了分析。在实际系统中对该算法进行了实验验证，结果表明给定任务的测试效率提高了40%以上。

A Kind of Scheduling Algorithm for Serial Test Tasks Based on Branch and Bound Algorithm

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%.