
Research Article


Multicriteria Decision Mechanism CNSGAAHP for the Automatic Test Task Scheduling Problem 

Hui Lu,
Ruiyao Niu,
Jing Liu
and
Zheng Zhu



ABSTRACT

Task scheduling problem is one of the key technologies for
automatic test systems. This study proposes a novel and integrated multicriteria
decision mechanism called the chaotic nondominated sorting genetic algorithm
plus analytic hierarchy process (CNSGAAHP) for the automatic test task scheduling
problem (ATSP). This mechanism contains two parts: the multiobjective optimisation
algorithm CNSGA and the decision making method AHP. CNSGA hybrids chaotic sequences
based on the logistic map and the nondominated sorting genetic algorithm II
(NSGAII) to avoid becoming trapped in local optima. It is responsible for the
search process and obtains a set of compromise solutions. However, getting this
set does not completely solve the problem. A best compromise solution still
must be chosen out of that set. Thereupon, AHP is used for the final decision
making process and chooses a best schedule from the solutions obtained by CNSGA.
The applied AHP can handle uncertainty, make the consistency check easily to
pass and reduce the workload of decisionmakers. A realworld ATSP abstracted
from a missile system is applied to verify the effectiveness of CNSGAAHP. Results
show that CNSGAAHP is very concise and suitable for the ATSP.





Received: February 28, 2012;
Accepted: April 24, 2012;
Published: July 03, 2012


