考虑云制造服务协同的多用户任务调度优化

王天日,张敏敏,刘 娟,2+,张鹏志

(1.太原理工大学 经济管理学院,山西 太原 030024;2.太原理工大学 省部共建煤基能源清洁高效利用国家重点实验室,山西 太原 030024)

0 引言

随着云计算、物联网、大数据等技术的发展及其在制造领域中的渗透,李伯虎等[1]最早提出了“云制造”的概念。在这种生产模式下,生产企业将制造资源和制造能力发布到云制造平台,平台将这些资源虚拟封装成云服务,以便用户按需获取,从而有助于实现分布式社会化资源的高效配置,进而降低资源的使用成本。

近年来,云制造环境下面向多任务制造云服务组合与调度引起了广大研究者的关注[2-4]。然而,大部分研究面向多任务需求,从制造云服务的服务质量(Quality of Service,QoS)属性进行建模与优化求解。LI等[5]从任务角度建立了以时间、成本和服务质量为优化目标的云服务调度模型。ZHOU等[6]构建了以服务质量和能耗为目标的云服务组合模型,并设计了一种多目标进化算法获得一组非支配解,以满足不同顾客的偏好。该模型只考虑了同质任务的组合问题,并未考虑制造系统中服务占用问题。以上研究中的任务并未涉及多个用户层面的讨论,针对多个用户任务的研究还相对欠缺。基于此,ZHOU等[7]从用户需求多样化出发建立了云服务调度生产模型,设定每一任务分属不同的用户,未能考虑一个用户可能提交多个任务的情景。

云制造平台中制造资源的多样性、分散性、协同性等给云制造资源的调度优化带来巨大挑战[8]。为实现云服务调度优化,除了QoS属性外,部分研究考虑了云服务间的信任特征来构建服务组合或资源调度模型,如服务的可靠性与可信性[9]、云服务信任关系[10]、云服务企业间信任度[11]等。此外,制造云服务的合作属性在云服务的协同特征中被考虑,但主要集中在云服务组合方面。具体而言,在云服务质量评价中构建基于网络协同模式[12]、云服务组合协同效应[13]、企业亲密度[14]等模型实现服务优选评价,进而利用蜂群算法、蚁群算法等进行求解。事实上服务协同不仅涉及到合作,还涉及到竞争属性,即在云服务协同完成一系列子任务过程中,具有相同功能属性的云服务之间存在竞争关系。服务间的合作与竞争关系会作用于服务调度中的选择与排序,最终影响调度结果。

协同配置分布式的制造资源服务是云制造生产模式的典型特征。因此本文在分布式制造环境下,考虑了不同用户提交多项任务的情景,挖掘云服务的社会属性以有效提高云服务的社会参与度和合作能力。首先,在云制造平台制造服务调度框架下,面向多个用户任务需求,从合作与竞争的角度考虑云服务间的协同效应,以平均用户满意度最大化、制造服务协同效应最大化为优化目标构建面向多用户的制造云服务双目标调度模型。然后,考虑到灰狼优化算法收敛速度快及较强的全局搜索能力,针对所提问题特点,在灰狼优化(Grey Wolf Optimizer,GWO)算法框架下引入模拟退火算法,利用其鲁棒优化能力,改进GWO算法的局部搜索性能。最后,通过试验验证了所提模型在改进云服务协同方面的优势,同时与其他算法相比,展示了所提算法在求解该模型的高效性,从而丰富了相关研究。

1 问题描述与模型构建

1.1 问题描述

云制造系统中涉及用户、云制造平台和制造资源提供者。不同的用户可以随时向云制造平台提交任务请求,如图1所示为云制造模式下多用户任务的调度框架。为了满足用户任务的调度需求,云制造平台通常将不同时间段提交的任务划分在不同的调度窗口,在同一任务提交窗口内的用户任务被划分在相同的调度窗口。假设N个用户向云平台同时提交多个制造任务,用户集合为U={U1,U2,…,Ui,…,UN},第i个用户有Ji个任务,其第j个任务可以分解为Lij个子任务,且各子任务都可由云服务平台注册的M个云服务执行。

图1 云制造模式下用户任务调度框架

1.2 数学模型

1.2.1 模型假设

模型假设如下：

(1)用户的所有任务之间是相互独立的,且每个任务都可分解为多个子任务;

(2)每个云服务可完成多种类型的子任务,但某一时刻仅能处理一项子任务;

