0 概述

云制造作为智能制造的重点研究领域, 自提出以来受到国内外学者专家的广泛关注^[1]。云制造是在“制造即服务”理念的基础上^[2], 借鉴云计算思想, 结合物联网技术, 实现制造资源高度共享的一种网络化制造新模式。

调度问题是云制造系统的核心问题之一^[3]。目前, 针对计算资源和计算服务调度问题的研究已非常成熟, 不同的智能优化算法被用于解决云环境下的计算资源任务分配和负载均衡等问题^[4-6]。但是针对云环境下制造资源、服务优化调度方面的研究仍然较少, 作为一个致力于满足用户个性化需求的以用户为中心的制造资源共享平台^[7], 如何为服务需求方从众多候选云服务中找到反映用户偏好, 方便可靠且质优价廉的服务, 一直是云制造任务调度研究的热点问题。

目前, 关于考虑用户偏好的云制造任务调度的研究较少, 其主要利用权重分配策略与启发式线性调度算法相结合的简单加权法。如:文献[8]根据用户偏好信息为目标分配偏好优先级, 据此获得量化的偏好权重, 并采用改进的免疫克隆算法获得最优调度方案; 文献[9]将用户提出的个性化任务要求分为功能性和非功能性两类, 据此获得更准确的用户偏好权重, 并采用改进的遗传算法获得最优调度方案; 文献[10]进一步考虑用户不同偏好的影响深度, 采用直觉模糊熵权法获得用户偏好权重, 并采用生物地理优化算法获得最优调度方案。然而, 用户偏好在应用中通常以定性的方式提供, 很难预先确定哪组定量权重是最合适的, 线性调度算法最终只提供一个最优解, 不能为决策者在实际决策中提供备选方案。

为解决上述问题, 研究者采用多目标优化算法求解云制造资源调度问题, 如多目标粒子群优化(Multi-Objective Particle Swarm Optimization, MOPSO)算法^[11-12]、改进的带精英策略的快速非支配排序遗传算法(Improved Non-dominated Sorting Genetic Algorithm-Ⅱ, NSGA-Ⅱ)^[13-14]等, 同时优化多个目标, 获得Pareto最优解集, 帮助用户选择折中解决方案。然而, 多目标优化算法通常以同等的优先级优化所有调度目标, 存在满足用户偏好的最佳解决方案可能不会出现在最初的Pareto最优解集中的问题。为此, 本文通过扩展非支配排序生物地理优化(Non-dominated Sorting Biogeography-based Optimization, NSBBO)算法, 提出一种反映用户偏好的任务调度算法(User Preference Task Scheduling Algorithm, UPTSA)。

1 问题描述 1.1 云制造任务调度流程

云制造环境下的任务调度过程, 从用户发出任务请求到完成制造任务, 主要经历任务分解、服务发现、调度决策3个阶段。具体步骤如下:

1) 任务分解:将提交的制造任务Task分解为M个子任务ST, 即Task={ST¹, ST², …, ST^j, …, ST^M}, 其中, ST^j表示第j个子任务, M为制造子任务总量。

2) 服务发现:针对各个子任务, 选取所有符合用户功能要求的制造服务CMS组成相对应的候选服务集MCSCS, 即MCSCS^j={CMS₁^j, CMS₂^j, …, CMS_i^j, …, CMS^j_Kj}, 其中, MCSCS^j表示第j个子任务的候选服务集, CMS_i^j表示第j个子任务候选服务集中的第i个候选服务, K_j为第j个子任务的候选服务集中的候选服务总量。

3) 调度决策:根据用户非功能性要求, 从每个子任务候选制造服务集中选出最优的制造服务, 生成$ \prod\limits_{j=1}^{M} K_{j}$种可能的调度方案, 利用多目标优化算法获得一组最优调度方案。

1.2 多目标优化问题的数学模型

