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