(3)每个子任务可选的云服务有多种,但只能由一个云服务执行,且一旦执行不可被打断;

(4)按照用户提交时间和交货期的要求,将所有任务开始时刻转化为零;

(5)不同云服务完成某一子任务的时间、成本不同,并且提前已知。

1.2.2 数学模型

基于以上的问题描述构建多用户任务调度的数学模型,涉及到的相关符号如表1所示。

表1 符号定义表

该模型以用户满意度和云服务协同效应为优化目标,具体描述如下：

(1)用户满意度

为构建用户满意度指标,综合考虑完工时间、完工成本和完工质量3个QoS因素。

1)用户的完工时间由最晚交付给用户的任务完工时间决定,表示为：

(1)

2)用户的完工成本等于用户所有任务的完工成本之和,表示为：

(2)

3)云服务的质量合格率可以体现服务质量,可通过以往用户对制造云服务的历史评分进行度量。由于每个用户有多个任务,将某用户所有任务的最小服务质量作为影响该用户服务质量的指标,表示为：

(3)

因此,第i个用户的满意度表示为：

(4)

(5)

(6)

(7)

以平均用户满意度作为第一个优化目标,计算方式如下：

(8)

(2)云服务协同效应

制造云服务的社会属性涉及合作与竞争两个方面。当云服务需要合作完成两个相继的子任务时必然存在信息交流与互动,云服务企业之间由于软硬件设施的不同则会造成云服务间合作关系的不同。同时,当多个云服务都能够完成某项子任务时,存在竞争关系的云服务会对同一个子任务进行抢夺,竞争力强的服务会获得该子任务订单。本文利用合作亲密度和距离亲密度衡量两个云服务之间的合作水平。

1)合作亲密度。

云服务间能够通过信息交流相互合作共同完成一项任务,在大数据环境下可以根据历史记录信息得到云服务之间的合作次数,因此合作亲密度CF可根据下式进行计算：

CFmm′=1-e-λ×CTmm′。

(9)

式中：CTmm′表示第m个云服务与第m′个云服务的合作次数,λ表示合作紧密系数,为常量。

2)距离亲密度。

由于生产云服务地理位置的分散性,越短的地理距离越有助于减少子任务之间物流运输的阻塞[15]。本文利用式(10)将两个云服务之间的地理距离映射为数值在0～1之间的距离亲密度：

(10)

式中DS、DM及DL分别为衡量距离亲密度高、中、低的3个阈值常量。

综上,云服务m和m′的合作水平SImm′可由下式表示：

SImm′=c1CFmm′+c2DImm′。

(11)

式中：c1、c2表示两个云服务之间合作亲密度和距离亲密度分别对二者之间合作水平的贡献程度大小,可依据专家评价进行设定,且c1+c2=1。

竞争属性指云服务企业的市场竞争力,本文用市场占有率衡量其竞争力,具体由云企业某类产品或服务在一定时期内和一定区域内的市场销售中占有同类产品或服务的比例表示,其计算公式如下：

(12)

式中：pm为云服务m的市场营业额,P为能提供与云服务m相同服务的所有云服务的营业额。

云服务之间竞争力差异越大,说明其市场优势差异越明显。此时,竞争力强的云服务之间在需要合作时更容易彼此认同;竞争力弱的云服务则可共同提高服务利用率。竞争力差异大的云服务之间则会产生与上述两种情况相反的倾向,即合作意向减弱,对协同效应产生负向影响。即使二者之间原先有很高的亲密度,由于一方受市场中其他服务影响从而竞争力变小拉大差距,最后服务协同性也会降低。因此,为更好地衡量云服务间的协同效应,应该同时考虑云服务m和m′之间的合作关系与竞争关系。其协同效应

(13)

采用云服务协同矩阵直观地表示不同制造云服务之间的协同能力,矩阵中数值可根据以上的协同效应计算公式计算得出,所有数值均在0～1之间。

作为第2个优化目标,所有用户任务的平均服务协同效应如下：

(14)

(3)模型约束

该模型的基本约束如下：

1)子任务约束。式(15)表示同一任务的各子任务满足预先定义的加工顺序,某一子任务的前序子任务都完工之后,该子任务才能进行加工。

i=1,2,…,N;j=1,2,…,Ji;l=2,…,Lij。

(15)

2)云服务约束。同一个云服务上加工的两个子任务加工时间不能重叠,如子任务stijl与stabp在同一个云服务上加工,且stijl的顺序优先于stabp,则有：

