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

王正元, 刘卫东, 景慧丽, 屈娜

(西安高技术研究所， 陕西 西安 710025)

0 引言

一些导弹武器、雷达装备在作战使用前需要按照一定工序测试维护，测试合格的武器装备才能投入使用[1-3]。通常情况下，测试车间预设多条测试流水线，每1条流水线上从左至右预先布置了多个工位，任意1条流水线上最多同时容纳一定数量的装备接受测试，任意工位任意时刻最多对1台装备进行测试，1台装备任意时刻最多在1个工位接受测试，所有装备从测试车间入口到某一流水线按照固定工位顺序接受测试，测试完后从出口离开测试车间。战时通常有多台同类别不同型号的装备进入测试车间接受测试，为保障作战任务顺利进行，要求全部装备完成测试所需时间越短越好。确定装备测试顺序，使得测试任务完成时间最短的问题就是一种装备测试任务调度问题。

装备测试任务调度问题实际上是一种并行任务调度问题。在每1条流水线上，各台装备测试任务调度问题与同顺序作业调度问题(FSP)类似。由于1条流水线上同时只能容纳一定数量的装备接受测试，导致该问题与FSP不同。此外，测试车间存在多条流水线，因而需要把待测试装备分配给各条流水线。装备测试调度问题的特点使得问题精确求解变得较为困难，目前主要采用仿真方法[1]、Petri网[4]、计划评审技术(PERT)[5]、分支定界法[6]、图染色理论[7]以及智能优化方法[8-16]计算调度方案，在计算过程中为简化问题有时采用优先权方法[1-3]。装备并行测试任务调度问题中，各装备测试顺序是可调整的，相应的网络结构也是可调整的，因而可利用PERT方法计算完工时间；实际问题求解过程中有一些规律可用于简化问题求解，如问题的下界、按照一定规律排列的待测试装备分配方案等。本文针对一种特殊的装备并行测试任务调度问题，建立了数学模型，并提出了该问题的启发式求解方法。根据装备测试任务调度问题的特点，提出了单一流水线装备测试任务调度问题的下界算法，利用下界算法进行各流水线待测试装备初始分配，构造了装备并行测试任务调度优化问题的求解算法，较好地解决了装备测试任务调度优化问题。

1 装备测试任务调度问题数学模型

装备测试任务调度的目的是为了在尽可能短的时间内完成装备测试任务，因而可以选择测试任务完成时间为目标函数。假设共有某类别m种不同型号装备等待测试，型号i的装备ni台，共有测试流水线h条。每台装备最多在n个工位完成测试，每个工位执行一道工序，型号i的装备在工位j上测试时间为tij. 安排在流水线u(u≤h)上测试的第k台装备型号为yku，流水线u上测试型号i的装备xiu台，1条流水线上任意时刻最多a台装备处于测试状态，任意工位任何时刻最多只测试1台装备。为简单起见，下面仅考虑a=2，a>2时可用类似方式得到相应结论。装备测试任务调度问题数学模型为

s.t.

dj+1(k,u)=
max{dj(k,u),dj+1(k-1,u)}+tykuj,k>1，
dj+1(1,u)=dj(1,u)+ty1uj，
d1(k,u)=d1+n(k-2,u),k>2d1(k,u)=d1+n(k-2,u)，k>2,
d1(k,u)=0,k=1,2.

(1)

(2)

(3)

yku=1,2,…,m,
y1u≠y2u.

(4)

其中

约束条件(1)式确保1条流水线上最多2台装备处于测试状态，并且1个工位最多1台装备处于测试状态；约束条件(2)式使得在h条流水线上测试完各型号装备；约束条件(3)式使得各型号待测试装备都安排到第u条流水线；约束条件(4)式使得测试装备型号在给定的型号范围内。

2 单一流水线上装备测试任务调度问题的下界

单一流水线u(u=1,2,…,h)上待测试装备给定时，各工位测试时间总和为

(5)

由于同一流水线上最多允许2台装备在不同工位上测试，任何时刻都有2台装备处于测试状态时，完成测试全部装备的时间为T(u)/2. 实际上，测试装备在1个工位测试结束后，后续测试装备才能使用该工位，因而完成测试全部装备的时间不小于T(u)/2. 此外，所有装备都必须在最后1个工位上测试，不妨假设倒数第2台装备测试完后立即在工位n上测试最后1台装备，这样完成测试任务时间最短。

定理1流水线u上，给定待测试各型号装备数量xiu(i=1,2,…,m)，型号i的装备在工位j所需测试时间为tij，流水线同时容纳2台装备进行测试，任意时刻每个工位最多对1台装备进行测试，则得到单一流水线装备测试任务调度问题的下界，即单一流水线上完成全部测试任务所需时间的下界为

(6)

证明：假设流水线u上待测试装备按照一定次序排放，奇数、偶数序号装备测试完毕所需时间总和分别记为To、Te，而各工位上测试全部装备所需时间和为

则

To+Te=T(u).

不妨设最后1台装备序号为奇数，记

tmin=min {tin|xiu>0,i=1,2,…,m},

则测试完成时间T满足

T≥max {To-tmin,Te}+tmin≥
(To-tmin+Te)/2+tmin=
(To+tmin+Te)/2=
(T(u)+tmin)/2,

所以完成全部测试任务所需时间的下界为

B(u)=(T(u)+min {tin|xiu>0,i=1,2,…,m})/2.

流水线上待测试装备已排序时，奇偶数序号装备测试任务所需时间分别为To、Te，则下界B(u)为

(7)

3 单一流水线装备测试任务调度问题求解的启发式方法

给定流水线上待测试装备时，装备测试任务调度问题就是一种排序问题。利用问题的领域知识构造启发式方法，可以实现问题的快速求解。对于单一流水线上装备测试任务调度问题，启发式求解方法步骤描述如下。

算法1单一流水线上装备测试任务调度问题求解的启发式方法。

步骤1输入待测试各型装备数量xiu(i≤m)，输入各型号装备在各工位上测试时间tij(1≤j≤n)，计算流水线u上待测试的装备总量为

步骤2首先将装备测试序号分成两个子集，相应装备在流水线上奇数或偶数序号测试。

步骤4改变当前解中装备的测试顺序，得到解Y.

步骤5计算目标函数值f(u)，如果f(u)

步骤6改变两个子集的组成，按(7)式计算测试时间下界B(u)，若B(u)

步骤7比较不同子集划分方式对应近似解的目标函数值，选择最优目标函数值对应近似解为装备测试任务调度问题的解。

求解过程通常从最均衡的子集开始，即优先考虑下界最小的情形。计算得到测试调度初始方案以后，再考虑下界略大的子集情形。一旦某种子集对应下界高于已得到调度方案目标值，则可以结束计算。由于使用了(7)式计算测试时间下界，可以很快确定有些情况不能得到最优解，从而简化了问题求解过程。

4 多流水线待测试装备分配方法

装备测试任务在多条测试流水线上进行时，首先需要进行待测试装备在不同流水线上的分配。实际问题求解过程中，通常需要对多流水线待测试装备进行多次重分配，每次分配都是围绕一个基准方案展开。基准方案中，各流水线上分配的测试任务量尽可能靠近，即每条流水线上各工位完成测试任务所需时间之和与各流水线上平均测试任务量A的误差平方和最小。由于

是常量，选择多流水线待测试装备初始分配模型为

模型求解步骤描述如下。

算法2多流水线待测试装备初始分配模型求解方法。

步骤1输入待测试各型装备数量ni(1≤i≤m)，在各工位测试时间tij(1≤j≤n)。

步骤2将各型号待测试装备按照每台装备所需测试时间由大到小依次分配到各流水线，已分配测试任务量最小的流水线优先分配任务，直到全部待测试装备分配完毕。

步骤3计算各流水线分配测试任务总量，调整承担测试任务量最大、最小流水线的装备测试任务，直到不能调整。

对于实际问题，依据各流水线待测试装备分配结果进一步求解装备测试任务调度问题，计算结果与问题的下界偏差较大。为了进一步降低完成测试任务所需时间，需要对分配给各流水线的待测试装备进行调整。调整时主要围绕初始分配模型的解展开，在目标函数值变化不大的范围内寻找可进一步降低完成测试任务所需时间的解。

