A Variable Neighborhood MOEA/D for Multiobjective Test Task Scheduling Problem

Abstract

Test task scheduling problem (TTSP) is a typical combinational optimization scheduling problem. This paper proposes a variable neighborhood MOEA/D (VNM) to solve the multiobjective TTSP. Two minimization objectives, the maximal completion time (makespan) and the mean workload, are considered together. In order to make solutions obtained more close to the real Pareto Front, variable neighborhood strategy is adopted. Variable neighborhood approach is proposed to render the crossover span reasonable. Additionally, because the search space of the TTSP is so large that many duplicate solutions and local optima will exist, the Starting Mutation is applied to prevent solutions from becoming trapped in local optima. It is proved that the solutions got by VNM can converge to the global optimum by using Markov Chain and Transition Matrix, respectively. The experiments of comparisons of VNM, MOEA/D, and CNSGA (chaotic nondominated sorting genetic algorithm) indicate that VNM performs better than the MOEA/D and the CNSGA in solving the TTSP. The results demonstrate that proposed algorithm VNM is an efficient approach to solve the multiobjective TTSP.

(ProQuest: ... denotes non-US-ASCII text omitted.)

Academic Editor:Kui Fu Chen

1, School of Electronic and Information Engineering, Beihang University, Beijing 100191, China

Received 26 October 2013; Revised 2 January 2014; Accepted 19 February 2014; 1 April 2014

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

1. Introduction

During recent decades, the manufacturing of electronic devices has become highly integrated and increasingly complex. As a result, the resource and time consumption expended on the test of electronic devices became a crucial problem in engineering application. Therefore, the research for improving the test efficiency is a topic that has attracted extensive attention. To address this situation, the objective of this research is to solve the test task scheduling problem (TTSP) more efficiently.

The goal of the TTSP is to arrange the execution of n tasks on m instruments. It is a difficult nondeterministic polynomial (NP) problem [1] for optimization. TTSP has some similarities with flexible job shop scheduling problem (FJSP) [2, 3], but the resource configuration of the TTSP is more flexible. For example, in the TTSP, one task can be performed on more than one instrument at a time. The precedence relationships in the TTSP resemble a network. One task can have one or more former or latter tasks in the TTSP. Generally speaking, feasible solutions are more difficult to be obtained in the TTSP than that in the FJSP.

TTSP, FJSP, and most scheduling problems belong to combinational optimization problems. For combinational optimization problems, the search space is too large that the best solution cannot be obtained by adopting the method of enumeration for even small-scale problem. Therefore, the intelligent algorithms based on integer programming model are devoted to solving these kinds of problems. Take FJSP as the example; genetic algorithm (GA) [4-7], simulated annealing (SA) [8-10], and the tabu search (TS) [11] have been successfully applied in solving scheduling optimization problem. FJSP receives extensive attention and researches, and many hybrid intelligent algorithms are invented for improving the performance of the solutions. For example, a combination of shuffled frog leaping and fuzzy logic is proposed to solve FJSP [12]. A particle swarm optimization (PSO) algorithm and TS algorithm are combined to solve the multiobjective FJSP [13]. A biogeography-based optimization (BBO) algorithm [14] was proposed for FJSP for finding optimum or near-optimum solution. Hybrid discrete particle swarm optimization for multiobjective flexible job-shop scheduling problem was proposed in article [15] especially for large-scale problems. The objective functions are different in each literature, but the makespan, the total tardiness, the critical machine workload, and the total workload of machines are frequently considered factors in those researches.

Different from the research of FJSP, the research of TTSP is relatively few because of the development of automatic test system. However, there are still some achievements in TTSP. Xia et al. [16] proposed a method that combined GA and simulated SA to optimize the parallel efficiency and speed up ratio of the multi-UUT parallel test. Genetic Algorithm-Ant Colony Algorithm (GA-ACA) [17], hybrid particle swarm and tabu search [18] and Ant Colony Algorithm [19] are used to solve parallel test tasks scheduling to obtain the minimum makespan. A chaotic nondominated sorting genetic algorithm is proposed to solve multiobjective TTSP [20]. The chaotic operations are combined with NSGA-II [21] in this approach. Those algorithms have shown excellent property in decreasing costs and improving efficiencies in automatic test system.

There are also some intelligent algorithms used to solve power dispatch problems and other scheduling problems. For example, opposition-based learning is employed in opposition-based gravitational search algorithm (OGSA) to solve optimal reactive power dispatch [22]. A fuzzified multiobjective PSO (FMOPSO) algorithm is proposed and implemented to dispatch the electric power [23]. An interactive artificial bee colony algorithm was proposed for the multiobjective environmental/economic dispatch problem [24].

In summary, most of the researches of scheduling problems focus on the single-objective problem or adopt weighted sum approach to convert the multiobjective problem into a single-objective problem. However, the weighting coefficients are difficult to choose, and human factors will greatly impact the performance of the algorithms. In fact, there are another two kinds of methods for solving the multiobjective problem. One method is the non-Pareto approach utilizing operators for processing the different objectives in a separated way. Another is the Pareto approaches which are directly based on the Pareto optimality concept. They aim at satisfying two goals: converging towards the Pareto front and also obtaining diversified solutions scattered all over the Pareto front. Those two kinds of methods mainly rely on the performance and strategies of the algorithms used in the multiobjective problems.

In this paper, the method based on Tchebycheff decomposition for multiobjective functions was adopted and the algorithm named MOEA/D is used to solve TTSP. MOEA/D is a typical evolutionary algorithm based on decomposition proposed by Zhang and Li [25]. This method decomposes a multiobjective optimization problem into a number of scalar optimization subproblems and optimizes them simultaneously. The results show that MOEA/D has a good performance for the ZDT and DTLZ test problems. MOEA/D is very efficient in solving multiobjective problems. Research on MOEA/D has also been performed in recent years. For example, Tan et al. [26] proposed a new version of MOEA/D with a uniform design to deal with the multiobjective problem in higher-dimensional objective spaces. This method can render the distribution of the weighting vectors more uniform, especially for problems with high dimension. Chen et al. [27] introduced a guided mutation operator and priority update to enhance the ability of MOEA/D. Stochastic ranking and constraint-domination principle are adopted in MOEA/D to improve the ability of the algorithm to deal with constrained multiobjective optimization problems [28]. Although these studies have improved the ability of MOEA/D for solving multi-objective problems, MOEA/D is mainly used to solve standard test cases like ZDT, DTLZ, and F1. However, MOEA/D is rarely used to solve combinational optimization problems such as FJSP, TTSP. Peng et al. applied MOEA/D to solve Travelling Salesman Problem (TSP) [29]. However, there is no special improvement for MOEA/D according to the feature of MOEA/D and the property of TSP.