i=1,2,…,N;j=1,2,…,Ji;l=1,2,…,Lij;

a=1,2,…,N;b=1,2,…,Ja;p=1,2,…,Lab;

m,m′=1,2,…,M。

(16)

3)完工时间与开始时间的约束如式(17)所示,每个用户任务的开始时间大于等于0,如式(18)所示：

(17)

STijl≥0,i=1,2,…,N;j=1,2,…,Ji;l=1,2,…,Lij。

(18)

4)每个子任务只能在一个云服务上进行加工,如式(19)所示：

(19)

2 GWO-SA算法设计

任务调度问题是一个典型的NP-hard问题[16],为了获得更优的决策解,本文采用离散的灰狼优化算法[17]。由于参数少、收敛速度快且具有较好的全局搜索能力,该算法目前已经被广泛应用于求解各类工程问题[18-19]。然而,原始的GWO在求解连续问题时其求解精度与稳定性方面有较大优势,而对于离散问题的求解并不能直接应用。因此,本文基于模拟退火(Simulated Annealing,SA)算法的局部搜索能力,在GWO算法框架上进行算法改进,从而设计了GWO-SA算法,该算法能提高解的质量,最终获得满足决策者的优化调度方案。

2.1 问题编码

由于该模型涉及两个问题：首先需要为每个子任务从可选的云服务候选集中选择一个可用的云服务;其次对同一个云服务上的多个子任务进行排序。根据问题特性,本文采用二向量实数编码方式对决策变量进行编码,染色体分为二向量：第一向量为子任务选择云服务,第二向量对子任务进行排序。

假设有两个用户同时向云制造系统中提交了生产任务。云系统中有5个云服务能够处理所有子任务,分别编号1～5。第1个用户有2个任务,分别分解得到2、3个顺序执行的子任务。第2个用户有1个任务,分解得到的子任务数量为3,其染色体如图2所示。从图中可看出染色体长度为子任务总数的2倍。对于云服务选择部分,从左到右每个基因位上的数字表示该位置对应的子任务选择了编号为这一数字的云服务。例如,第5个数字2表示第1个用户的第2个任务的第3个子任务选择了编号为2的云服务。其他基因位的表示方法类似。对于子任务排序部分,后半段染色体基因位数代表总的子任务数,子任务用其对应任务的序号表示,且某序号出现的次数代表对应任务的子任务数。进行排序的编译依据是对应任务的序号次序,即从左侧开始扫描后半段染色体,同一任务序号出现的第k次代表该任务的第k个子任务。如图2所示的调度问题,基因串中的两个1依次表示第一个任务的两个子任务,从左到右,第一个基因位上的1表示第一个任务的第一个子任务,第6个基因位上的1表示第一个任务的第二个子任务,用此种编码方式能够使得一个任务经分解得到的子任务之间保持先后顺序。

图2 染色体编码

2.2 社会领导层级机制

GWO的核心思想是找到种群中3个适应值最好的灰狼(α,β,δ),其他个体(ω)利用这些个体的引导对整个解空间进行探索,这种利用优良个体信息的方式能够加快种群的收敛。在多目标优化问题中,个体的适应值可由支配等级表示,根据带精英策略的快速非支配排序遗传算法(fast elitist Non-dominated Sorting Genetic Algorithm,NSGA-II)的支配等级计算和拥挤度计算可将种群划分为多个非支配层,因此,α,β,δ的确定可根据以下规则：

(1)若种群只有一个非支配层,根据拥挤距离采用二元锦标赛机制选取3个个体作为α,β,δ。

(2)当种群有两个非支配层,随机选择第一层中一个灰狼并将其视为α,第二层利用拥挤度计算采用二元锦标赛机制选取两个个体作为β,δ。

(3)当种群有3个非支配层,则从第1,2,3层各自随机选择一个个体作为α,β,δ。

2.3 捕食行为机制

原始的GWO每只ω狼随机选择领导个体进行追随,这种方式并不能确保一个好的搜寻方向。由于相似个体之间的信息交流往往更有利于生成优良个体,为了保持种群有一个良好的搜寻方向,本文设计的算法使每只ω狼可根据在当前种群中的非支配等级选择领导个体。新个体生成策略如下：

(1)若ω狼在第1个非支配等级,则Xnew=CR(Xα,X);

(2)若ω狼在第2个非支配等级,则

(20)

(3)若ω狼的非支配等级大于等于3,则随机选择领导个体：

