分布式科技资源多服务任务优化调度

阴艳超，张万达，廖伟智，牛红伟

(1.昆明理工大学 机电工程学院,云南 昆明 650550; 2.电子科技大学 机械与电气工程学院,四川 成都 611731;3.北京理工大学 机械与车辆学院,北京 100081)

0 引言

《国务院关于加快科技服务业发展的若干意见》明确提出了重点发展研究开发、技术转移、检验检测认证、创业孵化、知识产权、科技咨询、科技金融、科学技术普及等专业科技服务和综合科技服务[1]。《意见》的颁布使我国成为世界上第一个对科技服务业进行系统研究的国家。然而，我国科技资源及其分布复杂多样且科技服务系统众多，科技服务系统与系统外部的实体经济产业之间、科技服务系统内部之间的组成与关系十分复杂，需要在分布于各地各行业的巨大科技资源中搜索、分析、匹配和调度科技资源，形成科学合理的解决方案。科技服务活动的实时动态性和执行时间的随机性远比预期的复杂，作为科技服务活动本身自发形成的不确定性很难用传统调度理论和方法解决，而是要综合考虑科技服务调度过程中需求、服务、资源和效能之间的相互耦合和影响[2-3]。

调度问题是分布式科技资源按需服务的核心问题之一。与传统的科技资源检索服务相比，分布式科技资源按需服务在服务任务、服务过程、科技资源和服务效能等方面都存在较大差异。从科技资源服务任务来看，服务任务由实体经济产业的服务需求驱动，并随服务需求的动态拓展、转移和组合，在服务主体和实体产业客体交互过程中不断更新和完善；从服务过程来看，科技资源云服务是一种按用户需求定制的服务模式，其调度问题不再是简单的检索与资源匹配，而是要考虑服务过程的柔性与动态组合性；从科技资源本身来看，复杂多态的科技资源分布于全国各地、各行业和各单位等不同地理位置的异构系统中，跨企业的资源调度需要考虑不同企业资源服务能力、响应速度和负载能力问题；从服务效能看，资源的优化调度过程不仅需要考虑影响和制约科技资源服务能力以及效能最大化的成本和效率等基本因素，还需要考虑其服务于实体产业的及时性与均衡性等重要要素。因此，科技资源按需服务的动态性、不确定性和协同性使解决其分布式环境下的调度问题更加困难。

目前,针对科技资源服务，国内外学者大多针对高校图书馆和情报机构如何提供文献查新、文献检索和知识推送等资源服务的视角展开研究[4]。对资源调度的研究主要集中在云计算资源[5]、网络资源[6]和云制造资源[7]的调度，其中云计算资源调度的研究主要集中在调度算法方面，如粒子群优化算法[8]、遗传算法[9]、模拟退火算法[10]等智能启发式调度算法，然而该类方法对实际因素考虑不足，算法搜索效率偏低，无法应对大规模资源调度问题。针对云制造资源调度，LIU等[11]尝试引入博弈论，并考虑服务、物流和服务能力等动态因素，根据工作量和重要程度对调度任务进行排序。文献[12]研究了基于能耗的调度优化方法，文献[13]提出制造服务组合调度策略和算法。上述研究较少考虑科技资源调度的并发服务访问不确定和分配不均衡两个重要影响因素，而且上述方法虽然研究资源调度，但大都不是面向科技服务业，无法针对实体产业科技服务需求，在分布式科技服务环境下按需调度、共享和利用科技资源。

本文针对科技资源服务过程响应速度低，按需服务实体产业分配不均衡的问题，搭建了考虑分布式科技资源服务并发服务访问不确定性和资源分配不均衡性的多服务任务优化调度模型，通过重构粒子表达式完成粒子群搜索空间到优化调度方案的映射，通过引入多种群协同交互搜索机制和异步并行策略，提高知识服务过程响应能力，优化知识服务系统性能，为解决科技资源多服务任务调度问题提供了一种新的方法和技术手段。

1 分布式科技资源服务调度问题分析

科技资源服务的调度按照资源类型不同分为计算资源调度和科技资源调度两大类。科技服务平台中计算资源位于云平台的计算中心，主要为上层科技资源的管控和运行提供底层的计算和存储环境，是科技资源调度的基础。换言之，科技资源服务调度是科技资源与实体产业科技服务任务之间的组合匹配过程，调度系统位于云端的科技服务平台中，调度系统与分布于各地各行业的巨大科技资源之间通过互联网进行信息交互，导致云端调度系统难以对分布在不同地理位置、具有不同实时状态的科技资源发生的动态干扰和不确定事件做出及时有效的响应。因此，分布式科技资源服务调度问题的特点如下：