本文从用户需求的角度出发, 将服务需求方主要关注的完工时间、成本、质量作为目标函数来构建云制造任务调度模型。

1.2.1 目标函数

目标函数具体如下:

1) 时间最少

$ \min T = {T_{{\rm{process}}}} + {T_{{\rm{transp}}}} = \sum\limits_{i = 1}^n {\left[ {{T_{{\rm{process}}}}(i) + {T_{{\rm{trass}}}}(i)} \right]} $

(1)

其中, T_process(i)为第i阶段所选制造服务的执行时间, 当i=1, 2, …, n-1时, T_transp(i)为第i阶段到第i+1阶段所选制造服务间的物流时间, T_transp(n)为最后一个制造子任务完成后将产品交付给制造需求方的物流时间。

2) 成本最低

$ \min C = {C_{{\rm{process}}}} + {C_{{\rm{transp}}}} = \sum\limits_{i = 1}^n {\left[ {{C_{{\rm{process}}}}(i) + {C_{{\rm{transp}}}}(i)} \right]} $

(2)

其中, C_process(i)为第i阶段所选制造服务的执行成本, 当i=1, 2, …, n-1时, C_transp(i)为第i阶段到第i+1阶段所选制造服务间的物流成本, C_transp(n)为最后一个制造子任务完成后将产品交付给制造需求方的物流成本。

3) 质量最高

$ \max Q = \sum\limits_{i = 1}^n {{Q_{{\rm{process}}}}} (i)/n $

(3)

其中, Q_process(i)为第i阶段所选制造服务完成相应制造任务的可靠性。

1.2.2 约束条件

云制造环境下执行制造总任务的时间T, 不能超过制造需求者所规定的最长交货期限T_max, 即:

$ T \le {T_{\max }} $

(4)

云制造环境下完成制造总任务所花费的成本C, 不能高于制造需求者所能接受的最高成本C_max, 即:

$ C \le {C_{\max }} $

(5)

云制造环境下每个制造服务的质量, 均不低于制造需求者所要求的最低质量Q_min, 即:

$ {Q_{{\rm{process}}}}(i) \ge {Q_{\min }},\forall i \in \left\{ {1,2, \cdots ,n} \right\} $

(6)

制造服务需求方的总体目标是以完工时间最短、完工成本最低、完工质量最高完成制造总任务。综合上述目标函数和约束条件, 同时为便于后续利用算法求解该问题, 可将云制造环境下任务调度多目标优化问题的数学模型描述为:

$ \begin{array}{*{20}{l}} {{\rm{ s}}{\rm{.t}}{\rm{. }}\min F = {{\left[ {T,C,\left( {10 - R} \right)} \right]}^{\rm{T}}}}\\ {\;\;\;\;\;\;T \le {T_{{\rm{max }}}}}\\ {\;\;\;\;\;\;C \le {C_{{\rm{max }}}}}\\ {\;\;\;\;\;\;{Q_{{\rm{process}}}}(i) \ge {Q_{{\rm{min}}}},i = 1,2, \cdots ,n} \end{array} $

(7)

2 算法求解 2.1 NSBBO算法的改进

NSBBO算法是一种模拟生物地理学演化的非支配排序多目标优化算法^[15]。该算法已应用于无线网络规划优化^[16-17]与车间调度^[18-19]等方向, 且相较于其他现有多目标算法, 解集具有更好的收敛性和多样性^[20]。

2.1.1 栖息地编码

本文采用实数编码的方式, 设NSBBO中的每个栖息地表示一个可行解, 每个栖息地包含一个由适宜度变量(Suitability Index Variables, SIVs)构成的栖息地适宜度向量(Suitability Index Vector, SIV), 其代表分解子任务的类别。一个栖息地的适宜指数越高代表解决方法越好, 反之亦然。

