基于基因转录的机加工车间主动调度研究

吴正佳 龚 稳 孟荣华 涂晶鑫 董元发,2

(1.三峡大学 机械与动力学院,湖北 宜昌 443002;2.机器人与智能系统宜昌市重点实验室,湖北 宜昌443002)

生产过程中不确定的扰动事件,如紧急订单插入、交货期更改、设备突然失效等,随时可能导致车间生产紊乱甚至中断,给企业带来损失.故研究扰动因子已成为机加工车间稳健作业的核心任务.近年来,许多专家针对此问题做了诸多研究.Zakaria等[1]提出了基于设备空闲时间来有效地应对插单和机器故障;Vieira等[2]针对重调度,提出了一种新的重调度系统;Al-Hinai等[3]通过改进的遗传算法来研究随机机器故障下FJSP鲁棒调度问题;Lu等[4]通过最短路径问题解决最小化加工时间的单一目标函数的单机鲁棒调度问题;Ranjbar等[5]研究了有关随机加工时间和已知客户交货期的鲁棒并行机调度问题;刘明周[6]等采用主动和被动重调度规则进行响应扰动,建立了重调度优化集.综上所述,机加工稳健作业问题研究现状存在着以下几点不足:

1)在调度策略上大多采用鲁棒性调度,虽然考虑了不确定性事件,但是不确定性因素过于单一,适用的范围很小,且此调度方案对突发时间的响应能力较差,牺牲了调度系统的效率,难以融入实际生产中.

2)目前的研究重点着重于车间的显性扰动研究,忽略了隐性扰动的危害.而研究车间的隐性扰动,通过扰动因子之间的耦合可以提前预测隐性扰动,采用有效解决方法,可以提高车间调度系统的稳定性.

3)现有研究方式多为假设反应式调度,缺少主动式调度的研究,而运用好主动式调度可以有效增加车间调度的鲁棒性及减少车间的调度产生次数.

上述描述突出了现有研究现状下,缺少对车间主动调度问题的研究.车间主动调度问题非常复杂,因为扰动因子、设备故障和调度策略,在生产车间都是相互影响的.在扰动发生之前,对车间生产调度系统进行微调度,避免完全重新调度,同时节约成本,是主动调度的主要思想.基于上述车间主动调度问题,本文提出了生物学中基因的概念,以解决隐性因子不易表达的困难,同时借鉴基因转录与翻译的概念,对隐性因子进行研究,使多种不确定事件进行耦合,便于主动调度的实施.

1 问题描述

1.1 机加工车间调度问题描述

n个工件,m台机器,每个工序可以在多台机床中任意选择一台进行加工,不同工件的工序加工路径可以不相同.工件集为J={J1,J2,…,Jn};每个工件包含一道或多道工序数,工件i的工序集合为Oi={Oi1,Oi2,…,Oij};工件i的第j道工序可供选择的机器的集合为Mij={Mij1,Mij2,…,Mijk};工件i的第j道工序在机器k上的加工时间集合为pij={pij1,pij2,…,pijk}.

加工作业调度问题约束条件如下:

1)所有工件最早加工时间为零,加工开始前机器都是空闲的;

2)工件在加工过程中不能中断,除非有扰动事件发生;

3)工件的某工序在同一时刻只能占有一台设备,同样每台设备在某个时刻只能为一个工件所用;

4)不同工件没有优先级规则;

5)工件的加工工序顺序固定、不能调换,只有当前一工序加工完成后才能开始下一工序的加工;工序的准备时间忽略不计;

6)出现扰动时,不受其影响的正在加工的工件继续加工,直到该工序完成.

在建立模型时,需用特定的符号来描述车间中工序和机器的状态信息,见表1.

表1 鲁棒性测度建模符号含义

据此,本文的调度模型为

式(1)为工件最大完工时间;式(2)为机器能力约束;式(3)为工序约束,式(4)为开工时间.

1.2 主动调度方案的鲁棒性测度建模

当初始调度方案受实时与预测扰动事件影响时,对初始调度方案稍做修改,形成主动调度方案.调度方案的性能鲁棒性测度为:

初始调度方案的稳定性鲁棒性测度为:

当实时与预测事件影响初始调度时,形成响应的主动调度方案,其目标是最小化扰动时间对初始调度方案的影响.影响方案的鲁棒性测度表示为:

2 生产车间扰动因子分析