(1)多任务交互执行 科技服务是一种面向需求的科技资源分布式汇聚和按需分享的服务模式，在服务业与实体产业深度融合的背景下，与实体产业科技服务任务进行调度和匹配的不再是传统的科技资源，而是科技服务。因为科技服务系统与实体经济产业之间、科技服务系统内部之间的组成与关系均很复杂，而且科技服务过程中涉及大规模异构资源的汇聚、融合，跨语言搜索、匹配和推理，所以服务需求驱动下的科技服务活动形成了多任务交互执行协作网，科技服务具有较强的柔性。

(2)服务响应的不确定性 在分布式科技服务环境下，科技资源通过分布式汇聚、虚拟化封装和服务化共享后形成科技服务，并在云端的服务云池中被统一管控和运行，而科技服务所映射的科技资源分布在各地/各行业/各单位资源系统中。因此，在分布式科技服务任务调度过程中不仅要考虑服务之间的关联协作关系，还要考虑服务任务在分布式科技资源之间的传输时间。调度系统需要在调度过程中处理大量的服务调度并在设定好的时间内做出响应，因此要求调度系统合理安排影响服务响应的并发服务访问，在充分利用计算资源的同时保障系统的响应能力，按需给用户提供适时的输出。

(3)资源分配的不均衡性 科技服务需要围绕实体产业产品生命周期不同阶段的业务活动配置合理的科技资源，然而需求驱动下的科技资源服务活动形成多任务交互执行协作网，而且一个服务活动可同时发生在多个服务任务执行过程中，随着任务的形成和发展而动态衍生变化，随着实体产业服务需求的变化，相应的服务也需要不断拓展、收缩和重点转移。这些动态和不确定因素会严重影响服务资源分配的均衡性。

在分布式科技服务环境下，实体产业用户根据自己的服务需求向科技服务平台提交服务任务；科技服务云平台及时解析服务任务，并根据云平台中科技资源的状态信息和实体产业科技服务任务的实时信息，调动分布式科技资源云池中的科技资源，形成最优的服务任务执行方案，并将其提交到平台执行，以完成知识服务任务调度。在整个调度过程中，多服务任务交互执行，任务之间存在复杂的关联协作关系，并随着分布式科技资源池规模的动态增长，需要考虑服务任务在分布式科技资源服务的并发访问，同时大量动态和不确定因素会严重影响服务调度的能力和效果，本文将在提高服务效率的同时解决科技资源并发服务访问的不确定性以及节点负载不均衡引起的科技资源分配不合理问题。

2 科技服务优化调度模型

2.1 分布式科技资源并发服务访问的不确定性建模

实体产业用户服务业务流程中对科技资源服务的调用关系错综复杂，尤其当一个资源服务被多个业务流程调用，且这些业务流程同时运行时，就会出现并发访问。不同资源服务场景下，实体产业用户的访问频率和并发概率都存在一定程度的波动和不确定性，而且科技资源服务过程中不同的服务流程访问频率与其业务流程的顺序、选择、并行、循环等不同结构密切相关，因此科技资源并发服务访问的不确定性可以用并发服务访问概率来描述，其相关数学符号及描述如表1所示。

表1 分布式科技资源并发服务访问概率建模符号及描述

假设科技服务中心在执行某一项服务任务时，有K项虚拟资源供L个子任务调用，且这些子任务根据服务进程在特定的节点上完成，则该服务任务执行流程的概率为

(1)

当多服务任务交互执行时，在资源服务调用中经常发生并发访问，为完成某项任务，会调用多个资源服务流程，当流程中存在选择结构，且一个流程分支覆盖并发访问服务时，并发访问服务的概率为

(2)

如果服务流程中所有选择分支均覆盖当前并发访问的服务，则并发访问服务的概率为

(3)

2.2 资源分配不均衡性建模

假设某项服务任务T={t1,t2,…,tn}需要调用n项子任务完成，能够提供服务的分布式虚拟科技资源总数为m，这些子任务按照服务业务总流程和资源需求在不同任务环节上完成，则定义任务ti调用科技资源rj的预期完成时间为

(4)

式中：GIi为服务任务ti的总指令长度；SRj为科技资源rj被分布式调用指令的执行速度。

定义n个不同服务任务调度m项分布在异地的虚拟资源的平均负载为：n个服务任务总指令长度与m个虚拟资源被分布式调度总指令执行速度的商。即总服务任务完成时间为

