Non-integrated algorithm based on EDA and Tabu Search for test task scheduling problem

The optimization of test task scheduling problem (TTSP) is an important issue in automatic test system (ATS). TTSP is a complex combination optimization problem and includes two sub-problems. They are test task sequencing and test scheme combination. According to the characteristic of TTSP, a non-integrated algorithm based on estimation of distribution algorithm and Tabu Search (EDA-TS) is proposed in this paper. EDA focuses on solving test task sequencing in global searching, and TS emphasizes on solving test scheme combination in local searching. In addition, we give a mathematical model for TTSP. We prove that TTSP is an NP-hard by using traveling salesman problem (TSP) based on the mathematical model. The statistical results of single objective TTSP suggest that our approach has a stronger searching ability and good convergence compared with other three popular algorithms. The experiments of the multi-objectives TTSP also illustrate that EDA-TS has a strong searching ability and can maintain a diversity of solutions.