基于图染色理论和遗传蜂群算法的并行测试任务调度

Parallel test task scheduling based on graph coloring theory and genetic-bee colony algorithm

针对并行测试中任务优化调度这一关键性问题,提出了一种图染色理论和遗传蜂群算法相结合的任务调度优化算法。首先,建立了基于图染色理论的并行测试任务关系模型,用图来描述测试任务占用仪器资源的情况;然后,在测试任务关系模型的基础上,将遗传算法特有的交叉、变异操作与人工蜂群(ABC)算法相结合搜索最优解,能够有效避免算法早熟并且加速算法收敛;最终得到并行度最大的任务分组方案。经仿真验证,所提方法能有效地实现并行测试,提高自动测试系统的测试效率。

For the question of parallel test task scheduling, an innovative solution based on graph coloring theory and genetic-bee colony algorithm was proposed. Firstly, a relation model of test tasks was established based on graph coloring theory, in which the occupation of device resource by test task could be represented by graph. Based on this relation model of test task, the optimum solution was searched via combining the artificial bee colony algorithm and the crossover operation and mutation operation which are unique in genetic algorithm to avoid the prematurity of the algorithm as well as accelerate convergence. Eventually, a grouping scheme was generated with maximized parallelism degree. Verified by the simulation, the proposed method can effectively realize the parallel test, improve the test efficiency of automatic test system.