第四方检验检测平台任务动态调度策略优化

黄素贞HUANG Su-zhen；王莹WANG Ying

（北京信息科技大学经济管理学院，北京 100192）

0 引言

第四方检验检测平台是检验检测行业在第三方平台的基础上做出的创新，通过进一步集中市场现存的检验检测资源，整合检测领域产业链上的多个主体，从而实现检验检测领域的一站式集成化服务的专业领域集成化平台。在第四方平台运营的过程中，由于检测任务日趋复杂和集成化，因此需要拆分成若干个检测子任务，并由平台中的多个检测服务机构合作完成。在检测任务完成的过程中，新的检验检测订单不断进入，因此，如何对大量检测任务进行科学合理地动态调度是第四方检验检测平台面临的一个亟待解决的问题。高效有序的任务动态调度对于加快检测领域的发展和促进第四方检验检测平台的落地有重大推进作用。调度优化的目的是根据约束目标，合理分配资源，使调度目标达到最优[1]。

随着互联网+和大数据的快速发展，平台的动态调度优化吸引了大量学者的研究。曾薇[2]提出一种云平台大量任务的多目标约束调度模型，运用蚁群算法求解来达到调度目标最优。Liu 等[3]提出了一个多任务的云制造调度模型，并通过仿真实验研究了不同的基于工作负载的任务调度方法对系统性能的影响。当前的相关研究中针对检验检测领域的专业集成化平台动态调度问题的研究尚不多见。本文拟从复杂网络的视角出发，将大量检测子任务抽象为网络节点，通过约束规则构建成复杂网络模型，并对蚁群算法进行改进，使其适用于求解模型，为检验检测平台下的任务动态调度提供有效的优化方案，提高平台检测任务调度效率的同时也带动检验检测服务业的发展，具有较高的研究价值与意义。

1 第四方检验检测平台任务复杂动态调度模型构建

第四方检验检测平台中的检测任务是不断随机到达的，一个检测任务需要分解为多个检测子任务进行检测，在复杂网络中表现为若干个节点的增多，子任务检测完成后会退出网络，表现为节点的减少，因此网络是不断变化的，这种网络结构的动态变化称为更新规则。因此可以将复杂网络表示为节点、边和更新规则的三元组[4]，即

将检测任务抽象为复杂网络的规则如下：用网络中的节点代表每个检测子任务，根据子任务间的资源约束和任务约束将节点连接起来。假设有4 个检测任务，第四方检验检测平台中有n 个检测资源，检测任务与检测资源的匹配情况如表1 所示。

表1 检测任务与检测资源匹配结果

根据复杂网络构建规则得到的复杂网络如图1 所示。

图1 中Lxy表示检测资源x 与检测资源y 之间进行任务运输所消耗的时间。虽然检测任务的加入和退出使得复杂网络表现出很强的动态性，但任意时刻的网络都和图1相似。通过以上规则构建复杂网络模型，可以用复杂网络的节点遍历解决第四方检验检测平台任务动态调度问题。

图1 复杂网络调度模型

2 改进蚁群算法

2.1 路径选择规则优化

优先遍历度值较大的点，可以降低网络的耦合度，缩短遍历时间。同时检测子任务有其特定属性：子任务检测时间越长或后序子任务数越多，越有可能优先检测。因此本文将节点度值与任务属性相结合[5]，引入蚂蚁路径选择规则中，引导蚂蚁在节点转移时，优先选择度值与任务属性的综合值较大的节点，用hj表示节点综合任务属性，综合值计算方法如式（4）所示。

节点度值和任务属性的计算公式用式5）-（6）表示。

kj-um表示节点j 的无向边数目；kj-in表示节点j 的入度值，入度由有向边指向节点引起的；kj-out表示节点j 的出度值，出度由有向边从该节点指出引起的。

Vj表示节点j 对应子任务的检测时间。pnn（Vj）表示节点j 的后续节点数。

蚂蚁遍历过程中，将所有可达节点根据度值分为三种类型，并保存在不同的集合中，如表2 所示。

表2 节点类型示意图

蚂蚁的转移节点选择分为三步：首先遍历集合Uk1中的节点，当Uk1中的节点为空时，再开始遍历Uk3中的节点，最后遍历集合Uk2的节点，直到网络中的节点数量为0。

转移概率计算公式如式（7）所示。

按照上述步骤，可以使蚂蚁在遍历节点的过程中，首先遍历那些入度为0 的节点，而出度为0 的点在最后遍历，从而保证子任务按优先级顺序进行检测。