(5)

对于上述调度方案，服务资源被调用的负载均衡度定义为

(6)

式中：Ω为总服务任务的完成时间；Ωj为调用服务资源rj的任务完成时间。可见，Π越小，该服务调度任务负载越均衡。

2.3 多目标优化调度模型

在考虑分布式科技资源服务并发服务访问不确定性和资源分配不均衡性问题的基础上，搭建了包括服务效率、并发服务访问概率和资源调用负载均衡度的多目标优化调度数学模型。

(7)

记N项服务任务映射的科技资源集合为X={x1,x2,…,xn}，x为某一项服务子任务调用的科技资源，对于资源调度的优化，需要在将服务效率优化到最大的同时将并发访问概率和负载均衡度优化到最小，因此考虑了分布式科技资源并发服务访问不确定性和资源分配不均衡性的多目标优化调度数学模型为：

F(x)=(R,X)=(-Se(x),

Pt(x),Π(x))→min。

s.t.

xj∈X且x≤M;

(8)

式中：semin为符合用户需求的最低服务效率值；ptmax为某一科技资源节点所能承受的最大并发服务访问概率；Πmax为某一科技资源节点所能承受的最高负载均衡度。

由于-Se(x),Pt(x),Π(x)之间的数值差异很大且量纲不同，需要进行归一化处理：

(9)

式中vi={-Se(x),Pt(x),Π(x)}。设用户请求科技资源的服务效率、负载均衡度和并发服务访问概率的权重分别为ωse，ωΠ，ωpt，依据层次分析法对其进行赋值，且ωse+ωΠ+ωpt=1，则在考虑用户需求目标权重条件下的科技资源优化调度目标函数为

F(x)=ωΠZ[Π(x)]+ωseZ[-se(x)]+ωptZ[pt(x)]。

(10)

3 基于多群落协作搜索的科技服务动态 调度算法

3.1 多群落双向驱动进化机制

大规模任务调度问题往往涉及更多的决策变量和优化目标，而且随着系统、用户需求和调度目标等环境的变化，其必将成为复杂的多目标优化问题。粒子群算法可以在迭代过程中维持潜在解的种群，并根据环境变化不断调整种群的适应度，更容易适应环境变化。因此，面对多任务调度问题的不确定性、复杂性，本文改进和拓展种群寻优模式，提出多群落双向驱动协作搜索算法(Multi-Community Bidirectional Drive Collaborative Search Method, M-CBDCSM)，将高维解空间划分为低维多任务搜索子空间，引入一种由普通群落和模范群落组成的多群落交互网络，建立不同搜索任务与协作种群之间的信息交互和关联规则，并根据环境不断优化种群的适应度，提高算法对高维多任务变化的适应能力。在此基础上，制定不同群落间的异步并行搜索策略，减少群落进程间的通信，通过群落间的驱动进化机制[14]实现高效搜索，提高算法对任务调度问题的优化能力。多群落双向驱动进化机制如图1所示。

多群落双向驱动协同进化规则如下：

规则1粒子群落内进化规则。在多群落协同进化过程中，单个群落内的粒子按照式(11)对速度和位置进行更新迭代优化，并在群落内产生全局最优值，其中gbest为普通群落，Gbest为模范群落。

i=1,2,…,m，d=1,2,…,D。

(11)

式中：t为粒子搜索的迭代次数；ω为惯性权重；c1=c2=2为加速常数；r1和r2为两个在[0，1]范围内变化的随机函数。

规则2群落间的双向驱动协同进化规则。

(1)∀(r1:〈CCi,MCj〉)∈R，∃gbesti=max{gbest1,gbest2,…,gbestm}，Gbestj=min{Gbest1,Gbest2,…,Gbestn}，且gbesti≥Gbestj，则gbest中粒子CCi进入Gbest，而Gbest中排在最末位的群落MCj被淘汰。同时，将模范学习因子Pn引入gbest内部进化规则，则新迭代进化公式为：

i=1,2,…,m,d=1,2,…,D。

(12)

(2)∀(r2:〈MCi,MCj〉)∈R，存在群落节点强度SMCi[14]，对任意SMCj，均满足SMCi≥SMCj，则模范群落全局最优值PG=Gbestj。

(3)∀(r3:〈CCi,CCj〉)∈R，存在群落节点强度SCCi，对任意SCCj，均满足SCCi≥SCCj，则普通群落全局最优值Pg=gbesti。

3.2 科技资源多服务任务调度的编码策略

