Jia-yong FANG（方甲永）, Hui-hui XUE（薛辉辉）, Ming-qing XIAO（肖明清）
(Engineering College, Air Force Engineering University, Xi’an 710038, China)
Abstract-A Genetic Algorithm-Ant Colony Algorithm (GA-ACA), which can be used to optimize multi-Unit Under Test(UUT) parallel test tasks sequences and resources configuration quickly and accurately, is proposed in the paper. With the establishment of the mathematic model of multi-UUT parallel test tasks and resources, the condition of multi-UUT resources mergence is analyzed to obtain minimum resource requirement under minimum test time. The definition of cost efficiency is put forward, followed by the design of gene coding and path selection project， which can satisfy multi-UUT parallel test tasks scheduling. At the threshold of the algorithm, GA is adopted to provide initial pheromone for ACA, and then dual-convergence pheromone feedback mode is applied in ACA to avoid local optimization and parameters dependence. The practical application proves that the algorithm has a remarkable effect on solving the problems of multi-UUT parallel test tasks scheduling and resources configuration.
Key words-parallel test; Genetic Algorithm-Ant Colony Algorithm (GA-ACA); cost efficiency, multi-Unit Under Test(UUT); resources configuration; tasks scheduling
Manuscript Number: 1674-8042(2011)04-0321-06
doi: 10.3969/j.issn.1674-8042.2011.04.004
References
[1] Bill, Rose. NxTest: DoD’s next step in automatic testing. 2005-02-25. http://www.acq.osd.mil.
[2] Jin-song Yu, Xing-shan Li, 2005. Architecture and key Technologies of next generation automatic test system. Computer Measurement & Control, 13(1): 1-3.
[3] Rui Xia, 2005. Research on development methodology of the parallel automatic test systems. Xi'an: Air Force Engineering University.
[4] Yu Hu, 2003. Red petri net based modeling of parallel automatic test systems. Chengdu: University of Electronic Science and Technology of China.
[5] Rui Xia, Ming-qing Xiao, Jin-jun Cheng, 2007. Optimization for the parallel test task scheduling based on hybrid GASA. Journal of System Simulation，19(15): 3564-3567.
[6] Min Ma, Guang-ju Chen, Dong-yi Chen, 2007. Research on parallel test based on Petri net and GASA algorithm. Chinese Journal of Scientific Instrument, 28(2): 331-336.
[7] M.Dorigo, 1992. Optimization, learning and natural algorithm. PhD thesis Department of Electronic, Politecnico of Milano, Italy.
[8] M.Dorigo, G.D.Caro, 1999. Ant colony optimization: a new meta-heuristic. Proc of the 1999 Congress on Evolutionary Computation, Washington: IEEE Press, (2): 1470-1477.
[9] Hai-bin Duan, 2005. Principles and applications of ant colony algorithm. Beijing: Science Press.
[10] Z.H. Xiong, S.K. Li, J.H. Chen. Hardware/software partitioning based on dynamic combination of genetic algorithm and ant algorithm. J. of Software (1000-9825), 16(4): 503-512.
[11] C.Blum, 2005. Beam-ACO—Hybridizing ant colony optimization with beam search: an application to open shop scheduling. Computers & Operations Research (0305-0548), 32(6): 1565-1591.
[12] M.Dorigo, M.Birattari, T.Stützle, 2006. Ant colony optimization-artificial ants as a computational intelligence technique. IEEE Computational Intelligence Magazine(1556-603X), 1(4): 28-39.
[13] Jiao-feng Wu, 2007. Research on improved performance of ant colony algorithm by genetic algorithm. Taiyuan: Taiyuan University of Technology.
[full text view]