5 装备并行测试任务调度问题求解的启发式方法

装备并行测试任务调度问题求解过程较为复杂，可以把它分解为多个子问题迭代求解得到问题的解。问题求解步骤描述如下。

算法3装备并行测试任务调度问题求解的启发式方法。

步骤1输入流水线数量h、工位数n、装备型号数m，各型号装备数量ni(1≤i≤m)，型号i装备在工位上测试所需时间tij(1≤j≤n)。

步骤2使用算法2计算各流水线待测试装备初始分配方案。

步骤3使用算法1计算各流水线装备测试任务调度方案，得到这时装备测试任务完成所需时间为

步骤4改变各流水线待测试装备分配方案，使用下界算法计算各流水线装备测试任务完成所需时间的下界B(u).

步骤5选择满足Tf>max {B(u)|1≤u≤h}的待测试装备分配方案。

步骤6使用算法1计算各流水线装备测试任务调度方案，得到这种情况下装备测试任务完成所需时间T′f.

步骤7如果T′fmax {B(u)|1≤u≤h}的待测试装备分配方案。

步骤8输出计算结果，退出计算。

6 实例分析

现有2条流水线，每条流水线上有7个工位，需要测试交付使用的装备数量及其在各工位上测试所需时间如表1所示。

每条流水线上最多容纳2台装备同时测试，任意时刻每个工位最多测试1台设备，每台装备均从工位1开始测试(时间为0时不需要测试)，到工位7上测试完毕后离开测试流水线。确定甲、乙、丙3型装备测试任务调度方案，使得测试任务完成时间尽可能短。

表1 待测试装备数量及其在各工位测试时间

为了计算较好的装备测试任务调度初始方案，采用算法2求得2条流水线上待测试装备初始分配方案，装备初始分配方案为型号甲、乙、丙的装备数量相同，即2条流水线上各有5台甲型装备、5台乙型装备和10台丙型装备。使用算法1求解装备测试任务调度方案如表2所示，2条流水线上任务调度方案相同，完成测试时间为635 s.

表2 装备测试任务调度初始方案

对于单一流水线上装备测试任务调度，给定20台待测试装备时共涉及36种情况，求解时只需考虑6种情形(下界不超过635 s)，计算量大大减少。利用定理1，得到这种情况下装备测试任务调度问题下界为624 s，与当前解对应目标函数值635 s有一定差距。按照算法3，改变2条流水线上待测试装备分配方案，不考虑下界大于635 s的分配方案，选择满足条件的新分配方案如表3所示。

表3 2条流水线上待测试装备分配方案

使用算法1计算新分配方案下装备测试任务调度方案，结果如表4所示。

待测试装备新分配方案中，流水线1承担测试任务量1 248 s，完成测试任务所需时间下界628 s，测试任务调度方案对应完成测试时间632 s；流水线2承担测试任务量1 232 s，完成测试任务所需时间下界620 s，测试任务调度方案对应完成测试时间624 s. 因而，完成全部测试任务只需632 s，比初始方案缩短3 s.

表4 调整后装备测试任务调度方案

求解过程中，利用对问题自身的认识，从任务量最均衡时特殊初始解出发得到较好的近似解，进一步利用给定待测试装备分配方案下测试任务调度问题的下界与当前最优解目标函数值比较，可以预先排除一些分配方案，从而可以减少计算量，提高问题求解效率。如例中，按照算法3，改变测试任务量分配时，总计1 271种情形，只需考虑11种(2条轨道中最大测试任务量介于1 240 s与1 253 s之间)，这样，大大降低了问题求解计算量。

7 结论

装备测试任务调度问题是一类较为复杂的组合优化问题，本文结合装备测试任务调度问题的特点构造了问题求解的系列算法，提出了这类问题目标函数值的一种下界，并将问题求解过程分解为各流水线待测试装备分配和给定流水线上待测试装备时测试任务调度。 装备测试任务调度问题分解成2个子问题求解的方式大大降低了问题求解的难度，计算结果非常接近最优解，甚至就是最优解，这说明本文方法是解决装备测试任务调度问题的一种有效方法。

)

[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.