(21)

根据问题特性,染色体的前后两部分分别应用两种不同的交叉(Crossover,CR)操作。对子任务排序部分,采用POX(precedence operation crossover)交叉[20]。为增加种群多样性、防止算法陷入局部最优,云服务选择部分则采用自适应性交叉机制。首先定义一个个体G的引导概率pf,其计算公式如下：

(22)

式中：pf(t)表示第t次迭代的领导个体引导概率,pfmin、pfmax表示最小值和最大值,maxIt指最大迭代次数。根据该式可以看出个体的引导概率在逐渐减小,这有利于防止算法陷入局部最优。具体交叉过程如图3所示。

图3 自适应性交叉

交叉步骤如下：

步骤1随机生成一个取值在0～1间的数组。

步骤2找到小于pf的位置,将G相应位置的基因位继承给新个体。

步骤3新个体其他基因位则由原个体继承。

基于问题特征本文采用不同的变异算子。对于云服务选择部分,随机选择一个变异点,从该子任务的可选云服务序号中随机选择一个进行替换;对于子任务排序部分,随机选择两个基因位然后交换各自的值,这样产生的后代不会破坏解的可行性。

2.4 模拟退火算法

领导个体的引导虽然会加快算法的收敛速度,但是个体的追随策略会使GWO陷入局部最优[19]。因此,采用以下3种策略作为模拟退火算法的状态转移方式进行局部搜索,从而提高解的多样性和解的质量。

(1)云服务最优配置

随机选择一个子任务,为其随机选择服务成本最小、服务时间最小或者服务质量最大的云服务。

(2)增加协同策略

随机选择一个用户,逐步判断该用户每一任务的所有子任务是否可以在同一个云服务上进行服务。如果可以,则将相继的两个子任务安排在同一个云服务上以减少物流时间和成本,同时增加任务的协同能力。

(3)负载平衡策略

该方法是基于云服务负载均衡的启发式策略。保持子任务的排序不动,对云服务选择部分进行重新布置,配置策略如下：

1)计算每个云服务的最大完工时间(LFTm)：

(23)

2)计算每个子任务可选云服务的选择概率：

(24)

式中m为子任务可选择云服务的序号。

3)计算可选云服务的被选择概率：

(25)

4)采用轮盘赌的方法重新对云服务进行选择。

进行遗传操作后,对种群中的个体以概率pr进行模拟退火搜索,增加解的多样性。冷却温度计算如式(26)所示,可以看出冷却温度是自适应的、非线性的、缓和的。

(26)

式中：k为退火速度,it表示当前迭代次数,T0为一个常数。

模拟退火算法的步骤如下：

步骤1输入种群,模拟退火最大迭代次数Maxit,令it=1,根据式(26)计算冷却温度。

步骤2判断it是否大于Maxit,若是,则结束;否则转步骤3。

步骤3随机选择一种状态转移方式生成新个体xnew。

步骤4比较新解xnew与旧解xold的目标函数,根据支配关系和Metropolis准则接受新解,若xnew支配xold,则用xnew替换掉xold,跳出循环;若xold支配xnew,则转步骤2;若两个个体之间相互不支配,则随机选择一个目标函数比较两个个体,并按照Metropolis准则以式(27)接受新解,返回步骤2。

(27)

2.5 算法流程

GWO-SA的算法流程图如图4所示。

图4 GWO-SA算法流程图

3 试验仿真与结果分析

3.1 测试算例

表2 云服务某一时期合作次数

表3 云服务地理距离 km

表4 云服务竞争能力之差

表5 云服务协同效应

图5 FAG磨辊轴承的生产流程

比较以下两个模型下的结果：

(1)模型一：考虑两个优化目标(用户平均满意度和服务协同能力),即本文提出的服务选择模型;

(2)模型二：仅考虑一个优化目标(用户平均满意度),在所提出的GWO-SA基础上求解单目标制造云服务选择与调度模型。

算法运行平台的参数为Intel Core i5-4210M,CPU 2.60 GHz,4 GB内存,在Windows 10系统下采用MATLAB 2018a软件进行试验,试验独立进行20次。种群大小和最大迭代次数设置为100,交叉和变异概率分别为0.9和0.1,T0=50,k=0.05,Maxit=5,pr=0.1,pfmax、pfmin分别为0.5、0.4。

模型一的最终Pareto解集如图6所示。云平台运营者可以从多个解中权衡两个目标函数的重要性,选择合适的决策方案。以用户平均满意度最大的解为例(此时任务平均服务协同能力最弱)与模型二的最优解进行比较,试验结果如表6所示。

表6 模型比较结果

图6 最终Pareto解集

模型二由于过分追求QoS相关的满意度而忽略了服务之间的社会属性,虽然用户平均满意度最优,但是最优解的协同效应基本都明显低于模型一,即单目标情形下云服务的协同能力明显偏弱,其中只有最后一个任务的协同效应略高于模型一的结果。图7和图8展示了两个模型最优解的甘特图。与模型二相比,模型一虽然损失了一部分用户满意度,但模型一由于考虑了云服务的协同效应,第2个任务的2、3、5个子任务在同一个云服务上进行加工,第7个任务的2、3、4个子任务也在同一个云服务上进行加工。这种任务加工方式显然更有利于减少物流运输,从而提高云服务的协同能力以及云制造系统的可持续性。该结果也验证了所提模型的可行性及有效性。

图7 模型一用户满意度最大解甘特图

图8 模型二最优解甘特图

3.2 算法性能分析

为验证所提算法的性能,设计4组试验算例进行比较,各组试验的数据如表7所示。

表7 4组试验信息

每个任务可分解为顺序执行的多个子任务,每个子任务可选择的云服务个数为所有云服务个数的40%～80%,云服务的相关数据服从3.1节中的均匀分布,云服务之间的协同效应服从U(0.6,1)。为了验证GWO-SA的性能,将其与5种多目标进化算法NSGA-II[21]、改进的强度Pareto进化算法(improving the Strength Pareto Evolutionary Algorithm,SPEA2)[22]、进化多目标灰狼优化(Evolutionary Multi-Objective Grey Wolf Optimizer,EMOGWO)算法[23]、离散粒子群模拟退火混合优化(Discrete Particle Swarm Optimization with Simulated Annealing,DPSO-SA)算法[24]、改进的人工蜂群(Improved Artificial Bee Colony,IABC)算法[25]进行比较,算法基本参数设置同GWO-SA,其他参数根据原始文献设置。本文提出的混合算法部分参数设置见3.1节。

本文采用反世代距离[26](Inverted Generational Distance,IGD)和超体积[27](Hyper Volume,HV)两个常用的多目标评价指标对各算法进行比较。IGD衡量算法的收敛性能,HV衡量算法的综合性能。由于问题本身的真实Pareto前沿无法获得,在测试中汇总所有算法的最终结果并进行非支配排序,将得到的非支配解集作为真实Pareto解集。如图9所示为所有算例中各个算法最终的Pareto解的分布情况,从图中可以看出,6种算法中,GWO-SA具有较好的支配性,解的分布更加均匀,尤其对于问题规模较大时展示出的性能更为明显。GWO-SA在4组试验中都产生了高质量的解,说明该算法能够产生更稳定、更有效的解。如图10所示为20次试验中各个算例中6种算法IGD和HV的数值分布情况,其中G、N、S、E、D、I分别表示GWO-SA、NSGA-II、SPEA2、EMOGWO、DPSO-SA、IABC。由图10a可知,4组测试试验中,GWO-SA的IGD值分布情况相比于其他5种算法更小,这说明GWO-SA更接近真实的Pareto前沿,具有更好的收敛性。另外如图10b所示的4组试验中,GWO-SA的HV指标相比于其他5种算法具有更大的值,这反映了GWO-SA良好的多样性和收敛性。

图9 各算例Pareto解集

a IGD值 b HV值图10 算法性能箱线图

4 结束语

以往的制造云服务选择与调度研究大多只考虑云服务的QoS属性。在此基础上,本文面向多用户任务需求,将云服务之间的竞争与合作协同效应引入云服务调度模型中,构建了以最大化用户平均满意度、最大化云服务协同效应为目标的服务选择与调度模型,设计了GWO-SA算法对该模型进行优化求解。结果表明,本文提出的GWO-SA算法能够有效提高Pareto解的质量,该算法在较大规模的算例中可以获得更好的解。同时,比较对模型一和模型二的求解结果可知,考虑协同效应更加贴合实际,能通过影响调度策略进而减少物流运输、增加整个平台中任务执行以及云服务调用的可持续性等。然而,本文所提模型并未考虑云制造平台中制造服务的动态性,为此,在后期工作中可以对动态环境下制造云服务选择与调度优化开展深入研究。