韦智勇 杨晓武

1(南宁职业技术学院 广西 南宁 530008)2(中南大学机电工程学院 湖南 长沙 410083)

0 引 言

当前，资源受限系统[1-3]调度问题广泛存在于企业生产和社会实践中，对其研究的重要性和必要性不言而喻。一般而言，资源受限系统调度问题是以若干任务需求为处置对象，以消耗有限的服务资源为代价，在满足一定使用规则前提下，寻找能够促使特定指标得以优化的可行方案[4-5]。通常情况下，资源受限系统调度问题属于NP-hard问题，具有明显的复杂性特征。许多学者致力于为其寻找高效求解算法，通过调整任务编排方案以最大化资源使用效益。在此过程中，启发式算法和群智能算法应用普遍。

近年来针对资源受限系统调度问题的研究较多，例如，张忆文等[6]以并行处理器的节能调度策略为研究背景，在考虑任务执行时间与CPU处理速率为非线性关系的情况下，建立任务调度模型，并结合动态电压调节技术和功耗管理技术设计出低能耗资源调配算法。何杰光等[7]针对资源受限系统调度问题提出一种动态多样性群智能算法，主要思路是采用两点交叉算子和变异算子进化个体，基于精英保留策略优化种群，算法能够在全局搜索和局部优化之间进行平衡。GABREL等[8-9]对成像卫星观测任务调度问题开展研究，通过抽象约束条件建立出任务规划模型，并采用加权有向无环图方法进行求解。Arnaout等[10]分析了无联系并行机的调度策略，将蚁群算法ACO(Ant colony optimization)应用于问题求解，通过两阶段问题转换，获取最短任务完成时长的优化方案。在上述研究中，共性的基本假设之一是任务不可拆分，即每个任务若可被安排执行，只能一次完成，执行过程不能停顿。但是实际应用中，对长耗时任务进行切割以提升满足概率是被允许的。此外，任务切割还可以更好地利用调度过程中产生的碎片化资源，提升资源利用率。

本文针对任务可拆分条件下的资源调度方法开展研究，探讨采用何种切割方式提升任务满足概率。为保证调度效果，采用改进粒子群算法IPSO(Improve particle swarm optimization)[11-13]进行全局搜索。为降低资源使用的冲突程度，在执行时段优选时引入冲突规避策略CAS(Confliction avoid strategy)。文中给出了冲突集的概念，构建了冲突度模型。通过对比测试，对文中所提出方法的有效性进行了验证。

1 问题分析

1.1 调度过程描述

对于一个完备的资源调度系统[14-15]，应至少包含若干服务节点(服务资源)和任务需求(服务对象)，调度过程可从以下角度进行描述：

(1) 从服务资源的角度描述。在初始时刻，各服务节点均为空闲状态。调度开始后，规划器实时获取各服务节点的繁忙状态，根据一定规则挑选任务指派给服务节点。获取任务的服务资源被占用一定时长，完成服务后再转入空闲状态。

(2) 从服务对象的角度描述。在调度开始前，不同用户提交的资源使用申请汇聚形成待调度任务队列。可满足的任务汇入等待服务任务队列，到达预定服务时限后转入服务队列接收处置，服务完毕后再转入完成服务任务队列。在此过程中，可对部分任务进行拆分，通过化整为零方式执行，提升任务满足可能性。

结合实际应用背景，资源调度过程通常追寻特定优化目标。从服务资源的角度考量，资源利用率最大化是追求的重要指标。从服务对象的角度考量，任务满足率一般作为评价标准，这两项指标存在关联性，即高任务满足率往往对应着高资源利用率。但对于资源受限系统而言，通常存在服务资源稀缺的情况，即系统的服务能力仅能满足部分而非全部服务需求，这就要求设计合理的资源调配方法，使有限的服务资源得到高效利用。采用任务拆分方式，能够有效利用破碎化的资源时段，促使原本不可满足的任务得以执行。在此过程中，如何选择拆分对象，以何种粒度拆分是必须解决的问题。

1.2 服务资源描述

考虑资源受限系统服务节点异构，具体表现为状态准备时间、任务处置速率、状态恢复时间存在差异。采用五元组对服务节点进行形式化描述，表示为：

NS=

(1)