生产车间扰动事件的本质是由扰动因子之间的相互作用产生的[7].扰动因子与调度策略之间的关系如图1所示.扰动因子分为隐性扰动因子和显性扰动因子,而隐性扰动因子可以通过隐性扰动因子之间的耦合关系转变为显性扰动因子.

图1 扰动因子与调度策略关系图

2.1 生产车间的扰动因子分类

在目前的主动调度研究过程中,扰动因子分类是第一步.本文主要从设备类,物料类,产品类,订单类4个方面展开研究,总结出如图2所示的常见生产扰动现象原因分类图.

图2 因子分类图

2.2 扰动因子的相关关系

在车间中,一般能观察到的多为显性扰动,但隐性扰动也是十分重要的一部分[8].本文的主要思想为:显性因子不能自发地进行扰动,如要发生扰动则必须由一个或多个隐性扰动之间耦合对其进行驱动,使显性因子进行扰动.故隐性扰动也是间接影响了车间调度策略.隐性扰动因子之间的关系可以分为促进作用和抑制作用,促进作用是指当两个隐性扰动因子进行耦合时,能够增加耦合转变为显性扰动因子的几率,相反的抑制作用是指降低耦合转变几率.若因子X促进因子Y转变,则因子X为因子Y的促进子,否则称为抑制子.当因子X调节因子Y时,在网络中可以用关系X→Y表示.单位时间内生成因子Y的数量是因子X的活化状态函数,用希尔函数表述.对于促进因子而言,希尔函数从0开始,逐渐逼近最大的饱和水平,希尔函数具体的形式可以表示为:

对于抑制因子来说,希尔函数是一个S形递减函数.该函数曲线形状可表示为如下形式:

为了使系统具有一般性,本文让所有的节点参数相同.

2.3 扰动因子耦合图的建立

基于上述理论,可以将隐性扰动因子构建为一个有向网络渐变图,如图3所示.

图3 有向隐性网络渐变图

其中绿线代表促进作用,红线代表抑制作用.在车间未开始加工时(t=0时刻),无论什么生产元素的隐性扰动因子都是处于未被激活的状态,如图3(a)所示;在加工开始后,可能出现如图3(b)所示的已经激活的隐性扰动关系图;通过耦合后得到如图3(c)所示的渐变图.

2.4 阈值的设定

随着扰动个数的增加,以及耦合程度的增加,对单个生产要素的影响程度是不一样的.如图3所示,4个节点以及6条边都有赋值,代表了此点或边对这个4节点隐性扰动网络的影响程度,故这个4节点网络的节点代数和决定了网络的耦合程度.若耦合值α小于阈值δ,则对其进行添加抑制或者促进因子使生产恢复稳态;若耦合值α大于阈值δ,则产生的扰动很大.

3 车间的基因表达过程

鉴于上述分析得出,扰动因子分为显性扰动和隐性扰动.显性扰动是通过隐性扰动之间的耦合产生的,类似于生物学中遗传信息的转录.故本文将车间的扰动类比于生物学中的中心性法则进行研究.生物中心性法则表达如图4所示.

图4 中心性法则示意图

将车间表达成3层结构:把隐藏的隐性扰动因子信息耦合转录出来,成为易观察的显性扰动,显性扰动因子对生产调度产生影响,通过求解表达出新的调度策略.生产车间中的中心法则如图5所示.

图5 生产车间的中心法则图

故在生产车间加工生产的过程中,通过分析扰动因子与车间调度策略之间的关系,然后进一步分析扰动因子中显性扰动因子与隐性扰动因子之间的耦合关系,得出显性扰动转化的安全阈值.所有的隐性扰动因子视为DNA,它们之间的耦合形成显性扰动,此时就对原有调度方案形成了扰动,扰动大则需产生新的调度方案.

而本文的主动调度思想则是在隐性扰动耦合成为显性扰动的过程中,对其进行添加抑制或者促进因子,使得隐性因子的耦合值低于阈值(α＜δ),则维持原调度方案;若隐性因子的耦合值高于阈值(α≥δ),即产生的扰动很大,在可以调控的范围之内,则采用主动调度方案.本文根据专家经验设定阈值δ=0.8.基因抑制流程图如图6所示.

图6 基因抑制流程图

4 主动调度方案

4.1 主动调度框架

