云制造(Cloud manufacturing, CMfg)是一种基于网络、面向服务的智慧化制造模式^[1]。它利用网络和服务平台对制造资源进行统一管理和调度, 高效率、低成本地为用户提供各类按需制造的产品与服务^[2], 因此在面向CMfg服务的生产过程中, 优化云制造资源的调度至关重要。

CMfg服务平台融合并采用了物联网、虚拟化、信息物理系统等资源感知接入技术动态的对产品加工过程中不同粒度的信息进行采集, 实现对各种加工状态进行实时监测与控制。在CMfg资源调度中调度粒度存在两个级别, 分别是制造任务调度初步分解后的子任务级和将子任务继续分解后工序级, 粒度越细, 对加工状态的监测与控制更加精确, 从而提供更专业的面向服务的CMfg。在当前的CMfg资源调度的相关研究领域中, 很多有效的调度模型和调度算法^[3-6]被提出, 但这些研究基于的调度粒度仍停留在子任务级, 没有对工序级的资源调度进行深入研究。

本文针对CMfg资源的分散性、多样性、负载率不均衡性等特点, 提出了基于工序级的多目标CMfg资源调度。目标是以工序级为最小调度粒度为每个制造服务分解后的制造任务申请最合适的CMfg资源, 明确制造任务在制造资源上的加工顺序、加工位置, 使得总体加工时间最短、成本最小以及负载率均衡。粒子群算法(Particle swarm optimization, PSO)虽常用作求解多目标最优解问题, 但易陷入局部最优。因此采用遗传(Genetic algorithm, GA)与PSO结合的混合算法(GA-PSO), 将双层编码后的GA染色体作为PSO中粒子, 通过对其交叉变异操作进行粒子更新, 从而使整个调度过程能快速、准确地收敛于全局最优解。本文提出的调度方案能够很好地解决CMfg资源多目标调度问题, 为制造资源申请企业和提供制造资源企业提供调度结果, 使CMfg环境的资源利用率最大化。

1 CMfg资源特点与调度描述 1.1 CMfg资源特点

(1) 分散性与多样性:CMfg资源种类繁多, 分布在不同地理位置, 相同制造任务的制造时间、制造成本也不尽相同^[7]。因此要求最终的资源调度方案提供高效、低成本的服务。

(2) 负载率不均衡:CMfg资源负载率不平衡, 忙闲不均, 存在周期性或局部性的制造资源过剩^[8]。

1.2 CMfg资源调度描述

CMfg资源调度可以描述为制造任务需求和制造资源能力在所设定的约束条件(时间、成本、负载率)下的动态匹配行为。具体资源调度流程如图 1所示, 在云平台上形成了云资源库与云子任务库。工序级作为云子任务的最小粒度, 在云服务库中有多个候选制造资源, 可在任意候选资源上进行制造服务。为使研究更具有可操作性, 本文作以下假设:

(1) 相同工序在同一制造资源执行;

(2) 工序在制造资源上加工时间, 加工成本是确定的;

(3) 不同制造子任务具有相同的优先级, 而子任务内部可以存在工序约束。

2 多目标优化模型 2.1 目标函数

假定在云平台上有多个制造资源申请, 每个制造资源申请包含N个子任务F_i, i={1, 2, …, N}, 在M个制造资源上加工。每个子任务有P_i道工序。F_ij对应为第i个制造子任务的第j道工序, 有M_ij个可选制造资源。

2.1.1 总制造时间

总制造时间是从用户提出制造资源申请到获得制造资源所花时间, 由制造资源申请分解后所耗时间最长的子任务决定。总制造时间T表达式如下

$ T = \max \sum\limits_{j = 1}^{{P_i}} {\sum\limits_{k = 1}^{{M_{ij}}} {{e_{ijk}}{\eta _i}{t_{ijk}}} } $

其中:e_ijk表示F_ij是否在第k个资源上加工, η_i为F_i所对应的工件数量, t_ijk表示F_ij在第k个资源上加工时间。

2.1.2 总制造成本

总制造成本是从制造资源申请到加工完成所产生的费用总和。总制造成本C表达式如下

$ C = \sum\limits_{i = 1}^N {\sum\limits_{j = 1}^{{P_i}} {\sum\limits_{k = 1}^{{M_{ij}}} {{e_{ijk}}{c_{ijk}}{\eta _i}} } } $

其中:c_ijk表示F_ij在第k个资源上加工成本。

2.1.3 制造资源负载均衡率

制造资源负载均衡率是指制造资源之间负载差异最小。制造资源负载均衡率L表达式如下