INTRODUCTION
Automatic test technology has been used in aerospace systems to ensure safety
and in some modern manufacturing processes to improve the production efficiency.
One important feature of the Next Generation Automatic Test System (NGATS) is
parallel testing (Curry et al., 2006). Parallel
testing makes it possible to test more than one task at the same time. It can
improve the throughput by taking full advantage of the test hardware. On the
other hand, it increases the complexity of the system (Anderson,
2003). Therefore, an effective and efficient dispatching method for the
Automatic Test Task Scheduling problem (ATSP) is significant. However, a concrete
optimised algorithm has not been fully elucidated (Zhou
et al., 2009). Hence, this study is motivated to perform.
The mean work of dispatching method for the ATSP is allocating a task onto
the available instruments to improve the throughput, reduce the test time and
optimise the resource allocation (Xia et al., 2007a).
Many metaheuristics methods and evolutionary algorithms have been proposed
to solve the scheduling problems. The Simulated Annealing (SA), the Tabu Search
(TS) and the Genetic Algorithm (GA) are generally used to deal with the single
objective problems. For example, Liaw (2003) proposed
a tabu search approach together with the optimal timing algorithm for solving
the Open Shop Scheduling problem (OSSP). For the multiobjective problems, the
Strength Pareto Evolutionary algorithm (SPEA), the Pareto Archived Evolutionary
Strategy (PAES) and the nondominated sorting genetic algorithm II (NSGAII)
(Deb et al., 2002) are widely used. For example,
Moradi et al. (2011) used NSGAII and Nonranking
Genetic Algorithm (NRGA) for solving the Flexible Jobshop Scheduling Problem
(FJSP). Although, most of these multiobjective optimisation approaches have
been successfully used in realworld problems, one aspect that is often disregarded
in the current research is the decision making process (Fernandez
et al., 2010). The multiobjective optimisation approaches always
generate an approximation of the Pareto frontier, but getting this set does
not completely solve the problem. A best compromise solution still must be chosen
out of that set (Fernandez et al., 2011). That
is to say, both the multiobjective optimisation algorithms (search process)
and the decision maker’s preferences (decision making process) should be
considered to solve a multiobjective optimisation problem thoroughly. The combination
of these two processes can be classified into three categories (Coello
et al., 2007): the a priori, the progressive and the a posteriori
decision.
In the a priori decision, the decisionmaker (DM) is consulted before starting
the search process. The DM’s
preferences guide the search until the algorithm converges to a single point
which may result in a halfbaked search. The progressive decision is an interactive
method. In the progressive decision, the DM participates in the course of an
iterative optimisation process, gives information about the preferences to guide
the search until the DM is satisfied with the current solution. In this process,
the DM should always be present, which is not convenient. In the a posteriori
decision, a multiobjective optimisation algorithm is usually used to obtain
a set of compromise solutions. Then, the DM is asked to choose the final solution.
The search process and the decision making process are separated and the alteration
of one process will not influence the other process. The a posteriori decision
is used in this paper because of its flexibility.
A multicriteria decision mechanism called the chaotic nondominated sorting
genetic algorithm plus analytic hierarchy process (CNSGAAHP) is proposed to
solve the ATSP. As mentioned above, the multicriteria decision mechanism CNSGAAHP
is made up of two parts: the multiobjective optimisation algorithm CNSGA and
the decision making method AHP (Saaty, 1980). CNSGA incorporates
chaotic sequences based on the logistic map into NSGAII. NSGAII is a typical
representative of the multiobjective optimisation algorithms, which is effective
and can maintain a better spread of solutions. Xu et
al. (2006) used NSGAII in the design of standalone hybrid wind/photovoltaic
power systems. Chaos has some special characteristics such as the ergodic property
and the stochastic and is highly sensitive to initial conditions. Because of
these properties, optimisation algorithms based on chaos is presented to avoid
becoming trapped in local optima (Li and Wang, 2011;
Ren and Zhong, 2011). Thus, CNSGA can achieve better
results. AHP is extensively adopted in multicriteria decision making (MCDM)
and has successfully been applied to the ranking process of decision making
problems (Saaty, 1996). Barker and
Zabinsky (2011) used AHP for reverse logistics and Okeola
and Sule (2012) applied AHP to study the urban water supply scheme. AHP
has the following advantages (Duran and Aguilo, 2008),
(1) it is the only known MCDM model that can measure the consistency in the
decision maker’s judgments, (2) it helps dissect the problem and structure
it into a rational decision hierarchy, which makes the decision process easy
to handle, (3) DMs can derive weights of criteria and scores of alternatives
from comparison matrices by pairwise comparisons instead of quantify weights/scores
directly, (4) it can hybridise with other techniques to handle more difficult
problems, (5) it is easier to understand and can effectively handle both qualitative
and quantitative data. However, in many practical situations, DMs may have some
uncertain information and cannot assign exact numerical values to the comparison
judgments. Then, some researches applied fuzzy AHP as an extension of conventional
AHP to handle uncertainty. For example, Duran (2011)
proposed a fuzzybased AHP for comparative evaluation of a number of Computerised
Maintenance Management Systems (CMMS) alternatives, Wang
et al. (2011) presented an intuitionistic fuzzy AHP approach and
Pan (2012) proposed an evaluation method for Smart Logistics
based on benchmarking analysis and fuzzy AHP method.
Other researches considered the improvement of consistency check and the scale
measurement. In CNSGAAHP, the decision information can be quantified and the
above issues are actually a matter of indifference. That is to say, the uncertainty
can be handled, the consistency check can be passed easily and the scale measurement
can be more exact. CNSGAAHP is thus a suitable multicriteria decision mechanism
for the ATSP.
PROBLEM FORMULATION
The ATSP is to assign the execution of n tasks on m instruments. In this problem,
there are a set of tasks
and a set of instruments
(Xia et al., 2007b). The notifications
are used to present the test time, the test start time and the test completion
time of task t_{j} tested on r_{i}, respectively. A variable
is defined to express whether the task t_{j} occupies the instrument
r_{i}. Its definition is as follows:
Generally speaking, a task occupies more than one instrument.
In typical cases, some instruments could have redundancies, which make it possible
for a task to choose the instruments. The alternative schemes for t_{j }is
expressed as
where k_{j} is the number of schemes of t_{j}. The numbers of
schemes that correspond to every task can make up a set .
is represented as
and u_{jk} is the number of instruments for .
If ,
t_{j} and t_{j*} have resource conflicts.
is the test time of t_{j} for .
In addition, hypotheses considered in this paper are the following (Xia
et al., 2007b):
• 
All tasks and instruments are available at time 0 
• 
At a given time, an instrument can execute only one task 
• 
Each task must be completed without interruption once it starts 
• 
Assume
and
to simplify the problem 
In this study, there are two objectives should be minimised: the maximal test
completion time (makespan) f_{1}(x) and the mean workload of the instruments
f_{2}(x).
The definition of f_{1}(x) is:
where,
is the test completion time of t_{j} for
and meets the equation:
The definition of f_{2}(x) is:
where, Q is the parallel steps and its initial value is 1. Assign the instruments
for all of the tasks, if ,
Q = Q+1.
MULTICRITERIA DECISION MECHANISM CNSGAAHP FOR THE ATSP
In CNSGAAHP, multiobjective optimisation methods CNSGA can provide valuable
tradeoff information among the conflict objectives and multicriteria decision
making approach AHP helps DMs choose the most desirable and satisfactory alternative.
Before explaining the details of CNSGAAHP, some concepts of Multiobjective
Optimisation Problem (MOP) and multicriteria decision making should be introduced
briefly.
Multiobjective optimisation problem: A multiobjective optimisation problem
can be described, without loss of generality, as follows (Zhang
and Li, 2007):
where, Ω is the decision space and the function F means a mapping from
Ω to R^{M}. R^{M} is the objective space, with M objective
functions.
Multicriteria decision making: In MCDM, there are a number of options
called alternatives and an ultimate goal. The DMs should choose from the alternatives
to reach the goal according to some problembased evaluation criteria. These
criteria make different contribution to the goal and have different importance.
DMs try to compare the effects of alternatives and achieve best quality of the
final result.
CNSGA
Chaotic sequence: A chaotic sequence is generated by a chaotic map which
is an evolution function that exhibits some sort of chaotic behaviour. The logistic
map is a wellknown onedimensional chaotic map and its definition is as follows:
where, λ_{t} is the value of the chaotic variable λ at the
tth iteration and μ is the socalled bifurcation parameter of the system
(μ∈[0, 4]) (Hong et al., 2011). In
this study, μ = 4, then λ_{0.}∉{0.25, 0.5, 0.75}.
Implementation of CNSGA: The main procedure of CNSGA is similar with
NSGAII, but some details are modified by chaos:
• 
The main loop of CNSGA begins with the combination of the
current and previous populations and the calculation of the nondominated
fronts. Once all the Pareto fronts have been determined, the new population
is obtained. Finally, using this population, individuals are selected, crossed
and mutated to create a new population. This process is described in Fig.
1. 
• 
Problem encoding is a representation in a chromosome, which is relative
to the conditions of the problem being considered. Designing a suitable
encoding approach for the ATSP is very important. In this study, a new encoding
scheme, called the Integrated Encoding Scheme (IES), is proposed. 

