Scheduling Optimization of Test Tasks Based on Ant Colony Algorithm

doi:10.3969/j.issn.1000-1093.2019.06.023

Abstract

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

CLC Number:

TJ765.4⁺3

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.

References

［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]	GUO Wei， WU Kai， ZHOU Yue， SUN Hongming， XU Gaofei， GAO Sen. Path Planning of Deep-sea Landing Vehicle Based on Ant Colony Algorithm [J]. Acta Armamentarii, 2022, 43(6): 1387-1394.
[2]	ZHANG Jiawen， FANG Haolin， LI Jiawang. 3D Path Planning of Underactuated AUV Based on Complex Constraints [J]. Acta Armamentarii, 2022, 43(6): 1407-1414.
[3]	XU Yuxin, GU Chumei, CAO Jianjun, XU Jinyong, WEI Zhihu. Specific Emitter Identification of Twin Radiation Sources Based on Parallel Classifier Ensemble Learning Using Ant ColonyFeature Selection [J]. Acta Armamentarii, 2022, 43(12): 3132-3141.
[4]	L Guojun， CAO Jianjun， ZHENG Qibin， CHANG Chen， WENG Nianfeng， PENG Cong. Detection of Similar Duplicate Records Based on OCSVM and Multi-objective Ant Colony Optimization [J]. Acta Armamentarii, 2020, 41(2): 324-331.
[5]	YANG Shanchao， TIAN Kangsheng， LI Hongquan， ZHOU Guangtao， LIANG Futai. Comprehensive Priority-based Task Scheduling Algorithm for Anti-missile Early Warning Phased Array Radar [J]. Acta Armamentarii, 2020, 41(2): 315-323.
[6]	HAN Yuxing, DING Gangyi, CHAI Zuohong. Route Optimization Strategy of Military Cooperative Inspection [J]. Acta Armamentarii, 2019, 40(8): 1673-1679.
[7]	WANG Zheng-yuan, LIU Wei-dong, JING Hui-li, QU Na. An Optimization Solution to Armament Parallel Test Task Scheduling [J]. Acta Armamentarii, 2018, 39(2): 399-404.