$ L = \frac{1}{{\sum\limits_{s = 1}^M {{M_s} - 1} }}\sum\limits_{s = 1}^M {{{\left( {\frac{{{L_s}}}{{C{a_s}}} \times 100\% - \frac{1}{{\sum\limits_{s = 1}^M {{M_s}} }}\sum\limits_{s = 1}^M {{\theta _s}} } \right)}^2}} $

其中:M_s表示第s个制造资源, s={1, 2, …, M}, L_s表示第s个制造资源的负载, Ca_s表示第s个制造资源的可用工时, θ_s表示第s个制造资源的负载率。

2.2 约束条件

(1) 时序约束:制造子任务后续工序的加工开始时间不得超过其前道工序(一个或多个)的加工结束时间, 即

$ {t_{{\rm{en}}{{\rm{d}}_{ij}}}} \le {t_{{\rm{star}}{{\rm{t}}_i}}}\left( {j + 1} \right) $

其中:t_endij表示前置工序的完成时间, t_starti(j+1) 表示当前工序开始时间。

(2) 工序的原子性:制造工序为调度的最小粒度, 一道工序只能占用一个逻辑制造资源, 即

$ \sum\limits_{k = 1}^{{M_{ij}}} {{e_{ijk}}} = 1 $

(3) 交货期约束:所有子任务完成时间不大于项目交货截止时间, 表达式如下

$ T \ge {T_{i\max }} $

其中:T_imax表示F_ij的最晚交货时间。

(4) 制造任务总成本约束:子任务成本总和低于项目的预算成本, 表达式如下

$ C \ge {C_{i\max }} $

其中:C_imax为F_ij的最大预算。

2.3 多目标优化的目标函数

由制造资源调度的总制造时间、成本和负载率的目标函数组成最终目标函数, 表达式如下

$ \begin{array}{*{20}{c}} {F\left( x \right) = \left( {{f_1}\left( x \right),{f_2}\left( x \right),{f_3}\left( x \right)} \right) = }\\ {\left( {\min T,\min C,\min L} \right)} \end{array} $

3 资源调度混合算法的实现

本文提出的GA-PSO混合算法是采用将GA中双层编码方式的染色体作为PSO中粒子, 引入GA的交叉和变异操作, 通过粒子与个体极值或群体极值交叉以及粒子自身变异的方式更新粒子, 从而替代传统PSO中通过跟踪极值来更新粒子位置的方法。这样的做法不仅保持PSO良好的局部搜索性能, 同时还利用了GA良好的全局搜索能力。GA-PSO混合算法流程如图 2所示, 在种群初始化后, 通过适应度函数计算粒子的适应值, 从而进行个体极值和群体极值筛选, 对粒子进行交叉变异等更新操作后再次计算粒子适应值, 更新个体极值与群体极值, 在有限迭代次数之内, 得出最优解。

3.1 编码、解码方式及初始化

染色体编码采用双层编码方式, 个体长度为$2\sum\limits_{i = 1}^{{p_i}} {} {F_{ij}}{M_{ij}}$。其中染色体前半部分表示制造工序在制造资源上加工顺序, 后半部分表示制造工序对应加工制造资源编号。

然后初始化规模为N的粒子群, 在给定可行区域中为粒子群中每个粒子随机指定初始位置, 初始化过程中个体引导者为粒子本身。

3.2 适应度函数

多目标求解最优解有两种解决方案:方案1得到Pareto最优解集; 方案2根据用户需求设置目标权重, 将多目标转化为单目标进行求解得到唯一解^[9-11]。本文采用了一种随机权重相对加权法计算适应度函数, 保持Pareto最优解的多样性和均匀分布性的同时, 还可以找到合理度量意义下的优胜解。适应度函数为

$ \begin{array}{*{20}{c}} {{\rm{fitness}}\left( x \right) = {w_1}\frac{{\min T - {T_{\min }}}}{{{T_{\min }}}} + }\\ {{w_2}\frac{{\min C - {C_{\min }}}}{{{C_{\min }}}} + {w_3}\frac{{\min L - {L_{\min }}}}{{{L_{\min }}}}} \end{array} $

其中:权重${w_i} = \frac{{{r_i}}}{{\sum\limits_{i = 1}^3 {} {r_i}}},{\rm{ }}{r_i}$为非负随机数, 对于T_min, C_min, L_min分别对应只考虑制造时间因素时的最短时间、只考虑制造成本因素时的最低成本和只考虑制造资源负载率因素时的均衡负载。