Fig. 1: 
Main loop of CNSGA 

This encoding scheme can use only one chromosome to contain
the information about both the processing sequence of the tasks and the
occupancy of the instruments for each task. The main concept of the IES
is to use relationships between the decision variables to express the sequence
of tasks and the values of the variables to represent the occupancy of the
instruments for each task. Firstly, the decision variables are sorted in
ascending order and the rank of every variable denotes a test task index
in sequence. Then, the instrument assignment can also be obtained from the
decision variables according to the equation k = [x_{ij}x10]mod
k_{j}+1. Where, x_{ij} represents the decision variable
that corresponds to t_{j} and k_{j} is the number of schemes
of t_{j}. The IES never generates a duplication of a certain task,
can always get feasible instrument assignments, makes full use of decision
variables and improves the encoding efficiency: 
• 
The fitness function is used to measure the solutions. In
this paper, the makespan and the mean workload of the instruments are the
objectives. Their calculation is shown in Fig. 2. 
• 
The Simulated Binary Crossover (SBX) operator is used in CNSGA. P_{c}
is the crossover probability and η_{c} is the distribution
index for the crossover operator. 
• 
The polynomial mutation is applied with some modification. For a solution
x_{s}, the polynomial mutation is described as follows: 
where,
and
are the upper and lower bound of x_{s}, respectively.
where, ,
p_{m }is the mutation probability and η_{m} is the distribution
index for the mutation operator
AHP: It decomposes a complex issue into several levels, rigorously defines
the manager priorities and computes weights associated to the alternatives.
The output of AHP is a ranking indicating the overall preference for each decision
alternative. The main steps of AHP include:
• 
Step 1: Define the problem and determine its goal.
For the ATSP, this goal is to obtain a most satisfactory schedule 

