基于图禁忌的并行测试任务调度算法

doi:CNKI:11-1929/V.20110324.1152.005

电子与自动控制

本期目录 | 过刊浏览 | 高级检索

前一篇 | 后一篇

基于图禁忌的并行测试任务调度算法

路辉, 陈晓, 刘欣, 邓小乐

北京航空航天大学电子信息与工程学院, 北京 100191

收稿日期:2010-11-23 修回日期:2010-12-27 出版日期:2011-09-25 发布日期:2011-09-16
通讯作者: 路辉(1977-) 女,博士后,副教授。主要研究方向:自动测试系统、故障诊断。 Tel: 010-82316487 E-mail: mluhui@163.com E-mail:mluhui@163.com
基金资助:
"十一五"国防预研项目 (B0520060455)

A Graph Tabu Algorithm for Parallel Test Task Scheduling

LU Hui, CHEN Xiao, LIU Xin, DENG Xiaole

School of Electronics and Information Engineering, Beihang University, Beijing 100191, China

Received:2010-11-23 Revised:2010-12-27 Online:2011-09-25 Published:2011-09-16

摘要/Abstract

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

关键词: 图论, 禁忌搜索, 并行测试, 任务调度, 强约束关系

Abstract: 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.

Key words: graph theory, tabu search, parallel test, task scheduling, strong constraint

中图分类号:

V243
TP202

路辉, 陈晓, 刘欣, 邓小乐. 基于图禁忌的并行测试任务调度算法[J]. 航空学报, 2011, 32(9): 1669-1677.

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.

参考文献

[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)

E-mail：hkxb@buaa.edu.cn

关于我们

期刊社服务

专业学科

封面文章

友情链接

主管单位：中国科学技术协会主办单位：中国航空学会北京航空航天大学

基于图禁忌的并行测试任务调度算法

A Graph Tabu Algorithm for Parallel Test Task Scheduling

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 11

编辑推荐

Metrics

本文评价

[1]	赵长啸, 戴骏, 董方正, 李道俊. 机载时间敏感网络链路安全关键度均衡调度方法[J]. 航空学报, 2024, 45(6): 328870-328870.
[2]	杨盛庆, 吴敬玉, 朱文山, 钟超. 基于星间链路的星座相对构型保持方法[J]. 航空学报, 2023, 44(6): 326796-326796.
[3]	滕润航, 贺克伦, 赵甜, 於萧萧, 于喜奎, 徐向华, 梁新刚, 陈群. 飞行器能源与热管理系统中多能流统一建模与分析方法[J]. 航空学报, 2023, 44(19): 128427-128427.
[4]	雷刚, 罗炜, 李云舒, 赖灿辉. 高超声速滑翔飞行器多禁飞区再入机动航迹优化[J]. 航空学报, 2023, 44(15): 528769-528769.
[5]	王荣巍, 何锋, 周璇, 鲁俊, 李二帅. 面向无人机蜂群的航电云多层任务调度模型[J]. 航空学报, 2019, 40(11): 323183-323183.
[6]	丁达理;任波;黄长强;张得舒. 人在回路电视制导武器最佳投射域建模与仿真[J]. 航空学报, 2010, 31(5): 1054-1059.
[7]	钟波;孟晓风;王琳;王国华. 一种改进的GNS互连测试算法[J]. 航空学报, 2009, 30(4): 713-718.
[8]	付新滑;肖明清;刘万俊;周越文 . 一种新的并行测试任务调度算法[J]. 航空学报, 2009, 30(12): 2363-2370.
[9]	邱志平;张宇星. 智能优化算法在飞机总体设计中的应用[J]. 航空学报, 2009, 30(1): 62-67.
[10]	路辉;李昕. 一种基于分枝定界法的串行测试任务调度算法[J]. 航空学报, 2008, 29(1): 131-135.
[11]	陈志伟;高海龙;王智. 用图论方法分析马尔可夫频次阵特性[J]. 航空学报, 2003, 24(4): 328-331.