A chaotic non-dominated sorting genetic algorithm for the multi-objective automatic test task scheduling problem

Solving a task scheduling problem is a key challenge for automatic test technology to improve throughput, reduce test time, and operate the necessary instruments at their maximum capacity. Therefore, this paper attempts to solve the automatic test task scheduling problem (TTSP) with the objectives of minimizing the maximal test completion time (makespan) and the mean workload of the instruments. In this paper, the formal formulation and the constraints of the TTSP are established to describe this problem. Then, a new encoding method called the integrated encoding scheme (IES) is proposed. This encoding scheme is able to transform a combinatorial optimization problem into a continuous optimization problem, thus improving the encoding efficiency and reducing the complexity of the genetic manipulations. More importantly, because the TTSP has many local optima, a chaotic non-dominated sorting genetic algorithm (CNSGA) is presented to avoid becoming trapped in local optima and to obtain high quality solutions. This approach introduces a chaotic initial population, a crossover operator, and a mutation operator into the non-dominated sorting genetic algorithm II (NSGA-II) to enhance the local searching ability. Both the logistic map and the cat map are used to design the chaotic operators, and their performances are compared. To identify a good approach for hybridizing NSGA-II and chaos, and indicate the effectiveness of IES, several experiments are performed based on the following: (1) a small-scale TTSP and a large-scale TTSP in real-world applications and (2) a TTSP used in other research. Computational simulations and comparisons show that CNSGA improves the local searching ability and is suitable for solving the TTSP. (C) 2012 Elsevier B.V. All rights reserved.