2.2 并行蚂蚁优化

本文采用并行蚂蚁的策略，设置和检测资源数量相等的蚂蚁数目，将蚁群中的每只蚂蚁分配到每个检测资源上，让每只蚂蚁独立负责一个检测资源所构成的小网络的遍历。蚁群搜索过程中利用节点度值与任务属性的综合值来引导蚂蚁的路径选择。多只蚂蚁同时遍历，使收敛速度加快。每只蚂蚁遍历完成所在检测资源上的所有节点时，对该检测资源所构成的小型网络进行局部的信息素更新，所有蚂蚁完成遍历后，对整个网络进行全局的信息素更新。并行蚂蚁思想在第四方检验检测平台中的任务遍历过程如图2 所示。

图2 并行蚂蚁策略在第四方检验检测平台中的应用原理

局部信息素更新根据式（8）进行。

按式（9）-（11）进行全局信息素更新。

考虑加入最大最小蚂蚁系统的思想，来防止某条路径上的信息素积累过多，从而陷入局部最优，将信息素的量限制在某个范围内，和的值分别按式（12）-（13）计算。

其中Tbest是当前解的最优值，ε 是信息素因子的下限，一般设置为特别小的一个正数。

3 第四方检验检测平台动态任务重调度方案生成

3.1 重调度驱动机制和重调度策略设计

基于最大任务数的事件驱动机制的思想是：设置一个最大任务数上限值θs，当有新任务到达时，判断θ 的大小，若θ＜θs，则接受该新任务，触发重调度，否则不再接受该新任务的加入，继续按照原调度方案执行直至所有子任务检测完成退出网络。

第四方检验检测平台下的任务调度问题中，为每个子任务分配检测资源后不再改变，需要确定的是子任务间的检测顺序安排，因此本部分研究问题的完全重调度就是对子任务检测顺序的重新安排。完全重调度策略可描述为：当有新任务加入触发重调度时，检测资源首先需要将正在进行的检测任务完成，然后再对新增加的子任务和其他剩余未检测的子任务进行检测顺序的安排，得到新的检测顺序方案。

3.2 有新任务加入的动态重调度方案生成

基于预测反应式动态调度模型和复杂网络思想，当由新任务到达时，触发重调度，同时加入多个检测子任务，即复杂网络中有多个节点和边的增加，符合网络的生长规则。根据排队论思想,当新任务到达时遵循先到先服务的原则，新到达的任务根据到达顺序加入到网络中。根据重调度驱动机制、重调度策略，得到有新任务加入的第四方检验检测平台任务重调度方案如图3 所示。

图3 重调度方案执行流程图

4 仿真实验

本节设计仿真对比实验，设置相同的资源数目，当任务数量不同时，对比本文算法与文献[6]算法的性能。实验数据和算法参数如表3 所示。其中需要为子任务随机分配检测资源，同时生成检测子任务的检测时间。

表3 实验数据

实验环境保持相同开始实验，将10 次实验结果的平均值作为最终对比结果，两种算法在任务数不同时的平均最长检测完成时间、平均迭代次数对比结果如图4 所示。

图4 不同?任务数下两种算法实验结果对比图

从实验结果比对图中可得知，在不同的任务数量下，本文提出的结合复杂网络改进的蚁群算法在检测完成时间和算法迭代次数上都优于文献[6]，说明本文提出的改进蚁群算法具有良好的解决实际调度问题的性能。尤其在迭代次数上，随着任务数量的不断加大，收敛速度相对文献[6]表现出的优势越来明显。实验结果可以充分表明，将度值与任务属性的综合值应用于转移概率公式中引导蚂蚁对节点的选择，对基本蚁群算法的路径选择规则优化，并将并行蚂蚁思想应用于蚁群算法后，得到的改进蚁群算法在调度性能上优于文献[6]的算法。

5 结论

本文针对第四方检验检测平台中任务随机到达的动态任务调度问题，从复杂网络的视角出发，构建出复杂网络模型。采用预测反应式动态调度模型，并结合基于最大任务数的事件驱动机制和完全重调度策略，将第四方检验检测平台中有任务到达的动态调度问题转变为相对稳定的静态调度问题，生成第四方检验检测平台任务重调度方案，并使用改进蚁群算法对重调度方案进行求解。通过与其他算法进行实验对比，发现本文提出的改进蚁群算法在求解重调度问题中效率更高。