A multi-objective evolutionary algorithm based on Pareto prediction for automatic test task scheduling problems

The test task scheduling problem (TTSP) is a combinatorial optimization problem still under investigation. A multi-objective evolutionary algorithm based on Pareto prediction (PP-MOEA) is proposed fully considering the characteristics of TTSP. In a multi-objective TTSP, multiple solutions in the decision space correspond to a point in the objective space and the number of true Pareto front in the objective space is relatively small. Moreover, there are less solutions distributing in either high or low objective values while most solutions distribute in average. Based on these characteristics, a pure elitism strategy and a novel scale-down non-dominated sorting (SDNS) method are combined to improve the efficiency and convergence of the algorithm. Additionally, an extended encoding range approach and a Pareto prediction strategy are proposed to help exploring new solutions and increase the diversity of population. The Pareto prediction strategy is implemented by following the historical evolutionary information of the current Pareto set and then predicting the next generation of several individuals. The makespan (maximal test completion time) and the mean workload of the instruments are considered in this research. Based on the general framework of MOEAs, the proposed algorithm is more effective and efficient in tackling multi-objective TTSPs. PP-MOEA has the better performance of convergence and diversity compared with other algorithms based on the statistical analysis of experiments results.