考虑多时间因素的绿色柔性作业车间动态调度*

卫少鹏，王 婷，2，周 彤

(1.贵州大学管理学院，贵阳 550025；2.贵州省互联网+协同智能制造重点实验室，贵阳 550025)

0 引言

随着精益生产的盛行，制造业在生产过程中对质检的应用越来越广泛。为了减少残次品的数量，绿色柔性作业车间调度需要对关键工件的特殊工序穿插质检环节。质检环节使得紧邻工序间隙较大，造成机器空转能耗较高，尤其是返修、报废等问题的存在，严重影响了生产过程的流畅性，极大扰动了原始生产计划。绿色动态车间调度基于事件驱动的重调度策略，通过重新调整工件的加工顺序，同时匹配高效率、低能耗的加工机器，从而达到节能减排、按时交货的双重目标。

当前，国内外学者对柔性作业车间动态调度的研究成果较为丰富。Nouiri M等[1]针对机器故障问题提出了一种动态节能调度；张守京等[2]针对重调度问题提出了免疫度概念；成荣荣等[3]基于完工时间和总成本指标进行建模，分别对4类动态事件设计了重调度策略；孙丽珍等[4]针对工件批量加入和机器故障问题的重调度问题采取了改进的遗传算法进行求解；Liu B等[5]设计了一种快速分布估计算法带有模糊时间的柔性作业车间动态调度问题；李聪波等[6]建立了多目标重调度节能优化模型，引入多目标引力搜索算法进行求解；王雷等[7]引入了可变重调度区间策略，避免了重调度和原调度方案差别过大；陈超等[8]提出了一种退火遗传算法求解动态节能调度问题；刘燚等[9]将事件驱动策略和滚动窗口技术应用于动态调度问题。

综上所述，以往的动态调度研究仅关注加工环节的相关指标优化，较少考虑到辅助加工时间的影响，如：调整时间、质检时间。辅助环节对生产系统的效率和能耗均有较大影响，探明其影响机理极其重要。鉴于此，以下动态车间调度选取最大完工时间和机器总能耗为优化指标，同时考虑机床辅助环节的调整时间和质检时间，建立了绿色动态车间调度模型，用线性加权法将多目标转化为单目标。采用新型群体智能算法—头脑风暴算法进行求解，对编码环节进行改进，引进了转换机制，设计了多层编码方式，有效提高了最优解的收敛速度和精度。

1 问题描述与数学建模

1.1 问题描述

考虑多时间因素的柔性作业车间绿色动态调度描述如下：假设n个工件在m台机器上加工，每个工件有h道工序，所有工序按照固定的工艺路线在柔性机器上完成操作。其中，所有工序Ojh在加工之前要考虑调整时间，部分关键工序在加工前要同时考虑调整时间和质检时间。

在生产过程中，机器的能耗可以分为两部分：加工能耗和等待能耗。加工能耗指的是机器在加工各道工序时产生的必要能耗；等待能耗指的是机器处于调整时间、质检时间以及空闲时间时产生的非必要能耗，这部分能耗在保证工艺质量的前提下，应尽可能减少。结合实际情况，质检过程处理结果分为两种：合格和返修。若该工序的质检结果为合格，则直接进入下一道工序的加工；若结果为返修，则需要返回到有问题的指定工序进行加工，再以指定工序为起始工序直至完成加工任务。此外，调度过程需满足以下假设条件：①所有工件均可在0时刻进行加工；②每台机器在同一时刻只能加工一个工件；③所有工序一旦开始就不能中止；④同一工件的加工工序分先后顺序；⑤质检时间和调整时间之间不分先后顺序，可以同时并行；⑥不考虑机器故障问题。图1为不考虑质检扰动的原始调度甘特图。

图1 未考虑质检时间的动态调度甘特图

考虑质检扰动的重调度甘特图如图2所示。

图2 考虑质检时间的动态调度甘特图

图中红色方格和绿色方格表示质检工序的时间，红色方格表示工件的工艺加工质量不达标，需重新加工；绿色方格表示检验合格，直接加工下一道工序。调整时间和质检时间不分先后，可同时进行。

1.2 能耗模型

(1)加工能耗：机器对工件进行车、铣、磨等工艺加工时，所消耗的能量。这部分能耗可通过二次多项式拟合曲线求得，公式为：

(1)

式中，E1为加工能耗；α1、α2是二次多项式的拟合曲线系数；xijh为0-1变量；Ym1为机器加工功率；m为机器总数；Pijh为第j个工件的第h道工序在机器i上加工时间。

(2)空转能耗：机器在等待加工的过程中消耗的能量，包括：工件等待时间、机器调整时间、工件质检时间，公式为：

(2)

式中，E2为空转能耗；xijh为0-1变量；Ym2为机器空转功率；Cjh为第j个工件的第h道工序加工完成时间。

综上所述，能够得到所有机器的综合能量消耗表达式为：

(3)

式中，E为机床总能耗。

1.3 绿色动态调度模型

