This paper presents a graph tabu approach to deal with problems existing in present parallel test task scheduling approaches, such as long computation time, low probability optimization rate, premature convergence to local optima, etc. The approach in this paper starts with strong constraints among parallel test tasks, then uses the graph theory to establish a diagram of test tasks, and finally realizes multi-objective optimization of parallel test task scheduling by combining with a tabu search algorithm. This approach makes a separation between strong constraint test task scheduling and no constraint test resource scheduling, which improves the optimization speed. The experimental results show that the approach is feasible. Compared with the existing approaches, the proposed approach realizes a 96% reduction of computing time, 36.5% increment of the optimization rate, and better convergence.
LU Hui, CHEN Xiao, LIU Xin, DENG Xiaole
. A Graph Tabu Algorithm for Parallel Test Task Scheduling[J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2011
, 32(9)
: 1669
-1677
.
DOI: CNKI:11-1929/V.20110324.1152.005
[1] 孙宝江, 秦红磊, 胡文明, 等. 自动测试系统适配器自动设计技术[J]. 航空学报, 2007, 28(3): 703-707. Sun Baojiang, Qin Honglei, Hu Wenming, et al. Automatic design for general purpose test unit adapter of automatic test system[J]. Acta Aeronautica et Astrnautica Sinica, 2007, 28(3): 703-707. (in Chinese)
[2] 李昕, 沈士团, 路辉. 基于图染色理论的并行测试任务调度算法[J]. 北京航空航天大学学报, 2007, 33(9): 1068-1071. Li Xin, Shen Shituan, Lu Hui. Algorithms of tasks scheduling in parallel test based on graph coloring theory [J]. Journal of Beijing University of Aeronautics and Astronautics, 2007, 33(9): 1068-1071. (in Chinese)
[3] William A R. The impact of next generation test technology on aviation maintenance//AUTOTESTCON 2003. IEEE Systems Readiness Technology Conference Proceedings. Anaheim: IEEE Instrumentation and Measurement Society, 2003: 2-9.
[4] Anderson J L. High performance missile testing (next generation test systems) //IEEE Systems Readiness Technology Conference Proceedings. 2003: 19-27.
[5] 马敏, 陈光, 陈东义. 基于Petri网和模拟退火遗传算法的并行测试研究[J]. 仪器仪表学报, 2007, 28(2): 331-336. Ma Min, Chen Guangju, Chen Dongyi. Research on parallel test based on Petri net and GASA algorithm [J]. Chinese Journal of Scientific Instrument, 2007, 28(2): 331-336. (in Chinese)
[6] 胡瑜. 基于有色Petri网理论的并行自动测试系统建模研究. 成都: 电子科技大学自动化工程学院, 2003. Hu Yu. Colored Petri net based modeling of parallel automatic test systems . Chengdu: School of Automation, University of Electrical Science and Technology, 2003. (in Chinese)
[7] Nathan W. Parallel test description and analysis of parallel test system speedup through Amdahl's law [J]. IEEE AUTOTESTCON , 2007: 735-740.
[8] 夏锐, 肖明清, 程进军. 基于混合遗传退火算法的并行测试任务调度优化[J]. 系统仿真学报, 2007, 19(15): 3564-3567. Xia Rui, Xiao Mingqing, Cheng Jinjun. Optimization for the parallel test task scheduling based on hybrid GASA [J]. Journal of System Simulation, 2007, 19(15): 3564-3567. (in Chinese)
[9] 付新华, 肖明清, 夏锐. 基于蚁群算法的并行测试任务调度[J]. 系统仿真学报, 2008, 20(16): 4352-4356. Fu Xinhua, Xiao Mingqing, Xia Rui. Novel ant colony algorithm for parallel test task scheduling [J]. Journal of System Simulation, 2008, 20 (16): 4352-4356. (in Chinese)
[10] 付新华, 肖明清, 刘万俊, 等. 一种新的并行测试任务调度算法[J]. 航空学报, 2009, 30(12): 2363-2370. Fu Xinhua, Xiao Mingqing, Liu Wanjun, et al. A novel algorithm for parallel test task scheduling [J]. Acta Aeronautica et Astronautica Sinica, 2009, 30(12): 2363-2370. (in Chinese)
[11] 王伟斌, 秦红磊. 基于自然数编码遗传算法的并行测试技术[J]. 系统工程与电子技术, 2010, 32(6): 1343-1348. Wang Weibin, Qin Honglei. Parallel test using natural coding genetic algorithm[J]. System Engineering and Electronic System, 2010, 32(6), 1343-1348. (in Chinese)
[12] 卓家靖, 孟晨. 并行测试系统的任务分解和任务过程模型[J]. 电子测量技术, 2008, 31(8): 109-112. Zhuo Jiajing, Meng Chen. Task decomposition and task process models of parallel test system [J]. Electronic Measurement Technology, 2008, 31(8): 109-112. (in Chinese)
[13] 徐俊明. 图论及其应用[M]. 合肥: 中国科学技术大学出版社, 2004: 1-10. Xu Junming. Graph theory and its applications [M]. Hefei: Press of University of Science and Technology, 2004: 1-10. (in Chinese)
[14] Clover F. Tabu search—Part I [J]. ORSA Journal on Computing, 1989, 1(3): 190-206.
[15] Clover F. Tabu search—Part II [J]. ORSA Journal on Computing, 1990, 2(1): 4-32.
[16] 汪定伟, 王俊伟, 王洪峰, 等. 智能优化算法[M]. 北京:高等教育出版社, 2007: 70-78. Wang Dingwei, Wang Junwei, Wang Hongfeng, et al. Intelligent optimization methods[M]. Beijing: Higher Education Press, 2007: 70-78. (in Chinese)
CJA