Fig. 2: 
Calculation of the objective values 
Table 1: 
Pairwise comparison scale for AHP preferences (Saaty,
1980) 

• 
Step 2: Define the structure of the hierarchy of that
problem from the top goal through intermediate levels of criteria, subcriteria
and actors to the lowest level of alternatives. In this paper, the criteria
(C) are the makespan (C_{1}) and the mean workload of the instruments
(C_{2}) and the alternatives (A) are solutions obtained by CNSGA 
• 
Step 3: Construct a set of pairwise comparison matrices for each
lower level in a hierarchy and make all the pairwise comparisons by using
the relative scale measurement shown in Table 1. In our
work, f_{max} and f_{min} are the maximum and minimum of
the fitness function, respectively. The comparisons can be quantified as
follows: 
where, a_{ij} is an element of the pairwise comparison matrix, which
indicates the importance of ith factor over jth. f_{i} and f_{j}
are the fitness values of A_{i} and A_{j}.
Table 2: 
Average random consistency ratio (RI) (Saaty,
1980) 

• 
Step 4: Compute the consistency ratio (CR) for each
pairwise comparison matrix to measure the consistency of the subjective
ranking. Firstly, using the biggest eigenvalue λ_{max} of a
pairwise comparison matrix to calculate the consistency index (CI) by CI
= (λ_{max}n)/(n1), where n is the matrix size. The CR is
calculated by comparing the CI with a random index (RI), CR = CI/RI. RI
is the consistency index of a randomly generated pairwise comparison matrix
and its value depending on the matrix size is shown in Table
2. If CR≤0.10, the judgment matrix is acceptable. Otherwise it is
considered inconsistent and the matrix should be improved. 
• 
Step 5: Calculate the relative weights and determine the ranking
of the alternatives. The lambda max technique is commonly used, which defines
a vector of weights as the normalised eigenvector w corresponding to the
largest eigenvalue λ_{max}. If the combining vector of weights
of the (k1)th level W^{(k1)} and the vector of weights of the
kth level w^{k} is obtained, the combining vector of weights of
the kth level W^{k} can be calculated by W^{k} = w^{k}W^{(k1)},
k>1. 
RESULTS AND DISCUSSION
Experiments are designed to verify the effectiveness of CNSGAAHP. The applied
ATSP in Table 3 depends on a realworld instance that is abstracted
from a missile system. There are 20 tasks to be tested and 8 instruments can
be used. It was solved by CNSGA. The parameter settings of CNSGA are shown in
Table 4 and the obtained compromise solutions are shown in
Fig. 3. The objective values of these compromise solutions
are [(39, 14.357), (34, 19.546), (45, 14.286), (52, 13.667), (38, 15.539), (32,
20.000), (33, 19.636), (35, 18.182), (59, 13.533), (65, 12.813)].
Then, AHP is applied to make the final decision. The structure of AHP is shown
in Fig. 4.
Firstly, the pairwise comparison matrix for criteria with respect to goal was
constructed in Table 5. Generally speaking, for the ATSP,
makespan is more important than the mean workload of the instruments. Thus,
the rating 5 was considered.
Table 3: 
A realworld ATSP with 20 tasks and 8 instruments 


Fig. 3: 
Comparison solutions obtained by CNSGA 