Node={node1,node2,…,noden}：服务资源集合，nodei为所有资源中的第i个服务节点，n为服务节点的数量；

TW={tw1,tw2,…,twn}：可用时间窗口集合，twi=[twbi,twei]为nodei的可用时段，twbi和twei分别为twi的起始时间和结束时间；

SP={sp1,sp2,…,spn}：任务处理速率集合，spi为nodei的任务处置速率；

TP={tp1,tp2,…,tpn}：状态准备时间集合，tpi为nodei开始任务前所需的状态准备时间；

TR={tr1,tr2,…,trn}：状态恢复时间集合，tri为nodei完成任务后，再开展下一次任务前所需的状态恢复时间。

1.3 任务需求描述

对用户提交各种请求进行规范化处理，形成标准化待任务需求。本文考虑的任务需求均为相互独立的无关联任务，采用五元组对服务节点进行形式化描述，表示为：

TS=

(2)

Task={task1,task2,…,taskm}：任务需求集合，taski为第i个任务，m为任务数量；

TA={ta1,ta2,…,tam}：任务允许执行最早时间集合，tai表示taski允许被执行的最早时刻；

TD={td1,td2,…,tdm}：任务执行截止期集合，tdi表示taski的执行截止期；

DL={dl1,dl2,…,dlm}：任务数据量集合，dli表示taski的指令长度；

P={p1,p2,…,pm}：任务优先级集合，pi表示taski的优先级系数。

2 模型构建

任务规划的结果是完成服务资源与任务需求匹配，形成合理的规划方案，而构建资源调度模型是实现该目标的前提条件，其主要由决策变量集，优化目标集，约束条件集等要素构成。为便于后续描述，表1给出部分符号说明。

表1 部分符号说明

(3)

决策变量Y=[yi]用于标识任务的可执行性，明确任务是否分配资源，赋值方法如下：

(4)

式中:yi=1表示taski被分配资源(安排执行)；yi=0表示taski未被分配资源(拒绝执行)。

决策变量ETW=[]用于标识任务的有效服务时段。对于staski,j，其资源占用时段与有效服务时段存在以下关系：

(5)

在筹划任务规划方案阶段，所需遵循的主要约束条件如下：

约束1：如果任务被安排执行(yi=1)，对其累计有效服务时长不低于所需最少保障时间。

(6)

约束2：任务的执行时段应处于其允许执行窗口中，占用资源时段应处于其所分配服务节点的可用时间窗口内。

(7)

约束3：若任务被分解执行，其子任务不能被并行处理。

(8)

约束4：资源具有独占性，即每个服务节点同一时刻最多处理一个任务(子任务)。

(9)

约束5：若安排任务执行(yi=1)，其子任务应当全部得到满足。

(10)

本文考虑以任务满足率作为主要优化目标，以资源利用率为次要优化目标，表示为：

(11)

式中：Q1、Q2为X和Y的可行域；GT(X)为可用服务资源的利用率；GR(Y)为考虑优先级后的加权任务满足率。

3 算法设计

3.1 基本结构

本文在算法设计中引入了分层优化的算法结构，这是基于两点考虑：一是本文研究的问题既要考虑传统的任务资源匹配问题，还要考虑任务切分问题，所考虑的约束存在关联性，这增加了问题求解难度。采用分层优化的方法可以化繁为简，分而治之，更容易工程实现。二是从求解效率上来看，任务资源匹配问题和任务切分问题存在强耦合关系，若采用整体优化方式，搜索解空间较大。采用分层优化方式可逐层消减解空间规模，有利于有化解的快速产生。整体算法结构包括主控层、决策层和逻辑层，如图1所示。

图1 求解算法的主要构成

主控层负责掌控算法状态，控制迭代过程；决策层用于选择搜索方向，产生任务指派顺序；逻辑层负责挑选拆分任务，解算有效服务时段，具体生成任务规划方案。算法的基本流程如下：

Step1主控算法接收任务需求队列，则触发规划活动；

Step2决策层采用IPSO算法优化任务指派序列，并将结果传递给逻辑层；

Step3逻辑层完成约束消解，对决策变量X、Y、ETW赋值，并传递给主控层；

Step4主控层评估规划结果，若决定继续迭代，转入Step 2；否则，直接输出规划方案，算法结束。