粒子群算法是面向实数连续空间的计算模型[15-17]，难以解决属于离散空间的任务调度问题。因此，采用二进制对粒子的速度和位置进行编码，通过重构粒子表达式实现粒子群算法到离散空间、粒子搜索空间到优化调度方案的映射。

上述算法中，定义m行n列矩阵Zmn为粒子的位置矢量矩阵，其中：行表示任一服务任务执行时提供科技资源的情况，列表示调度过程中服务任务的分配情况，任一粒子代表调度方案某个科技服务任务调度问题的潜在解。则粒子位置的编码为

(13)

由编码方案知，位置矩阵Z中每一行有且只有1个元素值为1，表示科技资源X分配到服务任务R中执行；每个科技资源可以同时被多个服务任务调用，且不能中断任一科技服务任务的执行。定义速度矩阵Vmn如式(13)所示，表示粒子对执行任务分配情况的基本交换次序。

(14)

式中vij∈{0,1},vij+vji∈{0,1}。

定义算法中的加、减、乘运算为Θ，θ，⊕，⊗的交换操作，具体运算规则如下：

(1)A·θ·B表示在位置矩阵A与速度矩阵B中，∃zij=vij⟹zij=vij=0，反之为1；∃zij=vij+n=1⟹vij+n=0。

(2)AΘB表示在位置矩阵A与速度矩阵B中，∃vi1,vi2,…,vin=0⟹vii=0，其他元素随机取0或1。

(3)ci⊗B表示依据随机数ci的对应概率值确定粒子是否与矩阵B进行Θ操作。

(4)A⊕B表示在位置矩阵A与速度矩阵B中，∀zia=1,zjb=1,∃vij=1⟹zib=1,zja=1。

根据上述交换操作规则的定义，将式(11)更新为：

i=1,2,…,m,d=1,2,…,D。

(15)

所制定的编码方案简单可行，符合科技资源多服务任务调度的要求，而且清晰描述了粒子种群进化空间与服务任务调度方案间的映射关系，较好地避免了粒子进化过程中的重复搜索。

3.3 基于多群落协作搜索的科技资源服务调度 优化算法

基于多群落协作搜索算法及其编码方案，分布式科技资源多服务任务优化调度过程如图2所示。具体步骤如下：

步骤1种群粒子初始化。根据3.2节所述的粒子搜索空间与任务调度方案之间的编码策略，对n个群落进行初始化，赋予种群粒子随机位置(资源分配方案)和速度；设定群落数、群落成员内的粒子迭代次数、粒子加速系数和惯性权重系数。

步骤3将各群落分别运行于q个进程中进行异步并行进化运算。

步骤4计算各群落适应值Fi，并根据判定阈值将所有群落划分为模范群落和普通群落两类。

步骤5根据3.1节不同粒子种群间的交互进化机制，按照式(15)更新群落中粒子的位置和速度，并将模范和普通群落的全局最优位置保存到最优存储区。

步骤6若所有粒子种群均满足搜索终止条件，则算法结束，从全局最优存储区中获取全局最优解，输出最优调度方案，否则转步骤5。

4 应用案例与分析

本文以科技服务平台中针对汽车发动机故障维修进行科技服务为例，对所提科技资源服务调度算法进行实验验证。如图3所示，该平台上汽车发动机维护维修服务包括“发动机零部件三维模型展示”“发动机拆装路径规划”“发动机维护维修培训”“发动机故障识别与维修”等多个服务业务，每个业务活动需要通过服务任务调用相关手册、标准、维修方法、故障类型、工艺规范、工具、参数、程序、仿真分析模型和经验案例等分布异构的多领域科技资源，为实体产业用户服务提供按需服务。因此，面向汽车发动机维护维修任务的科技资源服务调度可以抽象为：某项汽车发动机维修任务通过云平台申请提供科技资源服务，该项维修任务又分为n个子任务，而服务平台有m个科技资源可以提供服务，如何将这n项发动机维修子任务合理安排在m个科技资源上并给出调度顺序，使其包含服务效率、并发访问概率和资源调用负载均衡度的调度目标达到最优。

针对科技资源服务平台中的发动机故障维修服务任务，将其细分为故障原因分析、维修资源匹配、维修资源推送、维修效果评价4项服务子任务，仿真实验中需要4个节点，粒子的维度应为4。假设能够向节点提供科技资源服务的I/O点数有100个，则在多服务任务调度过程中可采集服务效率、并发服务访问概率和负载均衡度等指标作为样本数据，由数据库查得本资源集合中服务效率、并发访问概率、负载均衡度的值，限于篇幅，不对样本数据进行列举。