绿色柔性作业车间动态调度模型，同时兼顾经济指标和绿色指标，即最大完工时间和机器总能耗。模型函数和约束条件为：

(4)

式中，Cmax为最大完工时间。其中，Cmax=min(max(Cj))为最大完工时间的计算公式。约束条件为：

Hijh=Cj(h-1)+Vijh

(5)

式中，Hijh为工件j的第h道工序在机器i上的允许开始加工时间；Vijh为工件j的第h道工序在机器i上的调整时间。

Hijk=Cj(k-1)+Rijh

(6)

式中，Rij为工件j的第h道工序在机器i上的质检时间。

Hijh′=max(Hijh,Hijk)

(7)

式中，Hijh′为工件j的第h道工序在机器i上的实际开始加工时间。

Cjh=Hijh′+Pijh

(8)

式中，Cjh为工件j的第h道工序的完工时间

(9)

式中，mjh为第j个工件的第h道工序的可选加工机器数；xijh为0-1变量。

式(5)表示调整时间约束；式 (6)质检时间约束；式(7)表示质检时间与机器调整时间中的较大者；式(8)表示同一时刻同台机器只能加工一道工序；式(9)属于机器约束，表示同一时刻同一道工序能且只能被一台机器加工。

多目标优化模型的求解大致可分为两类：加权优化模型和帕累托优化模型。为了便于决策者调节指标权重，寻找更有针对性的调度方案，选取加权优化模型进行求解。采用加权归一的方式，将多个目标的量纲进行统一，式(4)可进一步描述为：

(10)

2 头脑风暴算法

头脑风暴算法是一种模拟人类群体决策过程的群体智能优化算法。采用文献[10]的头脑风暴算法流程框架，在单目标算法的基础上引进能耗指标，设计了多目标头脑风暴优化算法。通过k-means聚类方法，不断把解集里的较好解挑选出来并聚集在一个较小的解空间里，提高了全局搜索能力；在旧解的基础上产生新解的迭代方式保证了种群的多样性，增强了局部搜索能力。

2.1 编码

编码是头脑风暴算法的关键环节，能够保证算法的收敛速度。为了避免单一编码方式导致解的表达不清楚，采用文献[11]设计的多层编码方式。每个个体分为两层{工序层S ,机器层M }，采用整数编码方式。如：{31232 / 31213}，工序层数字代表工件编号，数字重复出现的次数表示工件的某道工序，即第4位的3表示工件3的第二道工序；机器层数字代表机器编号。

2.2 重调度种群初始化

为了提高初始化种群的质量，依据种群个体的位置矢量向工序排序转换。首先，得到随机排序的工序层集合S0的位置矢量，按照位置矢量大小重排后，得到优化后的集合S。

表1 个体位置矢量向工序排序转换

由表2可知：解码后的工序优先度为O21→O31→O32→O11→O22。

(2)机器层编码方案

机器层编码为工序指派机器的集合M，其基因是工序所选择的可用机器。首先，得到随机指派集合M0的位置矢量，若位置矢量是整数则为有效编码，即为指派机器编码；否则属于无效编码，对位置矢量的大小向下取整，待指派的机器集合M。个体位置矢量向指派机器转换如表2所示。

表2 个体位置矢量向指派机器转换

最后，将编码工序层和机器层编码组合在一起，表示优化后的1个可行解: {31 232 / 31 213}。为了避免非法染色体的产生，第2层编码对应指派工序的机器为该工序的“第几个”可用机器，而不是全部机器。

2.3 适应度函数

在头脑风暴算法迭代的过程中，适应度值越高，被保留的概率就越大。以下研究的适应度函数设置为式(10)。

2.4 BSO解的分类和聚类

BSO的聚类过程是决定优化效果的关键步骤，主要作用是将不同的个体分类，让相似个体处于同一个类中。由于k-means聚类算法具有运算速度快、简单等优点，故采用k-means不断把较好解挑选出来，并聚集在一个较小的解空间里。

BSO的分类操作是基于已有的旧解来产生新解。分类操作采用高斯变异方式：

(11)

其中，w1+w2+wn=1。

(12)

式中，T为最大迭代数；t为当前迭代数；k为控制搜索步长的调整系数，作用是平衡算法的收敛速度；rand()为随机函数。

2.5 算法测试

为了验证算法的性能，选取3个标杆案例[12-14]中的算法与当前算法进行对比，指标选取最大完工时间，参数设置和标杆文献相同。标杆文献的算例规模分别为：6×6、8×6、10×6，结果如表3所示。

表3 不同规模问题的算法对比

从表中可以看出，IBSO算法的收敛速度和精度均优于其他算法，验证了算法的可行性和高效性。在6×6的实例中，IBSO稍稍优于CE-MOFJSP；在8×6的实例中，IBSO算法的性能最大提高了18.3%，且迭代次数远远低于标杆文献的迭代次数，优化效果最为明显；在10×6的实例中，性能也提高了14.5%。

3 实验与结果分析