3.2 IPSO算法

经典PSO算法的基本思想是通过驱动粒子以位移的方式搜索问题解空间，而个体根据种群间的交互信息确定移动方向和速度。其中，每个粒子均表示决策层的一个方案，种群挑选个体最佳位置作为群体最优位置。

3.2.1粒子编码规则

设种群由SN个粒子构成，其中pari为种群中的第i个粒子，其在第t次进化时的位置向量为：

(12)

例如，随机生成一个粒子pari，其位置向量及表示的任务指派序列为：

(13)

3.2.2位置更新方式

首先给出种群的适应度函数，用于评估粒子所在位置的优劣，如下所示：

(14)

(15)

(16)

3.2.3基于云模型的变异策略

为避免种群陷入早熟，引入变异操作。首先借鉴云模型产生变异概率，然后根据个体适应度挑选变异对象。

(16)

(17)

(18)

3.3 CAS策略

针对决策层传递的任务指派序列，利用CAS策略进行解析，生成具体的资源调配方案。在此过程中，需根据任务状态构建若干集合：

WSTSet：等待规划任务集，用于存储尚未参与调度的(子)任务队列；

WETSet：等待执行任务集，用于存储已分配资源但未执行的(子)任务队列；

RETSet：无法满足任务集，用于储存已参与调度但未满足的(子)任务队列；

FETSet：完成执行任务集，用于储存执行完毕的(子)任务队列。

在上述集合中，WSTSet是规划系统的处置对象，可满足的任务移至WETSet中，无法满足的任务移至RETSet中，而FETSet中的元素对对规划过程无影响。

定义1对于taski∈WSTSet和给定时间窗口TS，称taski在TS中具有需求冲突，记为Conf(TS,taski)=1，若满足以下关系：

TS∩[tai,tdi]≠∅

(19)

算法1Pseudocode ofCAS

01:DeletetaskifromWSTSet;

02:fornodekinNode

03:FTWSik←[tai,tdi];

04:forstaski′,j′inWETSet

05:ifxi′,j′k=1then

06:FTWSik←FTWSik∩([tsbi′,j′,tsei′,j′])C;

07:endif

08:endfor

09:forftwi,jkinFTWSik

10:ifspan(ftwi,jk)

11:Deleteftwi,jkfromFTWSik;

12:else

13:hdci,jk←0;

14:fortaski′inWSTSet

15:hdci,jk←hdci,jk+Conf(ftwi,jk,taski′);

16:endfor

17:endif

18:endfor

19:VTWSik←FTWSik;

20:endfor

21:Return;

算法2Pseudocode ofPTC

01:fortaskiinWSTSet

02: Calculate i=1,2,…，nby 算法1;

03: SortVTWi,jkbyHDCSi,jkin increasing order;

04:Rem_len←dli,dni←0,yi=0;

10:tsbi,dni=tvbi,dni+trk′,tsei,dni=tvei,dni+tpk′;

11:tsli,dni←tsei,dni-tsbi,dni,tvli,dni←tvei,dni-tvbi,dni;

12:Rem_len←Rem_len-tvei,dni+tvbi,dni;

13:endwhile

14:ifRem_len=0then

15:yi←1;

16:else

17:dni←0;

18:tsli,j←Null,tvli,j←Null,tvbi,j←Null,tvei,j←Null,tsbi,j←Null,tsei,j←Null,xi,jk←0,j=1,2,…，dni,k=1,2,…，m;

19:endif

20: LetX=[xi,jk],Y=[yi],ETW=[];

21:Return;

4 实验分析

本节中模拟生成任务规划场景，对文中所提方法的有效性进行对比分析。

4.1 测试场景设置

批量生成场景数据，调用不同算法进行实验，以统计指标的平均值作为测试结果，场景要素的设置方法如下：

1) 整个任务规划活动的周期跨度为24 h；

2) 设置3个服务节点，服务能力指标根据参数设置情况随机生成，如表2所示。

表2 服务资源的设置情况

3) 任务数量为100～300个，任务数据量包括150～250 min、250～350 min、350～450 min三种类型，任务允许执行最早时间和截止期在规划活动周期内随机生成。

