一种并行测试任务调度优化方法

doi:10.3969/j.issn.1000-1093.2018.02.024

摘要/Abstract

摘要： 装备并行测试任务调度问题是一种较为复杂的组合优化问题，难以高效求解。对此，建立了装备并行测试任务调度问题数学模型。根据问题特点分解为并行线上装备测试任务分配问题和单流水线上装备测试任务调度问题，降低了原问题求解难度，并提出了求解方法。进一步使用单一流水线上装备测试任务调度问题的下界，有效地减少了问题求解计算量。实验结果表明，提出的装备并行测试任务调度优化方法是解决这种问题的有效方法。

关键词: 组合优化, 任务调度, 装备测试, 启发式

Abstract: Armament parallel test task scheduling is a complicated combinatorial optimization problem which is difficult to solve efficiently. An optimization model is proposed for a parallel task scheduling problem of armament test. Parallel task scheduling problem of armament is decomposed into the armament test task allocation on assembly lines and the task scheduling problem of armament test on single assembly line on the basis of the problem’s characteristics. It has reduced the difficulty in solving the original problem. The solutions to these sub-problems are proposed, respectively. A lower bound to the task scheduling problem of armament test on single assembly line is constructed, which results in great decrease in computation of two sub-problems. Experimental results show that the solution to parallel task scheduling problem of armament test proposed here is valid.Key

Key words: combinatorialoptimization, paralleltaskscheduling, armamenttest, heuristic

中图分类号:

TJ760.6⁺1

王正元, 刘卫东, 景慧丽, 屈娜. 一种并行测试任务调度优化方法[J]. 兵工学报, 2018, 39(2): 399-404.

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.

参考文献