用Matlab2018a软件进行程序编译，实验环境配置如下：Intel Core i5-4210 2.6GHz CPU、4.00RAM、Windows 10 64位操作系统。参数设置为：终止迭代数500；种群规模50；Pclustering=0.8;Pgenetation=0.2。为了衡量原始调度和重调度的偏离度，采用相对偏差来表示原始调度和重调度间的完工时间和能耗偏差，公式如下：

(13)

(14)

因为当前没有绿色柔性作业车间动态调度的标准实例，所以机器的加工数据采用来自文献[15]的10×10测试数据，而测试数据不包含调整时间，将工序对应的调整时间设定为不超过4的随机数，质检时间和扰动工序为随机生成。机器能耗的设置参考文献[16] ，机器的额定功率和空载功率设置如表4所示。

表4 所有机器的加工功率 (kW)

算例为10个工件在10台机器上加工，共有30道工序。需要质检的工序为：1-1、3-1、4-1、6-1，对应的质检时间为：4.8 min、5 min、6.3 min、5.5 min。质检时间是固定的，不随机器的不同而改变。运算结果如表5所示。

表5 数值计算结果

从表5可以看出，完工时间指标和能耗指标是互斥的。原始调度和重调度方案随着α值的升高，完工时间逐渐缩短，而能耗不断增加。根据指标权重的特点将生产模式分为三类，便于企业决策者挑选适合的最优解。

为了反映重调度和原始调度的偏差变化情况，绘制了完工时间和能耗的偏差变化趋势，如图3所示。

图3 完工时间和能耗的偏差变化趋势

从图3可知，随着完工时间指标权重的增大，RT1直线的波动较小。这是因为原始调度和重调度完工时间的偏差值始终稳定在8附近，带入完工时间偏差式(13)后，结果变化不大；RT2直线波动较大，由最大值0.45降至0.2，能耗扰动偏差降低了55.6%。由于重调度方案的加工工序变多，必要的等待能耗和加工能耗增大，致使算法的搜索迭代空间更大，能耗结果的分布更加离散。随着能耗指标的增大，搜索强度提高，使得能耗偏差逐渐缩小至一定范围内。图4为原始调度和重调度的最优前沿分布图。

图4 原始调度和重调度的最优前沿分布

由图4可以看出原始调度和重调度的帕累托解均匀、全面地分布在最优前沿上，验证了算法和模型的有效性和可行性。原始调度方案和对应的重调度方案，其完工时间偏差值和能耗偏差值较为稳定，表明基于以上模型和算法的调度方案可有效将质检工序带来的完工时间扰动和能耗扰动控制在一定范围内，保障了生产过程的稳定性和高效性。由于篇幅有限，仅展示重调度之后的甘特图。

根据企业面临的实际情景，以速度为导向规则的重调度甘特图如图5所示，完工时间为28.2 min，能耗为1 064 kJ。

图5 速度导向下的重调度甘特图

图中，红色和绿色方格表示质检时间，红色表示需要返工，绿色表示质检合格；质检时间上方的条纹方格，表示调整时间，且调整操作和质检操作可以同时进行。黑色方格表示工件返工后被重新调度后所进行的安排。从图中可以看出，所有工序在各机床的分配较为均匀，机器负载也更为合理。

不同模式下的原始调度方案不同，故对应的重调度方案也不同。当企业需要推行绿色生产，则以能耗为导向规则进行重调度，甘特图如图6所示，完工时间为44 min，能耗为859 kJ。

图6 能耗导向下的重调度甘特图

图中，机器3、6、9承担了较多的加工任务，且每道工序的加工时间也较长。通过分析机器的加工特性可知，机器3、6、9的节能属性较好，加工功率较低，故工件都倾向于流向这几台机器。机器8在加工各工件的功率只有3 kJ，而流向该机器的只有工序3-1，这是由于机器8的整体加工时间过长，限制了更多的工序流向该机器。

两种规则导向所产生的实际效应差异较大。速度相差15.8 min，速度导向下的调度方案速度提高了35.9%；能耗相差205 kJ,能耗导向下的调度方案可以节省能耗19.3%。企业决策者根据生产的实际需要，可灵活选择不同的方案，保障企业效益最大化。

4 结论

以绿色柔性作业车间为研究对象，针对质检扰动引起的完工时间长和能耗高的问题，对绿色动态调度优化问题进行了研究，得出以下结论：

(1)建立节能调度数学模型，采用改进的头脑风暴算法进行求解，可有效将质检扰动的影响控制在一定范围内，保证了生产的稳定性和流畅性。用算例进行检验，原始调度和重调度的帕累托最优解集的分布较为均匀、全面，验证了模型和算法的有效性

(2)改进了头脑风暴算法，提高了最优解的收敛速度和精度。在编码环节引进了转换机制和多层编码策略，有效提高了初始种群的质量。通过与其他算法作对比，验证了算法的可行性与高效性。

(3)决策者根据生产情境选择恰当的绿色柔性作业车间动态调度方案，在保障交付期的前提下，将生产能耗降至最低，有利于企业降低生产成本、推行可持续发展战略。