Scheduling Optimization of Test Tasks Based on Ant Colony Algorithm

HU Tao;MA Chenhui;SHEN Liqun;LIANG Jie

CN Submission Journal Articles Figures Search
Adv. Search

  • Sponsored by: China Association for Science and Technology (CAST)

    Editor-In-Chief: Xu Yida

    ISSN 1000-1093

    　

  • Hosted By: China Ordnance Society

    Published By: Acta Armamentarii

    CN 11-2176/TJ

Acta Armamentarii, a Chinese monthly journal, was first published in 1979. The journal is supervised by China Association for Science and Technology, sponsored by China Ordnance Society，and edited and published by Editorial Board of Acta Armamentarii. The Journal is included in all important domestic databases，and also collected by Engineering Index (EI, USA), Chemical Abstracts (CA, USA), Science Abstracts (SA, UK）, Abstract Journal (AJ, Russia), and Current Bibliography on Science and Technology(CBST).Acta Armamentarii has been selected into the journal Of Ordnance Science and Technology (Weapons Industry) Field Of High Quality Scientific and Technological Periodical Classification Catalogue (2022 edition), ranking T1, and the journal of Automotive Engineering Field of High Quality Scientific and technological Periodical classification Catalogue, ranking T2.
Acta Armamentarii ›› 2019, Vol. 40 ›› Issue (6) : 1310-1316. DOI: 10.3969/j.issn.1000-1093.2019.06.023
Research Notes

Scheduling Optimization of Test Tasks Based on Ant Colony Algorithm

  • HU Tao1, MA Chenhui2, SHEN Liqun1, LIANG Jie1
Author information +
History +

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 obtainedaccording 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 improvethe test efficiency by 43.07% compared with the semi-serial test, and the balance degree ofresources in the task scheduling sequence with the shortest test time is the highest. Key

Key words

taskscheduling / paralleltest / antcolonyalgorithm / resourcebalancedegree

Cite this article

EndNote

Ris (Procite)

Bibtex

Download Citations
HU Tao, MA Chenhui, SHEN Liqun, LIANG Jie. Scheduling Optimization of Test Tasks Based on Ant Colony Algorithm. Acta Armamentarii. 2019, 40(6): 1310-1316 https://doi.org/10.3969/j.issn.1000-1093.2019.06.023

References



［1］FANGJ 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］LIANGX, 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］BAZOOBANDIH 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］CARNEIROM 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］MNCHL, 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］YOUW, 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］CHENL, 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

Accesses

Citation

Detail
Sections
Recommended

/

〈 〉