The scheduling problems, such as TTSP, FJSP, and TSP, and power dispatching problem are a branch of combinational optimization problems. Because of the properties of the combinational optimization problems, the final best solutions only account for a rather small subset of the search space. How to avoid the solutions obtained being trapped in local optima is the key to improve the ability of algorithms to deal with combinational optimization problems. Considering the fact that the size of the neighborhood is important in MOEA/D [25], too large size will lead to degradation and too small size will weaken the effect of evolutionary process. Moreover, there will be many duplicate solutions due to the influence of neighborhood updating of MOEA/D [25]. The population diversity will decrease obviously. Based on the analyses above, variable neighborhood based on a quadratic curve is adopted to ensure that the crossover span is more reasonable, and Gauss mutation is adopted at the beginning of iteration to maintain the diversity of the population. These two improvements can efficiently enhance the ability of MOEA/D for avoiding the solutions obtained from being trapped in local optima. The proposed approach cannot only solve TTSP but also deal with other scheduling problems, because the feasible solutions of TTSP are more difficult to obtain than most scheduling problems such as FJSP, TSP.

The organization of this paper is as follows. A brief introduction of TTSP is introduced in Section 2. The new method for TTSP, variable neighborhood MOEA/D (VNM), is proposed in Section 3. The convergence analysis of VNM is also presented in Section 4. A large number of experimental results and discussions are covered in Section 5. Conclusions are given in Section 6.

2. The Formulation of TTSP

2.1. The Mathematical Model for TTSP

The goal of the TTSP is to arrange the execution of n tasks on m instruments. There are three main mathematical models for TTSP. One model is based on Petri net. The second is based on Graph theory. And the third model is based on integer programming. Our work in this paper is mainly based on the integer programming proposed by us in paper [20].

2.1.1. The Petri Net Model for TTSP

Petri net [30, 31] was proposed in 1962. Petri net focuses on the changes of the system, the conditions for changes, the influence of changes, and the relationships between changes. We assume that there is one test task _t1 in TTSP. The instruments occupied for _t1 are _r1 , _r2 , and _r3 . The Petri net model for this TTSP can be shown as Figure 1. In this model, there are four places (_p1 , _p2 , _p3 , and _p4 ), one transition (_t1 ), three tokens (_r1 , _r2 , and _r3 ), three variables (_v1 ,_v2 , and _v3 ), four arc expressions (_v1 , _v2 , _v3 , and (_v1 ,_v2 ,_v3 )), and a guard ([_r1 ,_r2 ,_r3 ] ), where _v1 , _v2 , and _v3 are bound to _r1 , _r2 , and _r3 .

Figure 1: The Petri net model for one task TTSP.

[figure omitted; refer to PDF]

In Figure 1, at the beginning, test resources _r1 , _r2 , and _r3 are vacant. The corresponding tokens for three places _p1 , _p2 , and _p3 are _r1 , _r2 , and _r3 , respectively. Therefore, _r1 , _r2 , and _r3 can be allocated to _t1 . When the _t1 is finished, the tokens in _p1 , _p2 , and _p3 will be transferred to place _p4 . The tokens in _p4 are _v1 , _v2 , and _v3 . This means that resources _r1 , _r2 , and _r3 are released. The Petri net can describe the relationships between tasks by the places and transitions, but the complex models are needed to be established. The process will increase the development cost and extend the development cycle.

2.1.2. The Graph Theory Model for TTSP

Graph theory [32] is an important branch of mathematics. By adopting the Graph theory, the complex project planning and processing can be described using "graphs." In TTSP, the vertexes of the graph represent the test tasks, and the lines between vertexes mean that some test instruments are common for these two tasks. For example, there are four test tasks (_t1 , _t2 , _t3 , and _t4 ) and four test instruments (_r1 , _r2 , _r3 , and _r4 ). The instruments set needed by _t1 , _t2 , _t3 , _t4 are {_r1 ,_r2 } , {_r2 ,_r4 } {_r3 ,_r4 } , and {_r1 ,_r3 } , respectively. The graph for this TTSP example is shown in Figure 2.

Figure 2: The Graph model for TTSP.

[figure omitted; refer to PDF]

Graph theory model can only be adopted by typical optimization methods. With the increment of the scale of TTSP, the computation expense will greatly increase, but typical optimization methods are not suitable for large-scale TTSP problem. Therefore, Graph theory model cannot solve large-scale TTSP also.

2.1.3. The Integer Programming Model for TTSP

TTSP is a typical integer programming problem. For the integer programming model for TTSP, the TTSP can be described as follows [20]: assume that n tasks and m instrument are included in TTSP. There is a task set T={_t1 ,_t2 ,...,_tj } (1...4;j...4;n ) and an instrument set R={_r1 ,_r2 ,...,_ri } (1...4;i...4;m ). ^Sji , ^Cji , and ^Pji represent the test start time, test finish time, and test consumed time of task _tj tested on instrument _ri , respectively. In the TTSP, one task can be tested on more than one instrument. A judgment matrix is used to express whether instrument _ri is needed for _tj . The judgment matrix is defined as the following: [figure omitted; refer to PDF]

In general, task _tj may have several possible test schemes. The set of test schemes for _tj is defined as _Wj ={^wj1 ,^wj2 ,...,^wj_kj } (_kj is the number of test schemes for _tj ). The notation ^Pjk =_{max...ri ∈^wjk} ...^Pji is used to express the test time of _tj for ^wjk .

The following describes the restriction of resources: [figure omitted; refer to PDF]

Basic hypothesis includes three factors. At a given time, an instrument can only execute one task; each task must be completed without interruption once it starts. Assume ^Pji =^Pjk , ^Cji =^Sji +^Pji to simplify the problem.

