云制造智能车间机床资源的再分配服务模型与解算

张富强, 李植新, 张金源

(1.长安大学道路施工技术与装备教育部重点实验室, 西安 710064; 2.长安大学智能制造系统研究所, 西安 710064)

云制造是一种使用云计算技术和物联网,面向服务的网络化智能制造新模式,通过满足客户的需求,来为他们所需的产品找到合适的服务[1-3]。依据中国中小型制造企业数目众多、资源利用率不高、地理位置分散、资金投入不足和供需信息不对称等困境,云制造模式鼓励企业将闲置制造资源共享实现涵盖产品全生命周期的设计、制造、物流、服务和管理等网络化协作,变革传统工业生产运营方式,重构产业价值链,提高企业核心竞争力。当前,各个企业也开始智能制造转型的探索实践,同时,海尔COSMOPlat、航天云网INDICS+CMSS平台等工业物联网平台已经落地实施,推动着工业体系的网络化变革。因此,基于云制造模式下的智能车间管控问题显得尤为重要[4]。

云制造智能车间是在云制造的环境下,对原有的车间进行数字化、网络化和智能化升级重构。由于云环境下资源类型更加多样化,资源管理形式更加合理,资源分布更加广泛,资源实时共享性强,云制造技术与传统车间相结合形成云制造智能车间,利用智能优化算法对其进行优化处理,获得更好的调度方案,在经济和效益上都得到很大的提升。

针对云制造智能车间的研究,鲁建厦等[5]考虑混流装配与零部件加工的集成优化以及外协云任务与自制任务的协同调度,设计了一种两级递阶结构的混合生物地理学优化算法。董海等[6]考虑柔性车间零件加工的优化及云任务与自生产任务的协同调度,提出一种改进的烟花算法来进行多目标求解。许春安等[7]构建了云环境下代表制造资源需求企业和云平台运营方利益的多目标优化资源配置模型,并提出一种改进的NSGA-Ⅱ算法对该模型进行求解。Gao等[8]提出一种基于Pareto的分组离散和声搜索算法优化最大完工时间和提前和延误的时间平均值,并嵌入基于关键路径和截止日期的两种局部搜索方法,以提高开发能力。综上,当前关于智能车间的混流生产研究较多,但对线下/线上订单共存情况下的产线均衡问题研究较少。

结合云环境下的智能化制造车间特点,本文以线下/线上订单共存情况下机床资源再分配为对象进行研究,以各工件在机床上加工的最大完工时间最短、机器总负荷最小、加工成本最低为多目标函数,以机床均衡率为综合评判函数,构建了一种机床资源再分配服务模型,并采用基于Pareto外部档案的多目标教与学优化(multi-objective teaching and learning based optimization,MOTLBO)算法对上述模型进行了多目标优化。

1 机床资源再分配服务问题描述

云制造智能车间机床资源再分配服务问题可描述为:假设K个线下/线上批次零件在M台机床上加工,每个批次零件都有N道加工工序,每道加工工序都有多台性能不同的候选机床可以选配。并假设以下条件成立:①每台机床每次只能加工一个批次零件；②不同批次零件的工序之间相互独立,没有先后约束；③每个批次零件都是从指定的原材料库存运输至待加工机床缓存处,加工完毕后运至指定的成品库；④每台机床前后的批次零件存放缓冲区的容量都足够大；⑤如果机床有加工任务冲突,则机床完成当前加工任务后,才能执行下一道加工任务。

2 机床资源再分配服务模型

机床资源再分配服务的目标为在给定的上述假设条件下,找到一种可行的方案,使各批次零件加工任务的最大完工时间最短、机器总负荷最小、加工成本最低。根据该规划目标,其具体的数学模型描述如下。

2.1 变量定义

线下/线上批次零件个数设为K；工件加工工序设为N；候选机床个数设为M。

①加工任务集N={J1,J2,…,JK},i表示线下/线上批次零件的标识(1≤i≤K)；②加工任务Ji包含JNi道工序,j表示批次零件i加工工序的标识(1≤j≤JNi)；③加工工序Pi,j为任务Ji的第j道工序,则Pi={Pi,1,Pi,2,…,Pi,JNi}；④候选机床集M={M1,M2,…,Mm},m表示被选中的候选机床标识(1≤m≤M)；⑥Mti,j(fm)表示加工任务Ji的工序Pi,j在机床fm上的耗费时间；⑦Fk表示第m台机器的动态耗费率,即每台机器加工工件的运行成本;⑧工件i未在工序j的第m台机床上加工时Xijm=0,工件i在工序j的第m台机床上加工时Xijm=1。

2.2 目标函数

(1)Fti表示任务i的最后完工时间,F1表示最小化最大完工时间:

(1)

(2)加工过程所使用的生产成本F2:

(2)

(3)机器的总负荷F3:

(3)

