Abstract: This paper presents a graph tabu approach to deal with problems existing in present parallel test task scheduling approaches, such as long computation time, low probability optimization rate, premature convergence to local optima, etc. The approach in this paper starts with strong constraints among parallel test tasks, then uses the graph theory to establish a diagram of test tasks, and finally realizes multi-objective optimization of parallel test task scheduling by combining with a tabu search algorithm. This approach makes a separation between strong constraint test task scheduling and no constraint test resource scheduling, which improves the optimization speed. The experimental results show that the approach is feasible. Compared with the existing approaches, the proposed approach realizes a 96% reduction of computing time, 36.5% increment of the optimization rate, and better convergence.

Key words: graph theory, tabu search, parallel test, task scheduling, strong constraint