本次实验种群规模均设置为100，维数为4，迭代次数为200，惯性权重w=1.1，加速常数c1=c2=2，所有仿真实验均进行500次并取其平均值，具体编码设置如下：

(1)编码设置

定义调度算法粒子个体的位置矢量为矩阵Z1004，如图4所示。其中第i行表示科技资源zi的服务情况，第j列表示维修服务任务Rj的分配情况；若zij=1，则表示科技资源zi为维修任务Rj提供资源服务。此时，每个粒子表示一个资源服务任务调度方案。

(2)调度算法性能分析

科技资源服务平台通过调度引擎获取各个子任务所需的科技资源，为验证所提服务任务调度方法的有效性，采用MATLAB在基于Xeon E5-2609V2处理器和RAM64G的浪潮英信服务器上进行仿真实验，并采集多服务任务调度过程中的服务效率、并发服务访问概率和负载均衡度等作为样本数据。实验时，取服务效率ωse、并发概率ωΠ、负载度权重ωpt分别为：0.8，0.05，0.15；0.4，0.3，0.3；0.25，0.1，0.65。为了验证所提方法的有效性，采用文献[18]的改进混合遗传算法(Modified Hybrid Genetic Algorithm, MHGA)、文献[19]中的离散粒子群优化(Discrete Particle Swarm Optimization, DPSO)的任务调度算法和本文提出的M-CBDCSM算法，求解发动机故障识别与维修服务任务的最优调度方案，实验结果如图5所示。

由图5可知，在分布式科技资源多服务任务调度过程中，M-CBDCSM算法能够较好地适应并发服务访问概率的随机变化，在搜索过程中自适应选择粒子群落之间的交互进化规则；同时，随着群落个数的增加，M-CBDCSM算法能较其余两种算法相对快速且稳定地收敛到全局最优值。相对于DPSO算法，M-CBDCSM算法在不同搜索工况下均能于50代前找到最优调度方案，其收敛速度和精度优势明显；MHGA算法在面对动态随机的多任务调度时，由于难以自适应地进行个体变异操作和交叉操作，进而无法追踪资源服务调度的动态环境，造成在高随机搜索工况下难以避免早熟现象，其算法性能远低于M-CBDCSM算法。

为了进一步验证算法的执行效率，体现大规模种群面对复杂调度环境时强大的适应能力，选定种群规模为1 000，分别对不同数量的资源服务任务调度问题进行仿真实验，仿真结果如表2所示。可见，随着服务任务的增加，在调度求解过程中，M-CBDCSM算法的收敛速度并未出现大幅度降低的现象，特别是当服务任务数量由4增长为25时，该算法的收敛速度仅下降了20%，可见在采用大规模种群时，面对任务规模动态变化的服务调度问题，M-CBDCSM算法可以通过双向驱动进化机制协调多个群落进行协同搜索，以较快的收敛速度持续高效地完成调度优化。

表2 不同任务规模对比实验结果(n=0,t=200)

综合图5和表2的实验数据可知，本文所提的M-CBDCSM算法可根据资源服务调度过程中的环境变化，自适应选择和重组粒子群落之间的交互进化机制，以增强不同种群的多样性，从而提高算法对搜索环境的适应能力和求解精度。由仿真结果可知，本文方法可有效解决科技资源服务调度过程中并发服务访问不确定性和资源分配不均衡性，在解决分布式环境下的科技资源多服务任务调度问题上的性能明显优于其他对比算法。

5 结束语

针对科技资源服务过程中的并发服务访问不确定性高，按需服务实体产业分配不均衡的问题，本文提出一种考虑资源服务并发服务访问不确定性和资源分配不均衡的启发式任务调度方法，得到如下主要结论：

(1)本文构建的多服务任务优化调度数学模型能够满足高效率和高利用率的科技资源分配需求。

(2)本文设计的M-CBDCSM算法制定了优化算法映射到离散数据空间的编码规则，实现了普通群落和模范群落间双向驱动的协同交互搜索，增强了算法对动态随机调度任务的适应能力。

(3)采用算例验证本文所提模型和算法，结果表明本文方法克服了现有算法搜索效率偏低、很少考虑并发服务访问不确定和分配不均衡性方面的局限性，在解决科技资源与实体产业服务请求之间的动态资源匹配调度具有一定优势。

今后将进一步考虑调度过程中科技资源服务用户的需求与偏好特征，研究相应的动态调度快速响应策略，使其更加高效准确地解决多服务任务的资源调度问题。