定义1  第r个栖息地表示为H_r=(h_{r, 1}, h_{r, 2}, …, h_{i, j}, …, h_{r, Kj}), h_{i, j}为该调度方案对应的第j个候选制造服务集中制造服务的序号(索引), 其取值为一个离散的值域{h_{i, j}:0 < h_{i, j}≤K_j}。

图 1为云制造任务的栖息地编码实例。该制造任务由5个子任务协同完成, 执行第1个子任务时, 从其候选制造服务集MCSCS¹中选择第2个制造服务CMS₂¹, 则SIV中的第1个SIVs赋值为2。以此类推, 可以得到对应的栖息地个体表示(2-3-1-4-6)。

2.1.2 移民操作

移民操作通过分享具有高适宜度值的栖息地的信息或特征来改善其他具有较低适宜度值的栖息地。在移民过程中有2个重要参数, 即移入率λ_r和迁出率μ_r。

本文设计了一个梯形迁移率计算模型, 通过对拥有高适宜度的1/4个体和低适宜度的1/4个体采用统一移民率, 避免了少数拥有高适宜度的解决方案占主导地位而导致过早收敛, 扩大了对相邻空间的搜索。

传统线性模型为:

$ {\lambda _r} = I\left( {1 - \frac{{V(r)}}{N}} \right) $

(8)

$ {\mu _r} = E\frac{{V(r)}}{N} $

(9)

梯形模型为:

$ {\lambda _r} = \left\{ {\begin{array}{*{20}{l}} {I,V(r) \le {i_0}}\\ {2I\left( {1 - \frac{{V(r)}}{N}} \right),{i_0} < V(r) \le N} \end{array}} \right. $

(10)

$ {\mu _r} = \left\{ {\begin{array}{*{20}{l}} {2E\frac{{V(r)}}{N},V(r) \le {i_0}}\\ {E,i < V(r) \le N} \end{array}} \right. $

(11)

其中, I和E分别表示最大移入率和最大迁出率, N表示物种的最大数量, V(r)表示第r个栖息地的种群数量, i₀是大于等于(N+1)/2的最小整数。

以图 2为例进行栖息地的迁移, 选择第r个栖息地H_r(2-3-1-4-6)进行移民操作, 根据移入率λ_r生成一组二进制掩码字符串(0-1-0-1-1), 其中, 1表示该栖息地目前的SIVs将迁出, 0表示相反含义。因此, 在H_r中的第2、4和5个SIVs将被迁出的栖息地H_u中相应的SIVs所取代, 而剩余的SIVs将保持不变。基于迁出率μ_r概率性地选择迁出的栖息地H_r(3-1-2-3-4), 得到迁移后的栖息地为(2-1-1-3-4)。

2.1.3 突变操作

突变操作根据变异概率随机地改变栖息地中的SIVs以提高物种的多样性。栖息地的变异概率计算公式如下:

$ m(V) = {m_{\max }}\left( {1 - \frac{{{P_V}}}{{{P_{\max }}}}} \right) $

(12)

其中, m_max表示最大变异概率, P_V表示栖息地物种数量为V的概率, P_max表示所有栖息地中P_V的最大值。

以图 3为例进行栖息地的变异, 选择第r个栖息地H_r(2-1-3-4-6)进行变异操作, 根据变异率, 栖息地中的第1、2和5个SIVs将被新的SIVs所取代, 新的SIVs是从相应的候选制造服务组中随机选择的制造服务序号。

2.2 基于改进NSBBO的任务调度算法 2.2.1 权重系数获取

本文采用权重均匀分配策略, 根据定性的用户偏好获得一组权重数组。通过预先计算输入域的各个子域, 将每个优化目标的权重域作为输入域的笛卡尔积, 保证了均匀性选择权重, 具体步骤如下:

步骤1  设置一个除数参数d, 并初始化一组空的权重数组WD。

步骤1  将整个输入域分成d³种等效的子域。

步骤3  判断各个子域是否满足约束条件集C, 若不完全满足, 则采用系统驳斥消除该子域。

步骤4  从剩余子域中随机挑选一个子域, 并生成符合约束集C的一组均匀权重数组。

步骤5  返回生成的权重数组WD={w₁, w₂, w₃}, 用作分配给优化目标的权重。

2.2.2 偏好度定义

定义用户的偏好度θ, 基于用户对各个优化目标的定性偏好评估特定调度方案的质量, 取代NSBBO算法中原有的拥挤距离评估法。优化目标时间最短、成本最少和质量最高分别表示为o_time值最小化、o_cost值最小化和o_quality值最大化, 调度方案s的偏好度计算公式为:

$ \begin{array}{l} \theta (s) = {w_1} \times Norm \left( {1 - {o_ - } time (s)} \right) + \\ \;\;\;\;\;\;\;\;\;\;{w_2} \times Norm \left( {1 - {o_ - } cost (s)} \right) + \\ \;\;\;\;\;\;\;\;\;\;{w_3} \times Norm \left( {{o_ - } quality (s)} \right) \end{array} $

(13)

其中, Norm(x)=[x/(x+1)]。偏好度越高, 代表单个调度方案的质量越高。

2.2.3 算法流程

基于改进NSBBO的任务调度算法具体步骤如下:

步骤1  随机生成一个包含N个栖息地的初始种群pop。

步骤2  设置代数t=1, 种群P_t=pop。

步骤3  设置后代种群Q_t=∅。

步骤4  通过对P_t中的栖息地进行移民和突变操作得到新的种群, 并添加到后代种群Q_t中。

步骤5  结合种群P_t和后代种群Q_t得到双倍大小的新种群R_t。

步骤6  基于NSBBO中的非支配排序算法将R_t中的栖息地排序, 并根据等级分成多个部分F={F₁, F₂, …, F_n}。

步骤7  设置i=1、P_t+1=∅。

步骤8  判断是否符合条件|F_i|+|P_t+1|≤N, 若符合, 则将F_i添加到P_t+1中, 并令i=i+1;若不符合, 即F_i不能完全添加到P_t+1中时, 则停止添加。

步骤9  根据权重均匀分配策略, 生成为目标函数所需且满足所有用户偏好的权重集w={w₁, w₂, w₃}。

步骤10  使用生成的权重集, 计算θ(s)的值, 并将该值分配给属于F_i中的每个栖息地。

步骤11  根据θ(s)的值对F_i中的每个栖息地进行升序排序, 选择最好的精英栖息地形添加到P_t+1中, 直至|P_t+1|=N, 停止添加。

步骤12  判断算法终止条件, 若满足, 则输出最优种群; 若不满足, 则令t=t+1, 跳转到步骤3。

3 实例验证 3.1 用户偏好调度实例

通过一个实例来验证本文提出的UPTSA算法的可行性和有效性。该实例包含48个制造企业, 共提供6种类型的144个制造服务。企业提供的制造服务能力如表 1所示(其中“—”表示该企业不提供此类制造服务)、企业间的物流距离如表 2所示。假设云制造平台现有服务需求者提交了100个具有不同用户偏好的3种类型的制造任务, 具体任务类型和用户偏好如表 3所示, 其中w_t、w_c和w_q分别为制造任务完工时间、成本和质量所占权重。

3.2 实例求解与结果分析 3.2.1 实验环境

硬件环境:实验使用的电脑为DELL台式电脑, CPU为Intel(R) Core(TM) i5-4460S, 主频2.90 GHz, 内存容量为4.00 GB。

软件环境:实验使用的操作系统为Windows 10(64位), 编程软件为Matlab R2016a。

参数设定:设置算法初始种群大小为50, 最大迭代次数为200, 改变概率为0.98, 最大迁入概率为1, 最大迁出概率为1, 最大变异概率为0.1。

3.2.2 可行性分析

为验证UPTSA算法的可行性, 从制造任务完工时间、成本和质量三方面将UPTSA算法与另外3种单目标最优调度策略进行对比分析, 分别为完工成本最小调度策略(MinC)、完工时间最短调度策略(MinT)和完工质量最高调度策略(MaxQ)。

从图 4可知, UPTSA算法生成的调度方案集的平均任务完工时间与MinT基本一致, 且低于MinC和MaxQ。从图 5可知, UPTSA算法生成的调度方案集的平均任务完工成本与MinC基本一致, 且低于MinT和MaxQ。从图 6可知, UPTSA生成的调度方案集的平均任务完工质量低于MaxQ, 且高于MinT和MinC。对比结果表明, UPTSA算法在考虑用户偏好的同时, 尽可能搜索成本低、完工快、质量高的制造服务, 从而验证其可行性。

3.2.3 有效性分析

为验证UPTSA算法的有效性, 从调度结果与用户偏好两方面将UPTSA算法与其他多目标优化算法进行对比分析, 分别为MOPSO^[12]、NSGA-Ⅱ^[10]、NSBBO^[19]和本文改进的NSBBO(Improved NSBBO, INSBBO)算法, 可以得到5种算法在求解云制造环境下考虑用户偏好的任务调度问题的最短时间平均值、最低成本平均值、最高质量平均值和Pareto最优解集中完全非支配解的平均个数。

选取同一种任务类型但具有代表性的3种用户偏好的制造任务的不同算法调度结果进行对比分析, 对比结果如图 7所示。其中, A代表NSGA-Ⅱ, B代表MOPSO, C代表NSBBO, D代表INSBBO, E代表UPTSA。3个制造任务分别是:1)制造任务1, 任务类型1, 用户偏好为w_c>w_t>w_q; 2)制造任务45, 任务类型1, 用户偏好为w_t=w_c=w_q; 3)制造任务77, 任务类型1, 用户偏好为w_c=w_q>w_t。