2.2. The Objective Functions for TTSP

The objective functions are very important in the study of multiobjective optimization problem. The makespan is very important in scheduling problems such as TTSP and FJSP, because the completion time is an essential factor for scheduling problem in product process. In additional, for TTSP, the test instruments have high integration, and the test instruments have become increasingly expensive. Therefore, the demand for reducing the workload of the instruments and increasing the service life of the test instruments has great significance in TTSP. Therefore, our work focuses on two main objectives. One is to minimize the maximal test completion time, and the other is to minimize the mean workload of the instruments. These objectives are represented by _f1 (x) and _f2 (x) .

(1) The Maximal Test Completion Time _{f 1} ( x ) . The notification ^Cjk =_{max...ri ∈^wjk} ...^Cji is the test completion time of _tj for ^wjk . Thus, the maximal test completion time of all tasks can be defined as follows: [figure omitted; refer to PDF]

(2) The Mean Workload of the Instruments _{f 2} ( x ) . First, a new notation Q is introduced to describe the parallel steps. The initial value of Q is 1. Assign the instruments for all of the tasks, if ^{Xjj* kk*} =1 , Q=Q+1 . Therefore, the mean workload of the instruments can be defined as follows: [figure omitted; refer to PDF]

3. The Variable Neighborhood MOEA/D Algorithm

In this section, we proposed a variable neighborhood MOEA/D algorithm (VNM). To obtain solutions close to the real Pareto Front (PF) of the TTSP, two strategies are adopted. The variable neighborhood strategy helps to make the crossover span more reasonable. Moreover, Gauss mutation is adopted at the beginning of the iteration to maintain the diversity of the population.

3.1. The Main Strategy of the VNM

The VNM is an evolutionary algorithm based on decomposition. The main strategy of the VNM is to decompose a multiobjective optimization problem into a number of scalar optimization subproblems and optimize these subproblems simultaneously. The decomposition method used is the Tchebycheff approach [33]. Each subproblem is bound with a weight vector, and then each subproblem is updated by obtaining information from its neighborhood [25]. The neighborhood of each subproblem is determined by its weighting vector.