［1］毕义明, 杨宝珍, 杨萍,等. 导弹批量测试仿真研究［J］. 火力与指挥控制, 2003, 28(5): 98-100.
BI Yi-ming, YANG Bao-zhen, YANG Ping, et al. Simulation study on missile batch testing problem［J］. Fire Control & Command Control, 2003, 28(5): 98-100.(in Chinese)
［2］赵鑫, 肖明清, 夏锐. 基于综合优先级的并行测试调度算法设计及实现［J］. 计算机测量与控制, 2007, 15(4): 423-425.
ZHAO Xin, XIAO Ming-qing, XIA Rui. Parallel test scheduling algorithm based on integrated priority and its implementation［J］. Computer Measurement & Control, 2007, 15(4): 423-425.(in Chinese)
［3］丁超，唐力伟，邓士杰. 基于动态优先级的测试任务抢占调度算法［J］. 系统工程与电子技术, 2016, 38(9): 2080-2085.
DING Chao, TANG Li-wei, DENG Shi-jie. Test task preemptive scheduling algorithm based on dynamic priority［J］. System Engineering and Electronics, 2016, 38(9): 2080-2085.(in Chinese)
［4］周强,司丰炜, 修言彬. Petri网结合Dijkstra算法的并行测试任务调度方法研究［J］. 电子测量与仪器学报, 2015 (6):920-927.
ZHOU Qiang, SI Feng-wei, XIU Yan-bin. Research on the parallel test task scheduling method with Petri nets and Dijkstra algorithm［J］. Journal of Electronic Measurement and Instrumentation, 2015(6):920-927.(in Chinese)
［5］胡海生, 张铎, 李明雨. 基于PERT技术的导弹批量测试流程仿真研究［J］. 弹箭与制导学报, 2008, 28(1): 39-42.
HU Hai-sheng, ZHANG Duo, LI Ming-yu. Study of missile batch testing process simulation based on PERT［J］. Journal of Projectiles, Rockets, Missiles and Guidance, 2008, 28(1): 39-42.(in Chinese)
［6］路辉, 李昕. 一种基于分支定界的串行测试任务调度算法［J］. 航空学报, 2008, 29(1): 131-135.
LU Hui, LI Xin. A kind of scheduling algorithm for serial test tasks based on branch and bound algorithm［J］. Acta Aeronautica et Astronautica Sinica, 2008, 29(1): 131-135.(in Chinese)
［7］李昕, 沈士团, 路辉. 基于图染色理论的并行测试任务调度算法［J］. 北京航空航天大学学报, 2007, 33(9): 1068-1071.
LI Xin, SHEN Shi-tuan, LU Hui. Algorithm of tasks scheduling in parallel test based on graph coloring theory［J］. Journal of Beijing University of Aeronautics and Astronautics, 2007, 33(9): 1068-1071.(in Chinese)
［8］秦勇, 梁旭. 基于混合遗传算法的并行测试任务调度研究［J］. 国外电子测量技术, 2016, 35(9): 72-75.
QIN Yong, LIANG XU. Research on hybrid genetic algorithm for parallel test task scheduling［J］. Foreign Electronic Measurement Technology, 2016, 35(9): 72-75.(in Chinese)
［9］陈利安, 肖明清, 高峰,等. 人工蜂群算法在并行测试任务调度中的应用［J］. 计算机测量与控制, 2012, 20(6): 1470-1472.
CHEN Li-an, XIAO Ming-qing, GAO Feng, et al. Artificial bee colony algorithm for parallel test tasks scheduling［J］. Computer Measurement & Control, 2012, 20(6): 1470-1472.(in Chinese)
［10］付新华, 肖明清, 刘万俊,等. 一种新的并行测试任务调度算法［J］. 航空学报, 2009, 30(12): 2363-2370.
FU Xin-hua, XIAO Ming-qing, LIU WAN-jun, et al. A novel algorithm for parallel test task scheduling［J］. Acta Aeronautica et Astronautica Sinica, 2009, 30(12): 2363-2370.(in Chinese)
［11］夏克寒, 牟建华, 暴飞虎,等. 导弹测试流程优化系统设计与实现［J］. 导弹与航天运载技术, 2012(2): 43-46.
XIA Ke-han, MOU Jian-hua, BAO Fei-hu, et al. Design and implementation of missile test process optimizing system ［J］.Missiles and Space Vehicles,2012(2):43-46.(in Chinese)
［12］ Lu H, Wang X, Liu J. Constraint handling technique in test task scheduling problem［J］. Information Technology Journal, 2014, 13(8):1495-1504.
［13］ Addition I. Chaotic Multiobjective evolutionary algorithm based on decomposition for test task scheduling problem［J］. Mathematical Problems in Engineering, 2014(4):11-18.
［14］ Lu H, Zhu Z, Wang X, et al. A variable neighborhood MOEA/D for multiobjective test task scheduling problem［J］. Mathematical Problems in Engineering, 2014(3):1-14.
［15］ Lu H, Niu R, Liu J, et al. A chaotic non-dominated sorting genetic algorithm for the multi-objective automatic test task scheduling problem［J］. Applied Soft Computing, 2013, 13(5):2790-2802.
［16］ Lu H, ZHANG M M. Non-integrated algorithm based on EDA and Tabu search for test task scheduling problem［C］∥Proceedings of 2015 IEEE AUTOTESTCON. National Harbor, MD, US:IEEE,2015： 261-268.

第39卷
第2期2018 年2月兵工学报ACTA
ARMAMENTARIIVol.39No.2Feb.2018

[1]	陈亚萍, 王楠, 洪华杰, 刘召阳, 闫响达. 面向多无人平台区域监视任务的信息素正向激励栅格方法[J]. 兵工学报, 2023, 44(9): 2859-2870.
[2]	杨善超，田康生，李宏权，周广涛，梁复台. 综合优先级下反导预警相控阵雷达任务调度算法[J]. 兵工学报, 2020, 41(2): 315-323.
[3]	胡涛, 马晨辉, 申立群, 梁洁. 基于蚁群算法的测试任务调度优化方法[J]. 兵工学报, 2019, 40(6): 1310-1316.
[4]	吕志峰，赵欣，张金生，王仕成，李婷. 磁屏蔽装置结构参数的组合优化方法[J]. 兵工学报, 2018, 39(11): 2211-2219.
[5]	昝翔，陈春良，张仕新，王铮，刘彦. 多约束条件下战时装备维修任务分配方法[J]. 兵工学报, 2017, 38(8): 1603-1609.
[6]	郑玉军，田康生，张金林，刘俊凯. 基于模糊神经网络的相控阵雷达任务调度设计[J]. 兵工学报, 2016, 37(11): 2010-2014.
[7]	严峰，陈晓，王新民，彭程，胡亚洲. 改进的离散小波-优化极限学习机在倾转旋翼机故障诊断中的应用[J]. 兵工学报, 2014, 35(11): 1914-1921.