基于模拟退火禁忌遗传算法的并行测试任务调度

Parallel Test Task Scheduling Based on Simulated Annealing Tabu Search Genetic Algorithm

为了解决并行自动测试系统中并行测试任务调度复杂、优化困难的问题,提出了一种把遗传算法、禁忌搜索算法和模拟退火算法结合到一起的新型静态并行测试任务调度方法,在遗传算法中引入模拟退火算法和禁忌搜索算法的核心思想,避免了遗传算法早熟收敛的问题,从而得到总测试时间最短,具有最大并行率的任务调度序列.这种新型调度算法具有较低的运算复杂度,可在较短时间内得到大量高效的并行测试序列,并且可以有效避免局部最优解,并逐渐收敛到全局最优解.实例仿真结果证明了该算法的有效性和优越性.

To solve the complex problem of parallel test task scheduling in the parallel automatic test system,a new static test task scheduling algorithm based on Stochastic Genetic Algorithm,Simulated Annealing Algorithm and Tabu Search Algorithm is proposed.The main ideas of Simulated Annealing Algorithm and Tabu Search Algorithm are applied to Stochastic Genetic Algorithm to avoid premature convergence problem of Genetic Algorithm,so that test task sequences with shortest total test time and highest parallel efficiency can be obtained.This new test task scheduling algorithm has low algorithm complexity,and it can get many efficient parallel test sequences in short time.It can also avoid local optimal solutions and gradually convergent to the feasible globally optimal solution.The experimental result shows that the new test task scheduling algorithm is feasible and ascendant.