由图 7(a)~图 7(c)可知, 在制造任务1中, UPTSA和NSGA-Ⅱ的成本最低, 虽然UPTSA的平均质量相比NSGA-Ⅱ低, 但UPTSA的完工时间更短, 该对比结果表明当3个调度目标偏好度均不同时, UPSTA算法调度结果较优, 且更符合用户偏好。由图 7(d)~图 7(f)可知, 在制造任务45中, 除MOPSO算法外, 其他4种算法调度结果只存在微小偏差, 该对比结果表明当3个调度目标偏好度相同时, UPTSA算法调度结果相对来说更好。由图 7(g)~图 7(i)可知, 在制造任务77中, UPTSA的平均完工成本最低, 虽然UPTSA的平均完工时间略高于INSBBO, 但在平均完工质量上, UPTSA比INSBBO高12%左右, 该对比结果表明当3个调度目标中仅有2个偏好度相同时, UPSTA算法调度结果较优, 且更符合用户偏好。

由图 7可知, INSBBO算法相较于传统NSBBO算法, 得到的Pareto最优解集中解的平均质量更优, 该对比结果表明本文设计的梯形迁移率计算模型可以扩大对相邻空间的搜索, 避免其陷入局部最优解, 提高寻优能力。

综上所述, 基于INSBBO扩展的UPTSA算法继承了INSBBO较强的寻优能力, 且能更好地满足云制造环境下高度个性化的用户需求, 具有较好的实际应用价值。

4 结束语

本文基于改进的NSBBO算法, 提出一种反映用户偏好的任务调度算法, 根据定性的用户偏好搜索调度方案, 最终为服务需求者提供一组帮助其决策的调度方案集。实例分析结果表明, 该算法能有效求解云制造环境下考虑用户偏好的任务调度问题, 且与其他多目标搜索算法相比, 能更充分体现用户偏好, 实用性强。下一步将对高维多目标优化问题进行研究, 考虑企业间的合作关系, 构建新的多目标调度模型, 为资源需求者提供更优质的云服务。