2.3 约束函数

①K>M表示批次零件任务数大于加工机床数；②Sti,j(fm) ≥Stx,y(fm)+Mtx,y(fm)表示同一时间两道不同的工序不能在同一机床上加工；Stx,y(fm)表示此机床前加工任务的开始加工时间节点；③Ftk≤Ltk表示最终规划时间不能超过批次零件k的交货期。

2.4 综合评判函数

加工机床m再分配均衡率MTum=机床m的有效加工时间/加工任务最大完工时间,即

(4)

3 多目标教与学算法

云制造智能车间机床资源再分配服务问题属于典型的组合优化问题,可采用智能算法进行求解。当前主流的基于进化和群体智能的优化算法都需要共同的控制参数,如种群大小、世代数、精英大小等,而不同的算法除了一般的控制参数外,还需要各自特定的算法参数。例如,遗传算法使用变异概率、交叉概率和选择算子；粒子群算法使用惯性权重和社会认知参数；ABC算法使用蜜蜂数量(侦察、旁观者和使用)和限制；NSGA-Ⅱ需要交叉概率、变异概率和分布指数。适当地调整这些算法的参数是影响算法性能的一个非常关键的因素。对特定于算法的参数进行不适当的调整,要么会增加计算工作量,要么产生局部最优解。除了对特定于算法的参数进行调优外,还需要对常用的控制参数进行调优,从而进一步提高工作效率。而教与学优化(teaching and learning based optimization,TLBO)算法是一种基于迭代的全局搜索技术,不需要任何特定于算法的参数且求解效率高。因此,采用教与学算法对工序物流集成规划多目标模型进行求解。

3.1 编码与解码

涉及的问题是在智能车间中多个线下/线上批次零件的多个工序在多台机床上加工的问题,其中涉及的问题是工序和机床两方面,采用分层的方式,第一层为工序层,其长度代表工件的工序数,第二层为机器层,代表每个工序所需的机器,如图1所示,第一层的第一个数字2即表示该工件的工序2的第一道工序,第二个数字2表示工序2的第二道工序,第二层即表示加工工序所需的机器。

解码就是将每个学生所包含的信息转化为对应的解,上述的学生编码中,假设每道工序所需时间相同,即可得到如图2所示,横坐标表示加工时间,纵坐标为机器数。

图1 一个学生编码Fig.1 A student code

图2 学生解码结果Fig.2 Student decoding results

3.2 外部档案

外部档案用于保存和更新获得的最佳解决方案[9]。为适当控制外部存档的解集空间及解集的多样性与分布性,MOTLBO算法采用非支配排序和拥挤距离机制,对学员进行更新和比较挑选出优秀的精英个体。外部存档的具体步骤如下。

在初始阶段,随机生成一个初始种群,其中包含N个解(成员)。然后根据非优势概念和拥挤距离机制对初始种群进行排序。将所得解集保存在外部档案中, 用Li(i=1,2,…,n)表示成员在档案中的位置数组,在归档过程开始时,当前填充的第一个非支配前沿被添加到外部归档中。 在随后的迭代中,将档案成员a的位置数组La与当前总体中的个体b的位置数组Lb进行比较。 根据以下规则,比较结果更新存档。

①如果位置数组La支配Lb,则保持a存档并拒绝b；②如果Lb支持任何档案成员的La,然后b替换外部存档中的a；③当Lb对所有档案成员的La不支配时,b被接受为新的档案的成员; ④当a和b具有相同的位置向量,两个人占据相同的存储。 检验了两种解决方案之间的优势关系,并且删除了已解决的解决方案,将其他解决方案保留在存档中。

3.3 非支配排序

非支配排序用每一个解决方案与其他的解决方案想比较,以确定他们之间的主导地位,通过主导地位对所有解决方案进行排序[9]。对于每个解i,需要计算三个数值:它的主导地位Zi,支配i的解集Si,它的基数Ni。这个过程执行结束后,处在第一等级非支配前沿(Rank=1)的所有的解所对应的Ni=0。然后,对于每个对应的Ni=0的解,将其支配的解集中的每一个解所对应的Ni设置为-1。如果有任何一个解所对应的Ni变为零,就把这一个解放入一个单独的集合F中。F中的这些解就属于第二等级的非支配前沿(Rank=2),上述过程对集合F中的每一个解依次执行得到第三等级的非支配前沿(Rank=3)。该过程持续循环,直到确定所有前沿。

3.4 拥挤距离机制

在非支配排序操作完成后,将所有解按照升序在同一个非支配前沿进行排序目标函数值的次序。然后将任意维上目标函数值最大或最小的解距离设置为无穷大。对于其他中间解,计算每个目标函数的绝对归一化差值作为距离值,并对两边的两个相邻解进行估计。这些绝对归一化差异在所有客观函数中的总和就是一个解的拥挤距离值。在计算拥挤距离之前,对每个目标函数进行归一化。

