مرتب سازی بی نظمی، تحت سلطه ی الگوریتم ژنتیک برای تست کار مسئله برنامه ریزی چند هدفه اتوماتیک

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.

Automatic test technology offers much more efficiency, repeatability, and reliability than manual operations in the modern manufacturing processes and is widely used in many applications. For example, in mobile phone terminal manufacturing, automatic test technology is used to measure production performance; in spacecraft, missile, and other aerospace systems, it represents one of the important technologies for ensuring the safety of these systems. One key challenge in automatic test technology is the test task scheduling problem. This scheduling problem addresses allocating tasks to the available instruments to improve throughput, reduce test time, and optimize resource allocation [1]. Therefore, an effective and efficient dispatching scheme is important and highly valued. However, although there have been several research projects to date within this field with an important application value in modern manufacturing environments, a concrete optimized algorithm has not yet been fully elucidated [2]. These reasons motivated us to perform this study. Because of the similarities among many of the scheduling problems, the flexible job-shop scheduling problem (FJSP) is compared to the automatic test task scheduling problem (TTSP), and a brief description of our issue is provided. Both the FJSP and the TTSP must assign each operation or task to a machine or an instrument from a set of capable machines or instruments and then sequence the assigned operations or tasks on each machine or instrument [3]. However, the two problems contain some differences. First, in the FJSP, each operation can be performed on only one of the m machines at a time, whereas in the TTSP, a task can be tested on more than one instrument, which requires a much more complex allocation of the instruments to avoid resource conflicts. Second, in the FJSP, the operations for each job must be performed in a predetermined order, and the priority is linear. In other words, every operation has only one former operation and one latter operation. However, the precedence relationships in the TTSP resemble a network. In other words, one task could have one or more former or latter tasks, and thus, it is more difficult to obtain feasible solutions. As mentioned above, the TTSP is more difficult to solve than the FJSP. The FJSP is NP-hard [3], and many similar problems, such as TTSP, have this property. Thus, it is difficult or impossible to solve this type of problem with deterministic methods. Many meta-heuristics methods and evolutionary algorithms have been proposed. In this research, we present an algorithm, the chaotic non-dominated sorting genetic algorithm (CNSGA), which hybridizes chaotic sequences based on the logistic map and the cat map with the non-dominated sorting genetic algorithm II (NSGA-II). The NSGA-II method was presented by Deb in 2002 [4] and has been successfully used in solving shop scheduling problems [5], reactive power dispatch problems [6], and many other applications. This approach is effective and able to maintain a better spread of solutions. In addition, the TTSP has many local optima, and chaotic operators are used to avoid becoming trapped in the local optima. Chaos theory focuses on the behavior of dynamical systems that are highly sensitive to initial conditions. Chaotic sequences have some special characteristics, such as the ergodic property and the stochastic property [7]. Because of these properties, optimization algorithms based on chaos can escape from the local optima, depending on their chaotic motion [8]. Thus, some researchers used optimization algorithms combined with chaos to achieve better results. For example, Lü et al. [9] introduced a chaotic mutation into the GA to train an artificial neural network, and Guo et al. [10] used both chaos optimization of the initial population and excellent individual chaotic disturbance to escape from the local optima. Although approaches that combine evolutionary algorithms and chaos are applied in various fields, a few researchers have sought to solve the multi-objective optimization problems using chaotic operators. Thus, we contributed a substantial effort to find satisfactory approaches for combining multi-objective optimization algorithms with the chaos principles. In this paper, a chaotic initial population, a crossover operator, and a mutation operator are introduced into the NSGA-II to enhance the local searching ability. To determine the distinct performances of different chaotic maps, both the logistic map and the cat map are used as number generators in place of random number generators in the initial population, crossover operator, and mutation operator. Thus, there are six variants of CNSGA. Additionally, the chromosome-encoding scheme is an important aspect that should be carefully considered. Both the FJSP and the TTSP are a combination of machine/instrument assignment and operation/task-scheduling decisions [11]. Thus, a chromosome should include these two types of information. The FJSP has two main encoding schemes: the task sequencing list (TSL) (or the operations list coding (OLC)) [12] and the two-vector representation [11]. The TSL represents the schedule in a list of operations, and each operation holds one cell. Every cell contains the operation number, the job number, and the machine number. This encoding scheme is understandable, but it makes the corresponding genetic manipulations difficult to perform. The two-vector representation is composed of a chromosome with two parts: the machine assignment vector and the operation sequence vector. This encoding scheme can always represent a feasible operation sequence. However, it still contains some disadvantages. For example, it is not very efficient, and decoding is inconvenient. Moreover, the crossover operators and the mutation operators of these two vectors are usually different and should be considered separately; this constraint increases the complexity of the genetic manipulations. More importantly, the encoding scheme uses discrete encoding, and thus, algorithms such as PSO cannot use it directly because some bits of a particle position may appear as real values, whereas the discrete encoding requires integers. Two main approaches are applied to address this type of incompatibility. One approach is to revise the updated particles. For example, Xia and Wu [13] rounded off the real optimum value to its nearest integer number. The other approach is to design a new particle updating method to replace the traditional velocity-displacement model. Zhang et al. [14] enabled each particle to exchange information by performing a crossover operation, which did not generate real values. These two approaches require adjustments or special designs and are not always convenient. Similarly, chaotic technology cannot be easily applied to improve the performances of algorithms using discrete encodings because the chaotic variables are continuous variables. Thus, chaotic technology is suitable for the continuous searching space, and therefore, the limitations of discrete encoding have stunted the development of the continuous algorithms and chaotic technology in combinatorial optimization problems. Xia et al. [15] presented a matrix-encoding scheme for the TTSP. The column vectors of the matrix chromosome represent the instruments, and the row vectors express the tasks. For every instrument, if one task uses it, that task number is entered in the row vector of that instrument. This encoding scheme will generate unfeasible solutions during the genetic manipulations, and if a task can be tested on more than one set of instruments, it will become invalid. As mentioned above, the commonly used TSL (OLC), the two-vector representation, and the matrix-encoding are not always acceptable. The integrated encoding scheme (IES), inspired by random key (RK) encoding [16], is proposed to address deficiencies of certain encoding schemes. The IES approach improves the encoding efficiency by using only one chromosome to merge the information regarding both the instrument assignment and the task scheduling decisions. Additionally, the complexity of the genetic manipulations is reduced, and it is able to satisfy the resource constraints and solve the TTSP with multiple alternative test schemes. More importantly, IES transforms a combinatorial optimization problem into a continuous optimization problem, making the applications of algorithms more convenient without the consideration of whether the problem is combinatorial or continuous. This approach represents a “fast-track” between a combinatorial optimization problem and a continuous optimization algorithm, which makes the search algorithms such as PSO suitable for combinatorial problems and chaos technology applicable for enhancement of the algorithm. The remainder of this paper is organized as follows. Section 2 gives a summary of some proposed papers applied in scheduling problems as well as adopted algorithms. Section 3 briefly introduces certain concepts that are used for describing multi-objective optimization problems. The formulation, constraints, and optimized objectives of the problem under study are presented in Section 4. Then, in Section 5, the proposed CNSGA is described in detail for solving the TTSP, including the chaotic maps, the problem encoding scheme, and the implementation of the CNSGA. The experimental results and performance comparisons are presented and discussed in Section 6. Finally, Section 7 contains the conclusions and further research suggestions.

