现有算法处理强约束关系的并行测试任务调度问题具有运算时间长、寻优概率低、收敛性差等缺陷,针对这些问题提出了一种基于图禁忌的调度算法。该算法从测试任务间的约束关系入手,利用图论建立测试任务间的关系图,并结合禁忌算法实现并行测试任务的多目标优化调度。算法中将强约束关系的测试任务调度问题与无约束关系的资源配置问题进行分离,提高了算法的寻优速度。通过仿真实例证明了算法的有效性,与现有并行测试任务调度算法相比,运算时间减少96%、寻优率提高了36.5%,并且具有更好的收敛性。
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.
[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