Fig. 4: 
Structure of the AHP 
For matrix GoalC, the biggest eigenvalue λ_{max} = 2 and the
CI = 0. Therefore, the judgment matrix was acceptable. The vector of weights
W^{2} = w^{2} = (0.833, 0.167)^{T}.
Table 4: 
The parameter settings of CNSGA 

Table 5: 
Pairwise comparison matrix GoalC 

Table 6: 
Pairwise comparison matrix C_{1}A 

Table 7: 
Pairwise comparison matrix C_{2}A 

Secondly, the pairwise comparison matrix for alternatives with respect to the
criterion was created according to the Eq. 9. Both the makespan
(C_{1}) and the mean workload of the instruments (C_{2}) are
considered and the pairwise comparison matrices are shown in Table
6 and 7.
For matrix C_{1}A, the biggest eigenvalue λ_{max} = 10.338,
the CI = 0.038 and CR = 0.025<0.10. Therefore, the judgment matrix was acceptable.
The vector of weights corresponding to C_{1} was:
For matrix C_{2}A, the biggest eigenvalue λ_{max} = 10.404,
the CI = 0.045 and CR = 0.030<0.10. Therefore, the judgment matrix was acceptable.
The vector of weights corresponding to C_{2} was:
Thus, the vector of weights of the third level was:
The combining vector of weights was:
The ranking of all the alternatives were 6, 3, 7, 8, 5, 1, 2, 4, 10 and 9.
Therefore, the most satisfactory solution was (32, 20.000). Because the makespan
is more important, the ranking of the alternatives is almost corresponding to
the ranking of the makespan. Only the solution (65, 12.813) was reverse due
to its lowest mean workload.
The above experiments show that CNSGAAHP is very effective and suitable for
the ATSP. It can generate a set of compromise solutions and then choose a most
satisfactory solution from them scientifically.
CONCLUSIONS
This study proposes a multicriteria decision mechanism CNSGAAHP for the automatic
test task scheduling problem. In CNSGAAHP, the multiobjective optimisation
algorithm CNSGA is used to generate a set of compromise solutions. It incorporates
chaotic sequences based on the logistic map into NSGAII to avoid becoming trapped
in local optima and thus achieve better solutions. On the other hand, the widely
applied decision making method AHP is used to choose a most satisfactory schedule
from the solutions obtained by CNSGA. CNSGAAHP is a novel and integrated method
combined the search process and the decision making process flexible. It can
handle uncertainty, make the consistency check easily to pass and reduce the
workload of DMs. Experiment results show that CNSGAAHP is very concise and
suitable for the ATSP.
ACKNOWLEDGMENTS
This research is supported by the Natural Science Foundation of China under
Grant No.61101153 and the National 863 HiTech R and D Plan under Grant 2011AA110101.