Let {^λ1 ,^λ2 ,...,^λN } be a set of weight vectors, and ^z* =(^z1* ,^z2* ,...,^zm*)T is defined as the reference point. The problem of the Pareto Front approximation can be decomposed into N scalar optimization subproblems using the Tchebycheff approach, and the objective function of the j th subproblem is defined as [figure omitted; refer to PDF] where Ω is the decision space and ^λj =(^λ1j ,^λ2j ,...,^λmj)T , ^zi* =min...{_fi (x)|"x⊂Ω} for each i=1,2,...,m . It is clear that the VNM is able to minimize all N objective functions simultaneously in a single run.

The main procedure of the VNM can be described as shown in Figure 3.

Figure 3: The main procedure of the VNM.

[figure omitted; refer to PDF]

In the part of parameter setting, the iteration number M , the subproblem number N , the size of neighborhood T (which ranges from beginning size B to stopping size S ), and the population for saving the optimal solutions EP are set.

The crossover operation in VNM is as follows.

For each individual ^xit in generation t , the child ^xit+1 can be obtained by the following equation: [figure omitted; refer to PDF] CR , _F1 , and _F2 are the three control variables for the crossover; ^xi1t and ^xi2t are two individuals chosen in the neighborhood of ^xit . This crossover method can make full use of the information from the neighborhood and render the information exchange more sufficient.

The main idea of VNM is given above. Two improvements are involved in the VNM algorithm. Variable neighborhood strategy is adopted to make the crossover span more reasonable. Moreover, Starting Mutation is used to enhance the diversity of the population.

3.2. Variable Neighborhood

In the VNM, the size of the neighborhood T has a high impact on the performance of the algorithm. If T is too large, the two solutions chosen (^xl and ^xk ) for the genetic operation may be unsuitable for the subproblem, and degradation may occur during the progress of the evolution. In contrast, if T is too small, the subproblems are all similar. The child individual will be so similar to its parents that the crossover operation will have a weak effect.

T is the neighborhood size which determines the crossover and neighborhood updating span. Too large and too small T will both have a negative influence on VNM. Therefore, T should be large enough at the beginning of the evolution period to ensure sufficient information exchange of the solutions, and T should be sufficiently small in the latter portion of the evolution period such that degradation can be avoided. Motivated by this ideology, we designed and tested three curves to find the best T controlling curve.

The three curves are shown in Figure 4. In this figure, the abscissa is the number of iterations, and the ordinate is the size of the neighborhood. M1 , M2 , and M3 represent the straight line, the monotonic parabolic and the nonmonotonic parabolic curves, respectively. It is worth noting that in curve M2 , the curvature will be 0 at the end of the evolution period. This means that the rate of change of curvature for M2 is the fastest of all of the concave monotone parabolas during the period of evolution. Because the curvature goes to 0 in the end, curve M2 is determined. Assume that if the number of iterations is 125, the neighborhood of curves M1 , M2 , and M3 are _y1 , _y2 , and _y3 , respectively, in accordance with the equation: _y1 -_y2 =_y2 -_y3 . Thus, curve M3 can be also determined. Curve M3 is a nonmonotonic parabolic curve. A series of experiments should be performed to compare the influence of the three curves on the algorithm to identify the best controlling curve.

Figure 4: Three controlling curves for the neighborhood size.

[figure omitted; refer to PDF]

3.3. Starting Mutation

The TTSP represents a typical combinational optimization problem. The final best solutions may be limited to only several points in the solution space. Because of the neighborhood updating effect of the VNM, there will be many duplicate solutions so that the crossover operation will have little effect. Therefore, how to maintain the diversity of the population is the key question for enhancing the algorithm effect.

Motivated by the ideology above, a starting Gauss mutation is adopted at the beginning of the iteration. For a solution ^xi =(^x1i ,^x2i ,...,^xMi ) (M is the number of variables), Gauss mutation is described as the following: [figure omitted; refer to PDF] ^xi* =(^x1i* ,^x2i* ,....^xMi* ) represents the individual after mutation, p is the mutation probability, normal (^xji ,σ) is a number that obeys the normal distribution, ^xji is the mean value, and σ is the variance. With Starting Mutation, the problem with the initially invalid crossover operation can be resolved. Therefore, we can avoid the solutions from becoming trapped in local optima, and thus solutions with higher quality are obtained.

4. The Convergence Analysis of VNM

The convergence analysis of VNM in this section provides the theory ground for its application. The convergence behavior of VNM is analyzed according to the Markov Chain and the transfer matrix, respectively.

4.1. Strong and Weak Convergence

This section proposes the basic theories of convergence and proves the strong and weak convergence of VNM from the perspective of Markov Chain.

There is a global optimal solution set M for MOPs (multiobjective problem). M is defined as M={X;∀Y∈S,f(X)...5;f(Y)} . It is assumed that X[arrow right](n) is the population in evolutionary algorithms.

A detailed demonstration for the convergence of MOEA has been proposed in paper [34]. Based on it, the definitions are described as follows.

Theorem 1.

_{α n} , _βn , and _rn are defined as [figure omitted; refer to PDF] If _{lim...n[arrow right]∞rn} =0 , X[arrow right]......(n) converges to global optimal solution weakly. It is defined as X[arrow right]......(n)[arrow right]M(P.W.) .

Theorem 2.

_{α - n} , _β-n , and _r-n are defined as [figure omitted; refer to PDF] If _{lim...n[arrow right]∞r-n} =0 , X[arrow right]......(n) converges to global optimal solution strongly. It is defined as X[arrow right]...(n)[arrow right]M(P.S.) .

Based on Theorems 1 and 2 above, the demonstration for the convergence of VNM is described in the following. Here, _{lim...n[arrow right]∞βn} =0 , _{lim...n[arrow right]∞} ..._β-n =0 describe the evolutionary trend of VNM. There is _{lim...n[arrow right]∞rn} =0 , _{lim...n[arrow right]∞r-n} =0 .

Proof.

It is defined as P(n)=P{X...(n)∩M=∅} .

Based on Bayesian, we have [figure omitted; refer to PDF] Elitist strategy is adopted in VNM, _αn =0 . Hence [figure omitted; refer to PDF] Then, [figure omitted; refer to PDF] Therefore, we have [figure omitted; refer to PDF] It means that X[arrow right]......(n) converges to global optimal solution weakly.

Similarly, it is defined as P(n)=P{X[arrow right]...(n)∩^Mc ...0;∅} .

By Bayesian formula, we have [figure omitted; refer to PDF] Elitist strategy is adopted in VNM, _{lim...n[arrow right]∞} ..._α-n =0 . Hence [figure omitted; refer to PDF] Then, [figure omitted; refer to PDF] Therefore, we have [figure omitted; refer to PDF] It means that X[arrow right]......(n) converges to global optimal solution strongly.

4.2. Convergence to Global Optimal

This part focuses on the elitist strategy and proves that the VNM converges to the global optimum from the perspective of transfer matrix.

Theorem 3 (see [35]).

P = ( C 0 R T ) is a reducible stochastic matrix, where C:m×m is primitive stochastic matrix and R,T...0;0 . Then, [figure omitted; refer to PDF] where ^P∞ is a stable stochastic matrix with ^P∞ =^{1[variant prime]p∞} . ^p∞ =^p0P∞ is unique regardless of the initial distribution. The matrix ^p∞ satisfies that ^pi∞ >p for 1...4;i...4;m and ^pi∞ =0 for m<i...4;n .

According to the previous description of VNM, the extended transition matrices for crossover ^C+ , mutation ^M1+ , ^M2+ , selection ^S+ can be written as block diagonal matrix and upgrade matrix U is lower triangular: [figure omitted; refer to PDF] ^C+ , ^M1+ , ^S+ , ^M2+ , and U are with ^2nl square matrices. C , _M1 , _M2 , S , and _Uab (1...4;a , b...4;^2nl ) are all with the size of n×n (n is the number of individuals and l is the number of individual attributes).

a , b in _Uab represents the population's state sequence number (in the order of the populations of the pros and cons from 1 to ^2nl ). So U is used to represent population's selection process. Each block matrix _Uab is a selection of individuals. The details in _Uab can be described as: there are some individuals to make _uij =1 established in each row. Firstly, the first individual is compared with all other individuals, _u1j =1 if j th individual is optimal (there may be several optima) or _u11 =1 if no one is better than it. Then, the second individual is compared with all other individuals except the first individual. The best individual, g th individual, is chosen; set _u2g =1 if g th individual is optimal or _u22 =1 if there is no one better than the second individual. The sorting process continues until all individuals are sorted. To simplify the difficulty of the problem, assume that the there is only one global optimal solution set. Then, only _U11 is a unit matrix, whereas all matrices _Uaa with a...5;2 are not unit matrices.

In VNM, the populations go through Gauss mutation ^M1+ , crossover ^C+ , mutation ^M2+ , selection ^S+ , and EP upgrade matrix U . It is worth of noticing that (μ+λ) selection mode is not used in the evolutionary process of VNM and the number of individuals remains unchanged. This means that ^S+ =I . The transition matrix ^P+ for VNM is [figure omitted; refer to PDF] There is _P11 >0 in the transition matrix ^P+ . The submatrices _Pal which is with a...5;2 may be gathered in a rectangular matrix R...0;0 so that Theorem 3 can be used to prove that the corresponding VNM converges to the global optimum [36].

5. Experimental Results and Analysis

Computational experiments are carried out to compare the approaches and to evaluate the efficiency of the proposed method. There are two objectives: to minimize the makespan and the mean workload of the instruments. In this section, the performance metric, coverage metric C , is introduced first. There are two experimental instances adopted in this section. They are instances of 30 tasks with 12 instruments and 40 tasks with 12 instruments which are real-world examples taken from a missile system. The instance of 40 tasks with 12 instruments is displayed in Table 1. The instance of 30 tasks with 12 instruments is the first 30 tasks in Table 1. The experiment of selection of controlling curve for neighborhood size is shown in Section 5.2. The verification of the improvements of the algorithm is displayed in Section 5.3. In Section 5.3, VNM is compared with MOEA/D. In Section 5.4, the proposed algorithm (VNM) is compared with the variations of CNSGA using real-world TTSP problems. All of the algorithms are executed using 50 independent runs. In all of the experiments, the better performances are denoted in bold. The basic algorithm parameter settings are displayed in Table 2. CR , _F1 , and _F2 are the three control variables for the crossover. p is the mutation probability.

Table 1: The instance of 40 tasks with 12 instruments.

Task	Scheme	Resource	Time
t 1	w 1 1	r 1 , r 7	5
w 1 2	r 3 , r 5	5
w 1 3	r 6 , r 10	4
t 2	w 2 1	r 2 , r 11	5
w 2 2	r 4 , r 9	4
w 2 3	r 5 , r 6	6
w 2 4	r 3 , r 7	4
t 3	w 3 1	r 3	7
w 3 2	r 12	5
t 4	w 4 1	r 9	25
w 4 2	r 10	22
t 5	w 5 1	r 12	14
t 6	w 6 1	r 1 , r 4	7
w 6 2	r 3 , r 7	8
w 6 3	r 6 , r 8	8
t 7	w 7 1	r 1 , r 2	4
w 7 2	r 3 , r 8	2
w 7 3	r 7 , r 11	3
t 8	w 8 1	r 1 , r 3	5
w 8 2	r 6 , r 10	4
w 8 3	r 7 , r 12	7
t 9	w 9 1	r 1 , r 4	11
w 9 2	r 7 , r 9	13
w 9 3	r 8 , r 11	12
t 10	w 10 1	r 2	9
w 10 2	r 4	10
w 10 3	r 10	10
t 11	w 11 1	r 2 , r 7	6
w 11 2	r 3 , r 12	9
w 11 3	r 8 , r 9	8
t 12	w 12 1	r 2	11
w 12 2	r 5	13
w 12 3	r 11	15
t 13	w 13 1	r 2	4
w 13 2	r 8	5
w 13 3	r 9	7
t 14	w 14 1	r 3	7
w 14 2	r 11	10
w 14 3	r 12	8
t 15	w 15 1	r 12	2
t 16	w 16 1	r 2	9
w 16 2	r 5	7
w 16 3	r 8	6
t 17	w 17 1	r 1 , r 10	10
w 17 2	r 5 , r 9	12
w 17 3	r 11 , r 12	11
t 18	w 18 1	r 6	15
t 19	w 19 1	r 2	8
w 19 2	r 5	7
w 19 3	r 10	7
w 19 4	r 12	6
t 20	w 20 1	r 3	6
w 20 2	r 6	4
w 20 3	r 9	5
t 21	w 21 1	r 1 , r 4	2
w 21 2	r 3 , r 5	5
w 21 3	r 6 , r 8	3
t 22	w 22 1	r 2	3
w 22 2	r 4	4
w 22 3	r 6	3
w 22 4	r 10	4
t 23	w 23 1	r 3	5
w 23 2	r 12	5
t 24	w 24 1	r 4	14
w 24 2	r 11	17
t 25	w 25 1	r 7	19
t 26	w 26 1	r 1 , r 4	7
w 26 2	r 3 , r 7	8
w 26 3	r 6 , r 8	10
t 27	w 27 1	r 1 , r 2	2
w 27 2	r 1 , r 7	2
w 27 3	r 3 , r 8	4
t 28	w 28 1	r 1 , r 3	5
w 28 2	r 4 , r 5	4
w 28 3	r 7 , r 12	2
t 29	w 29 1	r 1 , r 4	11
w 29 2	r 3 , r 4	15
w 29 3	r 7 , r 8	12
t 30	w 30 1	r 1	9
w 30 2	r 4	12
w 30 3	r 12	10
t 31	w 31 1	r 2 , r 3	6
w 31 2	r 5 , r 11	8
w 31 3	r 6 , r 9	8
t 32	w 32 1	r 2	11
w 32 2	r 5	13
w 32 3	r 6	17
t 33	w 33 1	r 2	6
w 33 2	r 6	5
w 33 3	r 11	4
t 34	w 34 1	r 3	7
w 34 2	r 7	8
w 34 3	r 12	10
t 35	w 35 1	r 9	2
t 36	w 36 1	r 2	9
w 36 2	r 5	7
w 36 3	r 10	6
t 37	w 37 1	r 1 , r 2	10
w 37 2	r 7 , r 11	7
w 37 3	r 5 , r 12	11
t 38	w 38 1	r 10	15
t 39	w 39 1	r 4	8
w 39 2	r 6	7
w 39 3	r 9	7
w 39 4	r 10	6
t 40	w 40 1	r 3	6
w 40 2	r 6	5
w 40 3	r 9	5

Table 2: Parameters setting.

Population	Generation	CR	F 1	F 2	P
100	250	0.5	1	1	0.05

5.1. Performance Metric

For multiobjective optimization, the convergence to the Pareto-optimal set is the most important target to be considered. There are mainly two metrics to evaluate the convergence. One is convergence metric γ , and the other is convergence metric C . The true set of Pareto-optimal solutions is necessary for the calculation of γ . However, the solutions space of TTSP is so large that the true set of Pareto-optimal solutions cannot be obtained by enumeration. The metric C can be used to compare the performances of the two solutions sets obtained by different algorithms. The calculation of C needs only the information of the two solutions sets. Therefore, in this paper the convergence metric C is used to evaluate the performance of the proposed algorithm.

Assume that A and B are two sets of nondominated solutions, and C(A,B) is the ratio of the solutions in B that are dominated by at least one solution in A . Hence, [figure omitted; refer to PDF] C(A,B)=1 means that all of the solutions in B are dominated by solutions in A , and C(A,B)=0 means that there is no solution in B dominated by a solution in A . Generally speaking, if C(A,B)>C(B,A) , then solution set A is better than solution set B .

5.2. The Selection of Controlling Curve

In this section, three curves are designed and tested to identify the best T controlling curve. M1 , M2 , and M3 , respectively, represent the straight line, monotonic parabolic and nonmonotonic parabolic curves shown in Figure 4. In curve M2 , the curvature will be 0 at the end of the evolution period. Because of the influence of neighboring updating in MOEA/D, many duplicate solutions will be presented in the final evolution process of MOEA/D. Therefore, Starting Mutation is applied to the beginning of the next iteration to maintain the population diversity. Tables 3 and 4 show the comparison of the influence of the three curves on the algorithm using two instances. The results show that the monotonic parabolic curve M2 has the best performance. This means that the monotonic curve with the fastest rate of change of curvature is the most useful for the algorithm. And the boxplots of three curves for 30*12 and 40*12 instances in Figures 5 and 6 also give the same conclusion.

Table 3: Comparison of influence of three curves for 30*12 instance.

	Average	Times
C ( M 1 , M 2 )	0.2213	13
C ( M 2 , M 1 )	0.5196	37
C ( M 2 , M 3 )	0.4964	36
C ( M 3 , M 2 )	0.2069	14

Table 4: Comparison of influence of three curves for 40*12 instance.

	Average	Times
C ( M 1 , M 2 )	0.244178	14
C ( M 2 , M 1 )	0.501508	36
C ( M 2 , M 3 )	0.533806	38
C ( M 3 , M 2 )	0.242146	12

Figure 5: The boxplot of three curves for 30*12 instance.

[figure omitted; refer to PDF]

Figure 6: The boxplot of three curves for 40*12 instance.

[figure omitted; refer to PDF]

5.3. Experiments for Comparisons of VNM and MOEA/D

In order to verify the improvement of VNM, 30*12 , and 40*12 instances are used to test the performance of VNM and MOEA/D. The monotonic parabolic curve M2 is selected as the controlling curve in VNM. The neighborhood size in MOEA/D is 20. V and M , respectively, represent VNM and MOEA/D. The results in Tables 5 and 6 show that the concave curve with the fastest rate of change of curvature obtained improvement for VNM. The selected curve renders the size of the neighborhood more suitable than before.

Table 5: Comparison of VNM and MOEA/D for 30 * 12 instance.

	Average	Times
C ( V , M )	0.4845	35
C ( M , V )	0.2104	15

Table 6: Comparison of VNM and MOEA/D for 40 * 12 instance.

	Average	Times
C ( V , M )	0.5256	40
C ( M , V )	0.1949	10

The results of the two independent experiments for comparison of VNM and MOEA/D are shown in Figures 7 and 8 for the 30 * 12 and 40 * 12 instances, respectively. As shown in the figures the solutions obtained by the VNM dominate most of the solutions obtained by MOEA/D. Variable neighborhood and Starting Mutation improve the performance of MOEA/D efficiently.

The comparison of VNM and MOEA/D for 30*12 instance.

(a) [figure omitted; refer to PDF]

(b) [figure omitted; refer to PDF]

The comparison of VNM and MOEA/D for 40*12 instance.

(a) [figure omitted; refer to PDF]

(b) [figure omitted; refer to PDF]

Figures 9 and 10 are the boxplots for comparison of VNM and MOEA/D. It shows that the data distribution of VNM is superior to MOEA/D. VNM has the better performance because of application of variable neighborhood and Starting Mutation.

Figure 9: The boxplot of comparison of VNM and MOEA/D for 30*12 instance.

[figure omitted; refer to PDF]

Figure 10: The boxplot of comparison of VNM and MOEA/D for 40*12 instance.

[figure omitted; refer to PDF]

5.4. Experiments for Comparisons of VNM and CNSGA

In this section, the VNM is compared with the CNSGA for TTSP. CNSGA is based on NSGA-II. NSGA-II has been successfully applied to job shop scheduling problems [37], reactive power dispatch problems [38], and many other applications. CNSGA has successfully been adopted to solve TTSP [20]. Therefore, a comparison of VNM and CNSGA is carried out to test the performance of the proposed algorithm VNM.

There are two chaotic sequences, logistic map and cat map, and the chaotic sequences can be applied in three positions, population initialization, crossover, and mutation. Therefore, there are six combinations for CNSGA. The nomenclatures for six variants of CNSGA are shown in Table 7. Tables 8 and 9 show the comparison of VNM and CNSGA for 30*12 and 40*12 instances. The VNM is represented by V . All the comparisons between VNM and the variations of CNSGA are based on 50 independent experiments. The average of C metric and better computational times are used for the performance analysis. The results from Tables 8 and 9 show that VNM provides the best performance not only for the average metric C but also in terms of better computational times than CNSGA.

Table 7: Nomenclature for six variants of the CNSGA.

	The logistic map	The cat map
Initial population	L 1	C 1
Crossover operator	L 2	C 2
Mutation operator	L 3	C 3

Table 8: Comparison of VNM and six variations of CNSGA for 30 * 12 instance.

	Average	Times
C ( V , L 1 )	0.4206	36
C ( L 1 , V )	0.2200	14
C ( V , L 2 )	0.4077	34
C ( L 2 , V )	0.2648	16
C ( V , L 3 )	0.4182	36
C ( L 3 , V )	0.2248	14
C ( V , C 1 )	0.4638	35
C ( C 1 , V )	0.2210	15
C ( V , C 2 )	0.4602	34
C ( C 2 , V )	0.2288	16
C ( V , C 3 )	0.4128	35
C ( C 3 , V )	0.2525	15

Table 9: Comparison of VNM and six variations of CNSGA for 40 * 12 instance.

	Average	Times
C ( V , L 1 )	0.5243	37
C ( L 1 , V )	0.2264	13
C ( V , L 2 )	0.5359	36
C ( L 2 , V )	0.2282	14
C ( V , L 3 )	0.5218	38
C ( L 3 , V )	0.2338	12
C ( V , C 1 )	0.5044	36
C ( C 1 , V )	0.2138	14
C ( V , C 2 )	0.4844	35
C ( C 2 , V )	0.2169	15
C ( V , C 3 )	0.5116	37
C ( C 3 , V )	0.2055	13

Figures 11 and 12 show the comparisons of VNM and the 6 variations of CNSGA for 30*12 instance. The figures show that the solutions obtained by the VNM dominate most of the solutions obtained by the 6 variations of CNSGA. Therefore, the VNM obtains the best performance.

Figure 11: The comparison of VNM and three variations with logistic map for CNSGA for 30*12 instance.

[figure omitted; refer to PDF]

Figure 12: The comparison of VNM and three variations with cat map for CNSGA for 30*12 instance.

[figure omitted; refer to PDF]

The results of the comparison of VNM and CNSGA for the 40 * 12 instance are shown in Figures 13 and 14. The results also show that the solutions obtained by VNM have higher quality.

Figure 13: The comparison of VNM and three variations with logistic map for CNSGA for 40*12 instance.

[figure omitted; refer to PDF]

Figure 14: The comparison of VNM and three variations with cat map for CNSGA for 40*12 instance.

[figure omitted; refer to PDF]

In addition, box plots are used to display the performances of the algorithms. The box plots of C metric for VNM and CNSGA with 30*12 and 40*12 instances are shown from Figures 15, 16, 17, and 18.

Figure 15: The boxplot of VNM and three variations with logistic map for CNSGA for 30*12 instance.

[figure omitted; refer to PDF]

Figure 16: The boxplot of VNM and three variations with cat map for CNSGA for TTSP 30*12 instance.

[figure omitted; refer to PDF]

Figure 17: The boxplot of VNM and three variations with logistic map for CNSGA for 40*12 .

[figure omitted; refer to PDF]

Figure 18: The boxplot of VNM and three variations with cat map for CNSGA for 40*12 .

[figure omitted; refer to PDF]

From the box plots of C metric, it is clear that the median of VNM is larger than that of the variations of CNSGA in both the 30 * 12 and 40 * 12 instances, and the data distribution of VNM is more reasonable as well. Additionally, the average of VNM is also superior. The results show that VNM demonstrates better performance than CNSGA in solving the multiobjective TTSP. The performance of solutions obtained by VNM is better than that obtained by CNSGA because that the variable neighborhood is adopted in VNM. The span of information exchange in VNM changes following the evolutionary process, but that in CNSGA stays the same. The information from the process of evolution helps VNM get better performance.

The variable neighborhood provides a strategy to improve the performance of the algorithm. For different problems with different scales, the controlling curves for the neighborhood size will be different. The Starting Mutation can be also applied to solve other optimization problem in the evolution process. The strategies proposed in this paper can be investigated in other scheduling problem similar to TTSP.

6. Conclusion

How to improve the test efficiency is more and more important in modern industry. TTSP has important application value in modern manufacturing process. TTSP is combinational optimization problem. The final best solutions only account for a rather small subset of the search space. In order to help the solutions avoid being trapped in local optima, this paper proposed a new genetic evolutionary multiobjective optimization algorithm (VNM) to solve the TTSP. The variable neighborhood and Starting Mutation strategies are adopted in VNM to make the crossover span more suitable and improve the diversity of population. Three controlling curves for neighborhood size are studied. The experimental results have shown that the monotonic parabolic has the best performance. From the experiment conducted for comparison of VNM and MOEA/D, we see that the improved algorithm has made great progress in solving the TTSP problem. And the experiment conducted for comparison of VNM and CNSGA also shows that the improved algorithm is superior to CNSGA in solving TTSP. VNM can also be applied to solve other combinational optimization problems such as FJSP and TSP. Future work will focus on two objectives: the precedence constraint will be added to the TTSP, and information regarding bottleneck tasks will be considered.

Acknowledgments

This research is supported by the National Natural Science Foundation of China under Grant no. 61101153 and the National 863 Hi-Tech R and D Plan under Grant 2011AA110101.

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

References

[1] A. Radulescu, C. Nicolescu, A. J. C. van Gemund, P. P. Jonker, "CPR: mixed task and data parallel scheduling for distributed systems," in Proceeding of 15th Parallel and Distributed Processing Symposium, pp. 1-9, San Francisco, Calif, USA, April 2001.

[2] Z. Yin, J. Cui, Y. Yang, Y. Ma, "Job shop scheduling problem based on DNA computing," Journal of Systems Engineering and Electronics , vol. 17, no. 3, pp. 654-659, 2006.

[3] Y. Zuo, H. Y. Gu, Y. G. Xi, "Modified bottleneck-based heuristic for large-scale job-shop scheduling problem with a single bottleneck," Journal of Systems Engineering and Electronics , vol. 18, no. 3, pp. 556-565, 2007.

[4] N. Al-Hinai, T. Y. Elmekkawy, "Robust and stable flexible job shop scheduling with random machine breakdowns using a hybrid genetic algorithm," International Journal of Production Economics , vol. 132, no. 2, pp. 279-291, 2011.

[5] J. C. Chen, C.-C. Wu, C.-W. Chen, K.-H. Chen, "Flexible job shop scheduling with parallel machines using genetic algorithm and grouping genetic algorithm," Expert Systems with Applications , vol. 39, no. 11, pp. 10016-10021, 2012.

[6] L. De Giovanni, F. Pezzella, "An improved genetic algorithm for the distributed and flexible job-shop scheduling problem," European Journal of Operational Research , vol. 200, no. 2, pp. 395-408, 2010.

[7] D. Lei, "Co-evolutionary genetic algorithm for fuzzy flexible job shop scheduling," Applied Soft Computing Journal , vol. 12, no. 8, pp. 2237-2245, 2012.

[8] R. Zhang, C. Wu, "A hybrid immune simulated annealing algorithm for the job shop scheduling problem," Applied Soft Computing Journal , vol. 10, no. 1, pp. 79-89, 2010.

[9] P. Damodaran, M. C. Vélez-Gallego, "A simulated annealing algorithm to minimize makespan of parallel batch processing machines with unequal job ready times," Expert Systems with Applications , vol. 39, no. 1, pp. 1451-1458, 2012.

[10] K. Li, Y. Shi, S.-L. Yang, B.-Y. Cheng, "Parallel machine scheduling problem to minimize the makespan with resource dependent processing times," Applied Soft Computing Journal , vol. 11, no. 8, pp. 5551-5557, 2011.

[11] Q. Zhang, H. Manier, M.-A. Manier, "A genetic algorithm with tabu search procedure for flexible job shop scheduling with transportation constraints and bounded processing times," Computers and Operations Research , vol. 39, no. 7, pp. 1713-1723, 2012.

[12] W. Teekeng, A. Thammano, "A combination of shuffled frog leaping and fuzzy logic for flexible job-shop scheduling problems," Procedia Computer Science , vol. 6, pp. 69-75, 2011.

[13] G. Zhang, X. Shao, P. Li, L. Gao, "An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem," Computers and Industrial Engineering , vol. 56, no. 4, pp. 1309-1318, 2009.

[14] S. H. A. Rahmati, M. Zandieh, "A new biogeography-based optimization (BBO) algorithm for the flexible job shop scheduling problem," The International Journal of Advanced Manufacturing Technology , vol. 58, no. 9-12, pp. 1115-1129, 2012.

[15] X. Y. Shao, W. Q. Liu, Q. Liu, C. Y. Zhang, "Hybrid discrete particle swarm optimization for multi-objective flexible job-shop scheduling problem," The International Journal of Advanced Manufacturing Technology , vol. 67, no. 9-12, pp. 2885-2901, 2013.

[16] R. Xia, M. Xiao, J. Cheng, X. Fu, "Optimizing the multi-UUT parallel test task scheduling based on multi-objective GASA," in Proceedings of the 8th International Conference on Electronic Measurement and Instruments (ICEMI '07), pp. 4839-4844, Xi'an, China, August 2007.

[17] J. Y. Fang, H. H. Xue, M. Q. Xiao, "Parallel test tasks scheduling and resources configuration based on GA-ACA," Journal of Measurement Science and Instrumentation , vol. 2, no. 4, pp. 321-326, 2011.

[18] H. Lu, X. Chen, J. Liu, "Parallel test task scheduling with constraints based on hybrid particle swarm optimization and taboo search," Chinese Journal of Electronics , vol. 21, no. 4, pp. 615-618, 2012.

[19] X. Liang, B. G. Dong, H. Gao, D. S. Yan, "Parallel test task scheduling of aircraft electrical system based on cost constraint matrix and ant colony algorithm," in Proceeding of IEEE 10th International Conference on Industrial Informatics, pp. 178-183, Beijing, Chinese, July 2012.

[20] H. Lu, R. Y. Niu, J. Liu, Z. Zhu, "A chaotic non-dominated sorting genetic algorithm for the multi-objective automatic test task scheduling problem," Applied Soft Computing , vol. 13, no. 5, pp. 2790-2802, 2013.

[21] K. Deb, A. Pratap, S. Agarwal, T. Meyarivan, "A fast and elitist multiobjective genetic algorithm: NSGA-II," IEEE Transactions on Evolutionary Computation , vol. 6, no. 2, pp. 182-197, 2002.

[22] B. Show, V. Mukherjee, S. P. Ghoshal, "Solution of reactive power dispatch of power systems by an opposition-based gravitational search algorithm," Electrical Power and Energy Systems , vol. 55, pp. 29-40, 2014.

[23] L. Wang, C. Singh, "Environmental/economic power dispatch using a fuzzified multi-objective particle swarm optimization algorithm," Electric Power Systems Research , vol. 77, no. 12, pp. 1654-1664, 2007.

[24] O. Abedinia, D. Garmarodi, R. Rahbar, F. Javidzadeh, "Multi-objective environmental/economic dispatch using interactive artificial bee colony algorithm," Journal of Basic and Applied Scientific Research , vol. 2, no. 11, pp. 11272-11281, 2012.

[25] Q. Zhang, H. Li, "MOEA/D: a multiobjective evolutionary algorithm based on decomposition," IEEE Transactions on Evolutionary Computation , vol. 11, no. 6, pp. 712-731, 2007.

[26] Y.-Y. Tan, Y.-C. Jiao, H. Li, X.-K. Wang, "MOEA/D+ uniform design: a new version of MOEA/D for optimization problems with many objectives," Computers and Operations Research , 2012.

[27] C.-M. Chen, Y.-P. Chen, Q. Zhang, "Enhancing MOEA/D with guided mutation and priority update for multi-objective optimization," in Proceedings of the IEEE Congress on Evolutionary Computation (CEC '09), pp. 209-216, Trondheim, Norway, May 2009.

[28] M. A. Jan, R. A. Khanum, "A study of two penalty-parameterless constraint handling techniques in the framework of MOEA/D," Applied Soft Computing , vol. 13, no. 1, pp. 128-148, 2012.

[29] W. Peng, Q. Zhang, H. Li, "Comparison between MOEA/D and NSGA-II on the multi-objective travelling salesman problem," Studies in Computational Intelligence , vol. 171, pp. 309-324, 2009.

[30] P. A. Carl Communication with Automata , Applied Data Research, Princeton, NJ, USA, 1966.

[31] T. Zhang, B. Guo, Y. Tan, "Capacitated stochastic coloured Petri net-based approach for computing two-terminal reliability of multi-state network," Journal of Systems Engineering and Electronics , vol. 23, no. 2, pp. 304-313, 2012.

[32] B. Bollobas Graph Theory , Springer, New York, NY, USA, 1979.

[33] K. Miettinen Nonlinear Multiobjective Optimization , Kluwer Academic, Boston, Mass, USA, 1999.

[34] Y.-R. Zhou, H.-Q. Min, X.-Y. Xu, Y.-X. Li, "Multi-objective evolutionary algorithm and its convergence," Chinese Journal of Computers , vol. 27, no. 10, pp. 1415-1421, 2004.

[35] M. Iosifescu Finite Markov Processes and Their Applications , Dover, 1980.

[36] Q. Zhang, L. Dong, F. Jiang, X. J. Zhu, "Convergence of multi-objective evolutionary computation to its pareto optimal set," Systems Engineering and Electronics , vol. 22, no. 8, pp. 17-21, 2000.

[37] E. Moradi, S. M. T. Fatemi Ghomi, M. Zandieh, "Bi-objective optimization research on integrated fixed time interval preventive maintenance and production for scheduling flexible job-shop problem," Expert Systems with Applications , vol. 38, no. 6, pp. 7169-7178, 2011.

[38] S. Jeyadevi, S. Baskar, C. K. Babulal, M. Willjuice Iruthayarajan, "Solving multiobjective optimal reactive power dispatch using modified NSGA-II," International Journal of Electrical Power and Energy Systems , vol. 33, no. 2, pp. 219-228, 2011.