In this paper, a chaotic non-dominated sorting genetic algorithm is proposed for solving the multi-objective automatic test task scheduling problem. The two objectives are the minimization of the makespan and the minimization of the mean workload of the instruments. The problem description for the TTSP is given in Section 4. Afterwards, a novel integrated encoding scheme is proposed that can transform a combinatorial optimization problem into a continuous optimization problem. This encoding scheme integrates the information regarding both the processing sequence of the tasks and the occupancy of the instruments for every task into only one chromosome. Therefore, it leads to a reduction of the complexity of genetic manipulations and an improvement in the encoding efficiency. Furthermore, because the TTSP is a combinatorial optimization problem and has many local optima, the proposed algorithm CNSGA introduces the chaotic initial population, the chaotic crossover operator, and the chaotic mutation operator into NSGA-II, using both the logistic map and the cat map, to enrich the local search behavior. Because of the ergodicity and the pseudo-randomness of chaos, the local searching ability of CNSGA is better than that of the normal NSGA-II. This scenario has been confirmed by computational results obtained from two types of experiments. According to the different capabilities of the logistic and the cat chaotic operators, the CNSGA approach using the cat population initialization, the cat or logistic crossover operator, and the logistic mutation operator performs well and is very suitable for solving the TTSP. Future work includes study of the performances of additional chaotic maps and discovery of the reasons for their special properties. In addition, other multi-objective algorithms can be combined with chaotic operators to achieve better effects