$ {T_{\min }} = {\rm{fitnes}}{{\rm{s}}_1}\left( x \right) = \min T $

$ {C_{\min }} = {\rm{fitnes}}{{\rm{s}}_2}\left( x \right) = \min C $

$ {L_{\min }} = {\rm{fitnes}}{{\rm{s}}_3}\left( x \right) = \min L $

3.3 粒子更新 3.3.1 交叉操作

交叉操作采用整数交叉法, 针对个体与个体极值交叉、个体与群体极值交叉, 取出粒子的前$\sum\limits_{i = 1}^{{p_i}} {} {F_{ij}}{M_{ij}}$位, 随机选择交叉位置交叉。操作方法如图 3所示:交叉位置为6, 只对个体前$\sum\limits_{i = 1}^{{p_i}} {} {F_{ij}}{M_{ij}}$位进行交叉。

交叉后把某些子任务多余的操作变为子任务工序缺失的操作, 并按交叉前个体的制造资源来调整个体极值$\left( \sum\limits_{i=1}^{{{p}_{i}}}{{}}{{F}_{ij}}{{M}_{ij}}+1 \right)\tilde{\ }2\sum\limits_{i=1}^{{{p}_{i}}}{{}}{{F}_{ij}}{{M}_{ij}}$位的制造资源, 如图 4所示。

3.3.2 变异操作

随机选取变异个体, 选择变异位置Pos 1和Pos 2, 最后把个体中Pos 1和Pos 2位加工工序以及对应的制造资源编号进行调换, 如图 5所示, Pos 1为3, Pos 2为5。

4 算法的实例应用与分析

在前面介绍的高度模型与算法基础上, 作者搭建了用于管理云资源服务调度的云平台。平台通过制造企业发布自身的核心制造资源, 将资源汇集录入云资源地, 在企业面向自身不具备制造能力的制造任务时发布制造服务申请, 云平台通过分解服务申请对应的制造任务, 在云资源池中利用调度算法快速调度匹配对应有制造能力的企业, 满足资源申请企业需要的同时最大化使用了云资源池资源。

由于电梯制造工艺复杂, 流程繁多, 多数中小型电梯制造企业只能生产电梯某核心部件, 不具备生产完整电梯的制造能力。但这些企业可以将各自的制造资源聚集到云平台, 云平台通过整合分散资源形成生产完整电梯能力。以湖州某电梯制造企业为例, 该企业制造能力薄弱, 不具备生产电梯减震装置能力, 因此需要借助云平台, 提交生产电梯减震装置资源申请, 云平台对此申请进行任务分解为如表 1所示有6个制造子任务, 每个子任务对应有不同的工序, 通过在云平台的资源池搜索匹配, 这些工序在云平台上对应10个制造资源可供选择。表 2所示为子任务对应的加工工序。子任务的交货期与预算成本设定如表 3所示。子任务工序对应可加工制造资源如表 4所示。工序在不同制造资源上对应加工时间如表 5所示。工序在不同制造资源上所需加工成本如表 6所示。各制造资源对应的负载度如表 7所示。

根据调度模型及算法, MATLAB编程运算。为了评估GA-PSO混合算法的性能, 在相同实验条件下, 采用传统GA作为对比实验。初始化参数如下:迭代次数为200, 种群规模为100, 初始交叉概率为0.8, 变异概率为0.3。GA-PSO和传统GA求解的最优解变化曲线如图 6所示。对比结果表明, 相对于传统GA, GA-PSO具有更快收敛速度与全局探索。传统GA在迭代40次左右陷入了局部最优, 并最终收敛于最优解223, GA-PSO混合算法在迭代次数为30时收敛于全局最优解219。可以得出, GA-PSO的收敛性和局部探索能力均优于传统GA。

最终得出的最优调度方案如图 7所示。其中子任务1在总体加工4 h后开始, 第一道工序在编号为5的资源上进行, 第二道工序在编号为6资源上进行。所有制造任务在50 h后完成。

5 结束语

针对云制造资源的特点, 以工序级为最小调度粒度, 综合考虑云制造资源调度的主要影响因素, 以制造时间最短、制造成本最小以及制造资源负载率均衡为多目标, 构建一个云制造资源的多目标调度优化模型。提出基于GA-PSO的混合云制造资源调度算法, 结合利用了有较好全局搜索能力的遗传算法和具有局部搜索能力优势的粒子群算法, 使整个调度过程在最短时间内收敛于全局最优解。最后以湖州某电梯制造企业的生产订单为例进行实验, 结果证明了该算法可以有效解决云制造资源的多目标调度问题。