3.5 MOTLBO流程

算法的基本流程如下,流程图如图3所示。

图3 MOTLBO流程图Fig.3 MOTLBO flow chart

步骤1 输入:人口规模N,最大函数评估g,目标函数信息Q。

步骤2 初始化学生、设计变量和设计终止条件,在目标空间内随机生成第一个总体。

步骤3 计算各设计变量的均值(学习成绩)。

步骤4 对学生规模N进行非优势概念和拥挤距离机制对初始种群进行排序。将所得解集保存在外部档案中。

步骤5 教学阶段。

(1)选取总体成绩最好的Xtotal-kbest,i作为教师。

(2)利用式(5)、式(6)进行教学：

Di,j,k=ri(Xj,kbest,i-TfMi,j)

(5)

Tf=round[1+rand(0,1){2-1}]

(6)

式中:Di,j,k为现有各科平均成绩与教师对应各科成绩的差值,Xj,kbest,i为j学科中的最好学习者；Mi,j为j学科的平均成绩,ri是区间[0,1]中的随机数。

(3)评估学员的学习成绩,选取成绩好的进行更新。

步骤6 学习阶段。

(2)利用式(7)、式(8)进行对比学习：

X″j,P,i=X′j,P,i+ri(X′j,P,i-X′j,Q,i),

IFX′total-P,j

(7)

X″j,P,i=X′j,P,i+ri(X′j,Q,i-X′j,p,i),

IFX′total-Q,j

(8)

(3)评估学员的学习成绩,选取成绩好的进行更新。

步骤7 基于拥挤度和非支配排序,在当前学习者群体与外部精英档案中选择N个学习者。

步骤8 若算法没有满足终止条件,则转到步骤5。

4 案例仿真

为验证所提出MOTLBO算法求解多目标机床资源再分配服务模型的正确性,设计如下实例进行仿真、验证与分析。

4.1 初始条件与参数

以文献[10]中的标准问题作为算例,简化为一个8×7的车间调度问题。表1所示为6个线下批次零件和2个线上批次零件在7台机器上的加工时间数据,8个批次零件各具有2道或者3道加工工序,每个批次零件都对应着不同的加工路径。表2为每台加工机床所需的成本。参数设置如下:学生数取100,迭代次数200,目标函数设置为3,采用最大生成作为停止准则。基于MATLAB软件,通过GA和MOPSO算法最终进行比较,来验证MOTLBO算法的有效性。

表1 各加工任务的工艺路线Table 1 Process route for each processing task

表2 机器对应的加工成本Table 2 Processing costs corresponding to the machine

4.2 仿真结果与分析

MOTLBO算法运行的25组pareto解集如表3所示。选取1组解展示甘特图,如图4所示。

p(i,j)为第i个工件的第j道工序图4 序号1对应的甘特图Fig.4 Gantt chart corresponding to serial number 1

表3 25组pareto解集Table 3 25 sets of pareto solution set

图5描述了25组pareto求解结果的平均资源再分配均衡率评价。可知除了机床6的资源再分配均衡率较低外,其他资源的再分配均衡率都满足再分配均衡性要求。原因是机床6属于特种加工机床,只满足特定工序的加工要求,不适于通用加工。综合来看,MOTLBO算法具有较好的相对适应性。

图5 平均资源再分配均衡率评价Fig.5 Average resource redistribution equalization rate evaluation

表4 算法对比Table 4 Algorithm comparison

为了验证MOTLBO算法的性能,与其他算法进行对比分析。运行25次取平均值。它们的平均值比较结果如表4 所示。

从表4结果看,MOTLBO算法对比与GA算法有很大的提升,对比MOPSO算法有较小提升,最大完工时间分别缩短4.5、0.54 h,机器总负荷分别减少30.1、1.06 h,加工成本分别节约402.84、16.6元/h,由于是三个目标函数优化,pareto解集构成一个三维曲面,可用图直观地表示可行解,如图6所示。对比GA算法,MOTLBO的搜索空间较广,对比MOPSO算法,MOTLBO的pareto前沿较好。

图6 3种算法的最佳结果可视化Fig.6 Visualization of the best results of the three algorithms

5 结论

提出并建立了一种支撑多品种、小批量、强交货期的柔性生产方式下云制造智能车间机床资源再分配服务模型。以各加工任务最短完工时间、机器加工成本、机器总负荷为多目标,以资源再分配均衡率为评价因素,并采用多目标教与学优化算法进行了求解。其中,MOTLBO的核心思路是在确定学生情况下(即确定工艺路线),搜索出较优的学生(即教师),进而对其他学生进行迭代搜索出全局最优。仿真案例的结果表明MOTLBO算法在收敛性和求解效率等方面具有较大优势,为云制造智能车间的生产规划提供了一种有效的解决方法。