在求解方法设计时，同时嵌入了启发式算法和智能优化算法。其中，启发式算法用于快速提升解的质量，本文主要测试其有效性。IPSO算法单次运行时间较长，理论上而言，足够长的迭代次数均能获取较优的可行解，因此本文更关注其搜索效率。采用分步验证方法进行实验，测试内容主要包括以下两项：

(1) 算法的搜索质量分析。主要是CAS策略和PTC规则的有效性。决策层固定使用IPSO算法，逻辑层引入Greedy策略和禁止任务切割FTC(Forbid task cutting)规则，与之前所提算法进行对比。主控层算法根据对比算法的组合方式命名，如表3所示。

表3 测试算法的组合方式

(2) 算法的搜索速率分析。主要是加入CAS策略和PTC规则后对算法运行时间的增量，以及IPSO算法的收敛速率。

4.2 算法的搜索质量分析

在不同任务强度下对比三种组合算法的实验结果，统计指标包括任务满足率和资源利用率，如图2所示。

(a) 任务满足率

(b) 资源使用率图2 不同任务规模下的调度结果对比

从图2可以看出，随着任务强度的增加，任务满足率迅速下降，而资源使用率在快速增长后趋近平稳。系统资源的服务能力经历了由充足到饱和的过程，说明所选测试场景能够较为全面地呈现出多种供需状态，具有一定的代表性。

根据测试结果，在不同测试场景下，IPSOPG的求解结果均优于IPSOFG，这是由于PTC规则通过任务切割能够使原本无法满足的任务得到执行，由此说明该策略的有效性；IPSOPC的求解结果均优于IPSOPG，这是优于在具体指派资源时，CAS策略能够预见性的规避需求冲突，最大程度地保留后续任务的满足机会，因而求解效果更好。综上可以得出结论，CAS策略和PTC规则对于提升算法搜索质量是有效的。

4.3 算法搜索速率分析

在不同任务强度下测试算法的运算时间，统计结果如图3所示。

图3 不同任务规模下的算法耗时对比

从图3可以看出，以IPSOPC算法的耗时最高，IPSOFG与IPSOPG算法的耗时接近。由此可以说明，采用FTC规则对于算法造成的负担不显著，而引入CAS策略会明显增加算法的时间复杂度。为进一步分析CAS策略和FTC规则对算法搜索速率的影响，以IPSOFG算法为基准，分析其他两种算法的相对搜索时间增量，如图4所示。

图4 相对搜索时间增量的变化趋势

在图4中，随任务强度的增加，IPSOFG算法的搜索时间增量稳定处于较低水平，说明FTC规则对于算法搜索速率的影响较弱。IPSOPC算法搜索时间的增量呈线性变化，本文采用最小二乘法进行拟合，得到的近似关系式为：

t=-7.597 7+0.086 6m

(20)

由此可以说明，CAS策略虽会延缓算法的搜索速率，但该策略不会导致算法的搜索时间呈爆发式增长，其时间复杂度在可接收范畴。

IPSOPC为本文提出的主要算法，对算法中的种群适应度演变过程进行统计，以分析算法的搜索效率，如图5所示。

图5 种群适应度的演变过程

从图5可以看出，种群在第1～7代进化明显，在第7～23代进化平稳，在第23代后逐渐停止进化。说明IPSO算法在迭代早期能够快速搜索解空间，获取问题的初始优化解集。在迭代中期，能够不断提升种群适应度，持续改进优化解的质量。在迭代末期，能够保持种群的稳定，对优化解集进行收敛。基于上述过程，IPSO算法基本实现了在确保收敛前提下避免过早陷入局部最优的目标，能够以较为高效的搜索速率获得理想结果。

5 结 语

本文针对任务可拆分条件下的资源受限系统调度问题开展研究，以最大化任务满足率和资源利用率为优化目标，建立了约束模型。为降低求解复杂度，在算法设计时，构建了多层求解结构，并分别提出了优化算法。其中，IPSO算法应用于决策层，该算法是在经典PSO算法的基础上加入了部分改进策略，能够避免种群陷入早熟。CAS策略和PTC规则被应用于逻辑层，用于服务资源的指派和任务执行时段的明确。在实验部分，通过测试对文中所提方法的有效性进行了验证。需要指出的是，本文所提算法仍有很大改进空间，后续将根据项目背景作进一步研究。