REFERENCES 
1: Anderson, Jr. J.L., 2003. High performance missile testing (next generation test systems). Proceedings of the IEEE Systems Readiness Technology Conference, September 2225, 2003, Anaheim, CA., USA., pp: 1927 CrossRef 
2: Barker, T.J. and Z.B. Zabinsky, 2011. A multicriteria decision making model for reverse logistics using analytical hierarchy process. Omega, 39: 558573. CrossRef 
3: Coello, C.A.C., G.B. Lamont and D.A. Van Veldhuizen, 2007. Evolutionary Algorithms for Solving MultiObjective Problems. 2nd Edn., Springer, New York, USA., ISBN13: 9780387332543, Pages: 800
4: Curry, P.A., J. Burden and G.A. Lundy, 2006. Next Generation Automatic Test System (NGATS) update. Proceedings of the IEEE AUTOTESTCON, September 1821, 2006, Anaheim, CA., USA., pp: 318322 CrossRef 
5: Duran, O. and J. Aguilo, 2008. Computeraided machinetool selection based on a FuzzyAHP approach. Expert Syst. Appl., 34: 17871794. CrossRef 
6: Duran, O., 2011. Computeraided maintenance management systems selection based on a fuzzy AHP approach. Adv. Eng. Software, 42: 821829. CrossRef  Direct Link 
7: Fernandez, E., E. Lopez, S. Bernal, C.A.C. Coello and J. Navarro, 2010. Evolutionary multiobjective optimization using an outrankingbased dominance generalization. Comput. Oper. Res., 37: 390395. CrossRef 
8: Fernandez, E., E. Lopez, F. Lopez and C.A.C. Coello, 2011. Increasing selective pressure towards the best compromise in evolutionary multiobjective optimization: The extended NOSGA method. Inform. Sci., 181: 4456. CrossRef 
9: Hong, W.C., Y.C. Dong, L.Y. Chen and S.Y. Wei, 2011. SVR with hybrid chaotic genetic algorithms for tourism demand forecasting. Applied Soft Comput., 11: 18811890. CrossRef  Direct Link 
10: Li, Z.Y. and X. Wang, 2011. Chaotic differential evolution algorithm for solving constrained optimization problems. Inform. Technol. J., 10: 23782384. CrossRef  Direct Link 
11: Liaw, C.F., 2003. An efficient tabu search approach for the twomachine preemptive open shop scheduling problem. Comput. Oper. Res., 30: 20812095. CrossRef 
12: Moradi, E., S.M.T.F. Ghomi and M. Zandieh, 2011. Biobjective optimization research on integrated fixed time interval preventive maintenance and production for scheduling flexible jobshop problem. Expert Syst. Appl., 38: 71697178. CrossRef 
13: Okeola, O.G. and B.F. Sule, 2012. Evaluation of management alternatives for urban water supply system using multicriteria decision analysis. J. King Saud Univ. Eng. Sci., 24: 1924. CrossRef 
14: Pan, T.J., 2012. Value chain analysis method of smart logistics using fuzzy theory. Inform. Technol. J., 11: 441445. CrossRef  Direct Link 
15: Ren, B. and W. Zhong, 2011. Multi objective optimization using chaos based PSO. Inform. Technol. J., 10: 19081916. CrossRef 
16: Saaty, T.L., 1980. The Analytic Hierarchy Process: Planning, Priority Setting, Resource Allocation. McGraw Hill, New York
17: Saaty, T.L., 1996. Multicriteria Decision Making: The Analytic Hierarchy Process. RWS Publications, Pittsburgh, PA., USA., ISBN13: 9780962031717, Pages: 479
18: Wang, H., G. Qian and X. Feng, 2011. An intuitionistic fuzzy AHP based on synthesis of eigenvectors and its application. Inform. Technol. J., 10: 18501866. CrossRef  Direct Link 
19: Xia, R., M.Q. Xiao and J.J. Cheng, 2007. Parallel TPS design and application based on software architecture, components and patterns. Proceedings of the IEEE AUTOTESTCON, September 1720, 2007, Baltimore, MA., USA., pp: 234240 CrossRef 
20: Xia, R., M.Q. Xiao, J.J. Cheng and X.H. Fu, 2007. Optimizing the multiUUT parallel test task scheduling based on multiobjective GASA. Proceedings of the 8th International Conference on Electronic Measurement and Instruments. July 18August 16, 2007, Xi'an, China, pp: 48394844 CrossRef 
21: Xu, D., L. Kang and B. Cao, 2006. The elitist nondominated sorting GA for multiobjective optimization of standalone hybrid wind/PV power systems. J. Applied Sci., 6: 20002005. CrossRef  Direct Link 
22: Zhang, Q. and H. Li, 2007. MOEA/D: A multiobjective evolutionary algorithm based on decomposition. IEEE Trans. Evol. Comput., 11: 712731. CrossRef 
23: Zhou, D.X., P. Qi and T. Liu, 2009. An optimizing algorithm for resources allocation in parallel test. Proceedings of the IEEE International Conference on Control and Automation, December 911, 2009, Christchurch, New Zealand, pp: 19972002 CrossRef 
24: Deb, K., A. Pratap, S. Agarwal and T. Meyarivan, 2002. A fast and elitist multiobjective genetic algorithm: NSGAII. IEEE Trans. Evol. Comput., 6: 182197. CrossRef  Direct Link 



