计算机应用 ›› 2015, Vol. 35 ›› Issue (5): 1280-1283.DOI: 10.11772/j.issn.1001-9081.2015.05.1280

• 先进计算 • 上一篇    下一篇

基于图染色理论和遗传蜂群算法的并行测试任务调度

吴勇1, 王雪1, 赵焕义2   

  1. 1. 西北工业大学 电子信息学院, 西安 710072;
    2. 中国航空工业集团公司 江西洪都航空工业集团有限责任公司, 南昌 330024
  • 收稿日期:2014-12-03 修回日期:2015-01-05 出版日期:2015-05-10 发布日期:2015-05-14
  • 通讯作者: 王雪
  • 作者简介:吴勇(1964-),男,江苏武进人,教授,主要研究方向:航空电子综合系统、复杂系统、先进火控理论; 王雪 (1991-),女,河南新乡人,硕士研究生,主要研究方向:航空电子综合化系统、先进火控理论; 赵焕义(1978-),男,山东龙口人,高级工程师,主要研究方向:航空电子综合系统、复杂系统建模、先进火控理论.
  • 基金资助:

    航空科学基金资助项目(20125553032,20135153031,20135553035).

Parallel test task scheduling based on graph coloring theory and genetic-bee colony algorithm

WU Yong1, WANG Xue1, ZHAO Huanyi2   

  1. 1. School of Electronics and Information, Northwestern Polytechnical University, Xi'an Shaanxi 710072, China;
    2. Jiangxi Hongdu Aviation Industry Group Corporation Limited, Aviation Industry Corporation of China, Nanchang Jiangxi 330024, China
  • Received:2014-12-03 Revised:2015-01-05 Online:2015-05-10 Published:2015-05-14

摘要:

针对并行测试中任务优化调度这一关键性问题,提出了一种图染色理论和遗传蜂群算法相结合的任务调度优化算法.首先,建立了基于图染色理论的并行测试任务关系模型,用图来描述测试任务占用仪器资源的情况;然后, 在测试任务关系模型的基础上,将遗传算法特有的交叉、变异操作与人工蜂群(ABC)算法相结合搜索最优解,能够有效避免算法早熟并且加速算法收敛;最终得到并行度最大的任务分组方案.经仿真验证,所提方法能有效地实现并行测试,提高自动测试系统的测试效率.

关键词: 并行测试, 遗传蜂群算法, 图染色理论, 自动测试系统, 任务调度

Abstract:

For the question of parallel test task scheduling, an innovative solution based on graph coloring theory and genetic-bee colony algorithm was proposed. Firstly, a relation model of test tasks was established based on graph coloring theory, in which the occupation of device resource by test task could be represented by graph. Based on this relation model of test task, the optimum solution was searched via combining the artificial bee colony algorithm and the crossover operation and mutation operation which are unique in genetic algorithm to avoid the prematurity of the algorithm as well as accelerate convergence. Eventually, a grouping scheme was generated with maximized parallelism degree. Verified by the simulation, the proposed method can effectively realize the parallel test, improve the test efficiency of automatic test system.

Key words: parallel testing, Genetic-Bee colony Algorithm (GA-ABC), graph coloring theory, automatic test system, task scheduling

中图分类号: