基于蚁群算法的测试任务调度优化方法

doi:10.3969/j.issn.1000-1093.2019.06.023

摘要/Abstract

摘要： 复杂系统测试通常存在任务复杂、测试时间长、资源浪费等问题，对资源和任务进行合理调度具有重要实用价值。提出基于蚁群算法的测试任务并行任务调度优化方法，对测试问题进行描述，与蚁群算法结合，设计了启发函数、状态转移规则；根据算法流程获得测试时间最短的任务调度序列；针对任务序列多解的问题，提出资源均衡度的评价标准,得到最优的资源任务调度序列。基于蚁群算法解决了复杂测试系统任务调度问题，对某实际测试系统资源任务集进行调度仿真，并与随机穷举法对比验证算法的有效性，结果表明该方法能大大节约测试时间。测试实例与当前常用的半串行测试进行对比，测试效率提升了43.07%；所得结果为最短测试时间任务调度序列中资源均衡度最高的。

关键词: 任务调度, 并行测试, 蚁群算法, 资源均衡度

Abstract: The problems of complex tasks, long test time, and wasting of resources exist in the test of complex system. The reasonable scheduling of the resources and tasks is of great importance in real application. An optimization method for parallel task scheduling of test process based on ant colony algorithm is proposed. Considering ant colony algorithm, the heuristic function and state transition rule are designed to describe test problem. The task scheduling sequence with the shortest test time can be obtained according to the algorithm flow. To solve the multi solution problem of task sequence, an evaluation criterion based on resource balance degree is proposed to get the optimal task scheduling sequence. The task scheduling problem of complex system is solved by using the ant colony algorithm. A real test task was scheduled and simulated. Effectiveness of the proposed method is verified by comparing with the random exhaustive method. Results show that the proposed method can save test time greatly and improve the test efficiency by 43.07% compared with the semi-serial test, and the balance degree of resources in the task scheduling sequence with the shortest test time is the highest. Key

Key words: taskscheduling, paralleltest, antcolonyalgorithm, resourcebalancedegree

中图分类号:

TJ765.4⁺3

胡涛, 马晨辉, 申立群, 梁洁. 基于蚁群算法的测试任务调度优化方法[J]. 兵工学报, 2019, 40(6): 1310-1316.

HU Tao, MA Chenhui, SHEN Liqun, LIANG Jie. Scheduling Optimization of Test Tasks Based on Ant Colony Algorithm[J]. Acta Armamentarii, 2019, 40(6): 1310-1316.

参考文献

［1］ FANG J Y, XUE H H, XIAO M Q. Parallel test tasks scheduling and resources configuration based on GA-ACA［J］. Journal of Measurement Science and Instrumentation, 2011, 2(4): 321-326.
［2］ LIANG X, DONG B. Parallel test task scheduling of aircraft electrical system based on cost constraint matrix and ant colony algorithm［C］∥Proceedings of International Conference on Industrial Informatics. Beijing, China: IEEE, 2012: 178-183.
［3］王正元, 刘卫东, 景慧丽, 等. 一种并行测试任务调度优化方法［J］. 兵工学报, 2018, 39(2): 399-404.
WANG Z Y, LIU W D, JING H L, et al. An optimization solution to armament parallel test task scheduling［J］. Acta Armamentarii, 2018, 39(2):399-404.(in Chinese)

［4］熊婧. 基于改进蚁群算法的车间调度方法及实现［D］. 杭州：浙江工业大学, 2007.
XIONG J. The method to resolve job-shop scheduling problem based on improved ant colony algorithm［D］. Hangzhou：Zhejiang University of Technology, 2007.(in Chinese)
［5］付新华, 肖明清, 夏锐. 基于蚁群算法的并行测试任务调度［J］. 系统仿真学报, 2008, 20(16): 4352-4356.
FU X H, XIAO M Q, XIA R. Novel ant colony algorithm for parallel test task scheduling［J］. Journal of System Simulation, 2008, 20(16): 4352-4356. (in Chinese)

［6］路辉, 陈晓, 刘欣, 等. 基于图禁忌的并行测试任务调度算法［J］. 航空学报, 2011, 32(9): 1669-1677.
LU H, CHEN X, LIU X, et al. A graph tabu algorithm for parallel test task scheduling［J］. Acta Aeronautica et Astronautica Sinica, 2011, 32(9): 1669-1677. (in Chinese)

［7］ BAZOOBANDI H A, KHORASHAIZADEH M, EFTEKHARI M. Solving task scheduling problem in multi-processors with genetic algorithm and task duplication［C］∥Proceedings of 2014 Iranian Conference on Intelligent Systems. Bam, Brazil: IEEE, 2014:1-4.
［8］ CARNEIRO M G, OLIVEIRA G M B. SCAS-IS: knowledge extraction and reuse in multiprocessor task scheduling based on cellular automata［C］∥ Proceedings of 2012 Brazilian Symposium on Neural Networks. Curitiba, Paraná, Brazil: IEEE, 2012: 142-147.
［9］段海滨. 蚁群算法原理及其应用［M］. 北京：科学出版社, 2005.
DUAN H B. Ant colony optimization algorithm principles and applications［M］. Beijing: Science Press，2005. (in Chinese)

［10］宋代立, 张洁. 蚁群算法求解混合流水车间分批调度问题［J］. 计算机集成制造系统, 2013, 19(7): 1640-1647.
SONG D L, ZHANG J. Batch scheduling problem of hybrid flow shop based on ant colony algorithm［J］. Computer Integrated Manufacturing Systems, 2013，19(7): 1640-1647. (in Chinese)
［11］ MNCH L, SCHABACKER R, PABST D. Genetic algorithm based sub-problem solution procedures for a modified shifting bottleneck heuristic for complex job shops［J］. European Journal of Operational Research, 2007, 177(3): 2100-2118.
［12］ YOU W, TAO P, ZHOU C H, et al. ACOMCD: a multiple cluster detection algorithm based on the spatial scan statistic and ant colony optimization［J］. Journal of Graphics, 2012, 56(2):283-296.
［13］ CHEN L, ZHANG C F. Adaptive exchanging strategies in parallel ant colony algorithm［J］. Journal of Software, 2007, 18(3):617-624.
［14］曾梦凡, 陈思洋, 张文茜, 等. 利用蚁群算法生成覆盖表: 探索与挖掘［J］. 软件学报, 2016, 27(4): 855-878.
ZHENG M F, CHEN S Y, ZHANG W Q, et al. Generating covering arrays using ant colony optimization: exploration and mining［J］. Journal of Software, 2016, 27(4): 855-878. (in Chinese)
［15］曹明. 智能算法及其在信息安全若干关键问题中的应用与研究［D］. 北京北京邮电大学, 2008.
CAO M. Researches on the application of intelligent algorithms in some key issues of cryptography and information security［D］. Beijing: Beijing University of Posts and Telecommunications, 2008. (in Chinese)
［16］王鹏,黄焱,李坤,等.云计算集群相空间负载均衡度优先调度算法研究［J］.计算机研究与发展, 2014, 51(5): 1095-1107.
WANG P, HUANG Y, LI K, et al. Load balancing degree first algorithm on phase space for cloud computing cluster［J］. Journal of Computer Research and Development, 2014, 51(5): 1095-1107. (in Chinese)
［17］梁洁. 基于Petri网的导弹测试系统仿真验证技术研究［D］.哈尔滨：哈尔滨工业大学,2017.
LIANG J. Research on simulation and verification technology of missile test system using petri net［D］. Harbin：Harbin Institute of Technology, 2017. (in Chinese)

第40卷第6期
2019 年6月兵工学报ACTA
ARMAMENTARIIVol.40No.6Jun.2019

[1]	张渊博, 项昌乐, 王伟达, 陈泳丹. 基于粒子群优化-蚁群融合算法的分布式电驱动车辆模型预测转矩协调控制策略[J]. 兵工学报, 2023, 44(11): 3253-3258.
[2]	周球, 周悦, 孙洪鸣, 郭威, 吴凯, 兰彦军. 深海着陆车路径规划及跟踪控制方法[J]. 兵工学报, 2023, 44(1): 298-306.
[3]	胡致远，王征，杨洋，尹洋. 基于人工鱼群-蚁群算法的UUV三维全局路径规划[J]. 兵工学报, 2022, 43(7): 1676-1684.
[4]	郭威，吴凯，周悦，孙洪鸣，徐高飞，高森. 基于蚁群算法的深海着陆车路径规划[J]. 兵工学报, 2022, 43(6): 1387-1394.
[5]	张家闻，房浩霖，李家旺. 基于复杂约束条件的欠驱动AUV三维路径规划[J]. 兵工学报, 2022, 43(6): 1407-1414.
[6]	徐雨芯，顾楚梅，曹建军，许金勇，魏志虎. 基于蚁群特征选择并行分类集成学习的孪生辐射源个体识别[J]. 兵工学报, 2022, 43(12): 3132-3141.
[7]	吕国俊，曹建军，郑奇斌，常宸，翁年凤，彭琮. 基于多目标蚁群优化的单类支持向量机相似重复记录检测[J]. 兵工学报, 2020, 41(2): 324-331.
[8]	杨善超，田康生，李宏权，周广涛，梁复台. 综合优先级下反导预警相控阵雷达任务调度算法[J]. 兵工学报, 2020, 41(2): 315-323.
[9]	韩宇星，丁刚毅，柴作鸿. 军事协同巡检路线优化策略[J]. 兵工学报, 2019, 40(8): 1673-1679.
[10]	王正元, 刘卫东, 景慧丽, 屈娜. 一种并行测试任务调度优化方法[J]. 兵工学报, 2018, 39(2): 399-404.
[11]	郑玉军，田康生，张金林，刘俊凯. 基于模糊神经网络的相控阵雷达任务调度设计[J]. 兵工学报, 2016, 37(11): 2010-2014.