加工过程中,扰动不可避免.当车间出现异常的扰动时,首先判断异常类型,确定受影响的工件、工序和机器,更新调度参数,产生新的动态调度方案,并执行新调度方案;为避免调度中时间的浪费,减小异常扰动给制造加工系统带来的损失,在异常扰动发生之前,根据加工过程中RFID采集的实时数据与历史数据,对将来可能发生的异常扰动进行预测,采取必要的预防维护措施,避免扰动的发生,确定受影响工件与工序,更新调度参数,形成主动调度方案.本文的调度目标为最小化异常扰动对初始调度方案的影响.加工作业的主动调度框架流程图如图7所示.

图7 主动调度框架流程图

4.2 主动调度策略

通过RFID标签技术,实现从原材料出库经过机床加工以及产品入库整个加工过程的监测,在物料经过的各个加工工位都配置有RFID感知节点,以达到实时感知到达工件的ID号、时间、位置等数据,形成工件的实时状态矩阵S=(aij)(1≤i≤m,1≤j≤4).

式中:i表示工件序号;j表示工位序号;aij=0,表示工件在该工位加工情况正常;aij=1,表示加工情况异常.

主动调度采用基于预测事件驱动的重调度策略.该调度方式根据制造车间现场采集的加工过程实时数据以及历史数据,预测扰动事件的发生,并在扰动事件开始之前,预先安排处理,如更换刀具等.

滚动调度策略是常用的动态调度策略[7],在滚动调度策略中需要定义一个工件窗口,在重调度时刻,只调度该时刻工件窗口中的工件,滚动调度工件窗口示意图如图8所示.

图8 滚动调度工件窗口示意图

5 计算实例

以B车间为例,B车间有6个工件,每个工件均有3道工序,每道工序可以选择可加工该工件的机器中的任意1台进行加工,每道工序在各个机器的加工时间确定,各个工件每道工序可选择的加工机器见表2,各工序在对应机器上的加工时间见表3.

表2 工序加工可选机器设备

表3 工序在对应机器上的加工时间 (单位:s)

利用Matlab编程,使用遗传算法[9],基本参数根据规模与复杂度,设定种群规模为500,最大迭代次数为500,交叉率为0.7,变异率为0.3.得到初始的调度方案为图9所示:在加工开始进行时按照此加工方案进行操作,最小完工时间为712 s.此方案未考虑车间的其他运行情况因素(如物料运送时间或者考虑维护时间),是一个理想化的方案.

图9 调度甘特图

若考虑到扰动时,当t=326 s时刻,RFID对工件实时监测返回的异常状态矩阵如下:

说明在t=326 s时刻,O62=1表示第6个工件在第2道工序工位加工情况异常.甘特图9得到O62在M3上进行加工.则通过RFID预警检查在工作状态下的O62可能发生的扰动因子,能否使得O62在隐性扰动的情况下增加抑制或者促进因子,使之隐性因子之间的耦合影响不超过阈值.故分析得知,O62存在的隐性扰动见表4.

表4 存在的隐性扰动

得到隐性扰动网络如图10(a)所示,耦合后的网络图如图10(b)所示.

图10 隐性扰动因子耦合图

由希尔浓度关系,取h=2,k=0.3,对各点进行赋值,计算出耦合值为:α=0.84＞0.8,故无法通过增加抑制或者促进因子使得扰动维持在隐性扰动水平.故需要采用主动调度方案使得原始调度方案维持稳定.

以扰动因子3(缓冲区堵塞)进行说明,针对后续影响工序,采取调度方案时的目标为工件完工时间和鲁棒性测度和最小.对初始的调度方案局部调整,很快可以得到最优目标值为795.6,以使得出现扰动时间对初始调度方案影响最小.如图11所示:为应对加工O62出现的缓冲区堵塞的扰动时间,只是将O62后面的工序O13,O53采取了右移重调度,其他的加工工序保持不变,避免了缓冲区堵塞对O13,O53的影响,同时也确保了对初始调度计划影响最小.

图11 主动调度方案甘特图

6 结 论

在生产车间中,生产调度经常会随着扰动的发生而变化.针对目前车间调度研究的薄弱环节,本文研究了扰动因子之间的关系,并借助基因生物学中的动力学模型,研究扰动因子之间的关系,以达到对扰动事件的一个实时预测;采取主动调度的方法,使得生产调度系统在不需要产生新的调度方案之前消除扰动,使生产调度系统趋于稳态.最后通过经典的调度问题证明了方法的可行性.主要成果如下:1)建立了设备相关的隐性与显性扰动因子关系,且量化了隐性因子之间的耦合关系;2)针对实时调度问题的求解,设计了主动调度的框架,引入了前后两个不同单目标进行优化调度,并用经典的调度实例进行了应用分析.