基于Stigmergy的Holonic控制架构下的动态调度问题研究

, ， ，

(浙江工业大学 机械工程学院，浙江 杭州 310014)

传统集中式的控制方法，强调在统一的控制单元中对整个系统进行信息控制，通过一个计算中心实现所有的调度任务与资源规划.但这对于实际上处于动态环境中的制造单元来讲，随着问题规模的扩大以及动态环境下实时数据的不断增多，这种控制方法对动态的调度环境无法显示很好的适应性，也无法通过任务分解等方式降低其计算的复杂性.

Holonic制造系统(Holonic manufacturing system，HMS)由具有自治与协作特性的Holon单元递归嵌套而成，能够把分布式控制结构与分层控制结构的特点相结合，使车间调度系统具有集中控制系统的稳定性和全局优化等优势的同时兼具分布式系统的鲁棒性、柔性等特点.文献[1-4]提出了一些基于HMS的调度方法，这些方法在已有的Holonic控制架构或者构建新的控制架构基础上加上适当的协商机制来构建调度系统，普遍采用合同网协议、组合拍卖等显示协商机制或者拉格朗日松弛法等数学方法.蚁群的Stigmergy机制是在一组分散分布的实体之间以对环境的改变为媒介协调自身行为的一种间接通信方式[5]，十分适合作为基于Holonic控制架构的调度系统的协商机制.文献[6-8]讨论了Stigmergy机制应用于车间调度系统的原理、方法以及优势，但都未给出具体的实现方式.因此，在PROSA控制架构[9]的基础上，通过对Ant Holon以及面向动态调度的Staff Holon进行设计，构建了基于Stigmergy的Holonic控制架构，并给出了动态环境下这一架构的动态调整机制.在定义Holon单元之间通信所需信息素的基础上，提出了在这一架构下各Holon单元以Stigmergy机制为协商机制的协商过程以及实现作业车间动态调度的一般策略.

1 动态环境下基于Stigmergy的Ho-lonic控制架构

在蚁群的Stigmergy机制中，蚂蚁通过在从食物源返回蚁巢的路径上释放“信息素”来指导自身或者其他蚂蚁找到从蚁巢到食物源的最短路径.类似地，原材料所在的仓库系统可以视为蚁巢，生产车间中每台可供选择的机器设备都可以看做是蚂蚁觅食道路上的一个结点，而设备的不同加工时间就像路径的不同长度.若以最大完成时间最小作为生产调度的目标函数，则蚂蚁用以在蚁巢和食物源之间寻找最短路径的Stigmergy协商机制完全适用于车间的生产调度.因此，可以在PROSA架构中引进一种Ant Holon，如同蚂蚁在周围环境中散布和感知信息素一样负责在制造环境中发现和传播信息[7]，由此建立基于Stigmergy的Holonic控制架构.

1.1 Ant Holon设计

在PROSA架构的基础上，基本Holon与Staff Holon以一定的速率来创建各自对应的Ant Holon来负责信息的传播与接收.但是与真实环境中的蚂蚁一样，建立基于Stigmergy的Holonic控制架构所需的Ant Holon不仅要求数量很大而且还要很“便宜”，其中Ant Holon的数量是可以通过创建速率来设定的参数.另一方面，Ant Holon的内部属性与创建它的基本Holon或者Staff Holon相同，但并不具有同等的功能，而只是负责感知和散发信息素，所以只需要有限的计算能力和通信带宽[10]，废弃这种Holon也只需释放一些计算机内存，从而满足“便宜”这一要求.Ant Holon的属性与功能采用UML建模语言中的对象图来表示，如图1所示.

图1为基于Stigmergy的Holonic控制架构中各类Holon之间的关联关系.

图1 控制架构中各类Holon关联关系的UML描述

1.2 面向动态调度的StaffHolon设计

在PROSA架构中，基本Holon涵盖了制造系统中独立的三个方面，Holon本身又具有自相似性，使得系统具有可重构性，更易于扩展.另一方面，通过Staff Holon又可以实现系统的所需的优化性能.因此，实际上Holonic控制架构是利用Staff Holon来解除系统可靠性、敏捷性与系统性能之间的耦合关系.当系统平稳运行的时候，通过Staff Holon建立一种递阶控制结构，基本Holon采用Staff Holon所给出的建议，从而实现系统的整体优化性能.当生产过程中出现扰动的时候，又通过Staff Holon将系统动态调整到一种临时的异构式控制结构.此时，基本Holon将进行自主决策来处理扰动的影响.为此，定义了一类面向动态调度的Staff Holon—On-line Supervisor Holon(OS Holon)，其作用包括：

1) 为基本Holon提供充足的信息，通过自身的专家知识和经验为基本Holon提供建议，辅助基本Holon完成生产任务.

2) 监督整个生产过程，定期通过Ant Holon向IP Holon发布询问状态的信息素，基本Holon感知到这一信息素后回复自身当前状态.

3) 在生产过程中出现意外扰动后，判断扰动类型以及对系统造成的影响，并对系统架构进行动态的调整.

除上述功能外，OS Holon的内部属性中还包含有车间中生产加工过程信息，如某个资源的加工过程相关信息(出现故障、恢复加工等)；生产信息，如某个加工任务的进度信息；基本Holon的信息，如基本Holon当前的状态、负荷情况等等.OS Holon的属性与功能的UML描述，如图1所示.

1.3 信息素定义

与Stigmergy机制中蚂蚁释放“信息素”来指导自身或者其他蚂蚁找到从蚁巢到食物源的最短路径一样，在Holonic控制架构下使用Stigmergy机制作为协商机制也需要定义一种信息素，基本Holon与Staff Holon通过各自对应的Ant Holon释放这种信息素来供其他Ant Holon感知，从而实现信息的交互与传递，这种信息素的表达方式如表1所示.

表1 信息素表达方式

这类信息素的运行机制强调Stigmergy机制中局部信息素的发布无需同步的特性.比如，在旧式的医院中，护士按时测量完病人的体征参数之后，将记录的结果放在病人的病床上方.当医生到达之后，取下记录查看并采取相应的措施.在这一过程中护士与医生无需约定时间和地点来获取信息，从而能够更自由地安排自身的时间，提高工作效率.同理，基本Holon和Staff Holon只需不断通过Ant Holon向Information Publish Holon(IP Holon)中释放或者感知信息素，预定的时间和地点交换信息.IP Holon则是模拟Stigmergy机制中蚂蚁所生活的环境，作为信息素的载体.例如，当有订单下达到生产车间，Order Holon便会创建0rder Ant Holon在IP Holon中留下信息素[N,O]，来供Product Holon感知从而获得相关的产品加工知识.

与蚁群Stigmergy机制中的信息素一样，这种信息素也具有挥发性，挥发的速率ρ是可以设定的参数.因为信息素包含有具体内容，其挥发速率ρ通常较小，但是一旦被Ant Holon感知之后就会立即完全挥发掉.如信息素[N，O]一旦被Product Ant Holon感知，表明Product Holon已经接受了这一项任务，信息素[N，O]也就随之挥发掉了.这一特性保证了Ant Holon感知到这一类信息素始终是有价值的、可用的，同时也保证了IP Holon中始终都有一定的可用存储空间，降低了系统的通信负荷.

1.4 Holonic控制架构的动态调整机制

在PROSA控制架构中，当系统平稳运行的时候，通过Staff Holon建立一种递阶控制结构，基本Holon采用Staff Holon所给出的建议，实现系统的整体优化性能.当生产过程中出现扰动的时候，又通过Staff Holon将系统动态调整到一种临时的异构式控制结构.此时，基本Holon将进行自主决策来处理扰动的影响.因此，基于OS Holon建立在动态环境下Holonic控制架构的动态调整机制，从而明确扰动事件出现后Holonic控制架构的变化过程.

为了更好地说明Staff Holon对Holonic控制架构的动态调整过程，先引入自治因子的概念，自治因子α，反应Holon自治性能力的参数.Order Holon,Resource Holon以及OS Holon内都包含有这一参数.自治因子值越大，表明对应Holon的自治性越高.通常，在稳定情况下Order Holon和Resource Holon的自治因子值较小，会尽量服从OS Holon的协调，并接受其调度建议.

调整机制包括以下4个步骤：

1) 在系统稳定运行情况下，OS Holon通过自身的专家知识和经验为基本Holon提供建议，辅助基本Holon完成生产任务.此时，Order Holon和Resource Holon内的自治因素值较低，因而会尽量服从OS Holon提供的建议，系统中呈现出一种递阶控制的结构，如图2所示.

图2 稳定状态下的系统结构模型

2) 当OS Holon监督扰动出现之后，会立即判断扰动事件的类型并评估对系统造成的影响程度，然后通过OS Ant Holon向IP Holon中释放信息素来通知Order Holon和Resource Holon升高自身的自治因素.

3) 当Order Holon和Resource Holon接受到这一信息素后，根据信息素的内容对自己的自治性因素进行调整.当Order Holon和Resource Holon的自治性高于OS Holon时，两者之间直接进行协商决策，此时系统中呈现临时的异构式控制结构，OS Holon仍然继续监督整个生产过程，并对调度方案提供建议，但由于现在Order Holon和Resource Holon具有较高的自治因素，它们很有可能拒绝这些建议.

4) 扰动事件结束后，Order Holon和Resource Holon将自身的自治性因素降低，降低的幅度与升高的幅度相同.之后由于Order Holon和Resource Holon的自治性低于OS Holon的自治性，因此系统恢复到稳定运行状态下.

在上述步骤中，OS Holon通过自治因素实现对Holonic控制架构的动态调整.Holonic控制架构的动态变化只是瞬时的，由扰动事件触发，扰动结束后即恢复到稳定状态，这一过程依赖于Holon单元内决策机制的制定.

2 Holonic架构下的动态调度策略

2.1 问题描述

动态环境下的车间调度问题与一般作业车间调度问题相比，是将已有的大大简化的作业车间调度生产模型，与实际生产状况相结合，使模型更贴近真实的生产情况[11].一般地，作业车间动态重调度问题可描述为：n个工件Ni(i=1,2,…,n)在m台机器Mj(j=1,2,…,m)上加工，每个工件由一组加工工序k(1≤k≤m)组成，每道工序需要在指定的机器上加工，以Oikj表示第i个工件的第k道工序在机器Mj上加工.车间的生产环境是动态的，当扰动事件发生后，对初始调度方案进行调整，在保证工件都能按时交货的情况下，尽量使得调整后的调度方案对原方案的偏离最小.另外还需满足以下假设：

1) 重调度的时间忽略不计，一旦调度完成，对应的工件立即进入加工状态.

2) 扰动事件是随机发生的，但是同一时刻只发生一件扰动事件，并且不会在动态重调度过程中发生.

3) 受到影响的工件动态调度后，在新机器上重新开始加工.

4) 只考虑机器故障、加工延时、紧急插单三种扰动事件.

在静态环境下，调度的稳定性通常不是问题.但在动态的调度环境下，稳定性和鲁棒性是很重要的评价指标.采用文献[12]中提出的评价调度性能的方法，采用重调度与预调度中最大完成时间的偏差最小作为动态重调度目标，并满足与预调度相同的约束条件.

(1)

s.t.STilq-STikp≥Tikp

STilj-STikp≥Tikjdi-Tieij≥STieij

2.2 动态调度流程

为了应对初始调度方案执行过程中不可避免的各种扰动事件，使得调度系统能够基于适当的策略做出合适的反应，在对调度驱动策略的研究基础上，制定了如下动态调度策略：首先评估扰动事件对生产过程的影响，根据评估结果来判定是否需要进行重调度，重调度策略与扰动事件的类型有关，整体的动态调度策略如图3所示.

图3 动态调度策略图

Step1在初始调度方案执行过程中，OS Holon监测是否有扰动事件发生.如果有，则判断扰动事件的类型，并通过实时的现场数据评估扰动事件的影响大小.否则，按预调度方案继续执行.

Step2根据扰动事件影响的大小判定是否需要进行重调度，如果是，则转向Step 3；如果不是，则进行右移重调度，下达新的调度方案.

Step3判定是否需要进行全局重调度，如果是，则转入Step 4；否则，进行局部重调度，下达新的调度方案.

Step4扰动事件的影响很大，需要进行全局重调度.调度完成后，下达新的调度方案.

3 协商机制

基于Holonic控制架构的动态调度方法由内嵌有决策机制的分布式Holon单元通过支持动态调度的协商机制来完成，个体的Holon单元发挥自治与协商的特性自下而上地寻找一种动态的平衡，而局部单元的决策能力是实现调度功能的基础.在基于Stigmergy的Holonic制造执行控制架构下，对扰动事件类型的判断以及对扰动事件造成的影响评估机制封装在OS Holon内部，动态重调度策略以及重调度策略的选择机制封装在Order Holon中.当OS Holon监测到扰动发生后，通过信息素来修改Order Holon和Resource Holon的自治性，从而动态地调整系统的控制架构来实现对扰动的处理.信息素的内容包括两部分：扰动类型、影响等级，表达方式为[Ⅰ，up-1]，编码方式如表2所示.扰动解除之后，Order Holon和Resource Holon降低同等的自治性等级，系统中的架构恢复到稳定状态.

表2 修改自治性的信息素中的编码方式

现以紧急订单下达到车间为例来说明扰动事件发生各Holon单元之间的协商过程，如图4所示.这里默认为当紧急订单下达到生产车间则表示车间有能力完成加工.

图4 出现紧急订单后各Holon之间的协商过程

Step1当OS Holon监测到紧急订单下达到车间后，立即判断故障类型并对影响进行评估，并通过OS Ant Holon向IP Holon中释放对应的信息素.同时，系统便为其创建一个Order Holon(*).Order Holon(*)隶属于当前正在加工的Order Holon中，其内部属性与功能与Order Holon相同，如图5所示.但Order Holon(*)的生命周期比Order Holon要短，当紧急订单得到处理之后，Order Holon(*)的生命周期也就随即结束.

图5 Order Holon(*)结构图

Step2Order Ant Holon与Resource Ant Holon感知到信息素后反馈给对应的基本Holon.若信息素内容为[Ⅰ，up-1]或者[Ⅰ，up-2]，转向Step 3；若为[Ⅰ，up-3]，则转向Step 4.

Step3Order Holon与Resource Holon根据信息素内容升高自身的自治性等级，Order Holon根据影响等级选择对应的重调度策略，并创建一定数量的Route Ant Holon根据重调度策略与Resource Holon协商生成新的调度方案.

Step4若信息素内容为[Ⅰ，up-3]，表明该扰动事件对调度系统的影响较大需要进行全局重调度.这时，Order Holon通过Order Ant Holon向IP Holon中释放信息素来向Product Holon请求新的加工工艺规划.

Step5Product Holon感知到这一信息素后，重新安排对应工件的加工工艺，并将结果发布在IP Holon中.

Step6Order Holon感知到新的设计结果后，创建一定数量的Route Ant Holon与Resource Holon进行协商，得到全局重调度的加工方案.Route Ant Holon与Resource Holon协商得到全局加工方案的过程选用蚁群算法[13]进行实现.

若经过一段时间扰动事件得以解除Resource Holon与Order Holon对应降低自身的自治性等级，之后Holonic控制架构恢复到稳定状态.

4 算例应用

为了说明上述调度策略，选取了表3所示的典型的6×6 JSP问题为算例.假设在t时刻编号为001的订单下达到生产车间，该订单中有6个待加工工件的加工要求，6台加工设备分别抽象为6个Resource Holon，初始调度方案的甘特图，如图6所示.

表3 6×6算例加工任务数据

图6 初始调度方案的甘特图

假设在t=70时刻有紧急订单下达到生产车间，预交货期为185.紧急订单中加工任务数据如表4所示.

表4 紧急订单中加工任务数据

根据各Holon单元的协商机制，系统将在紧急订单下达时为其生产对应的Order Holon(*).同时OS Holon开始判断此次扰动事件类型为Ⅰ型，这里假定OS Holon对扰动事件的影响等级评估结果为3级.之后OS Holon通过OS Ant Holon像IP Holon中释放信息素[Ⅰ，up-3]，Order Holon与Resource Holon通过各自对应的Ant Holon感知到信息素后升高自身的自治性.Order Holon通过信息素判定需要采用全局重调度的处理方法，向IP Holon中释放信息素[N,O]请求新的加工工艺规划，Product Ant Holon感知到这一信息素后带回给Product Holon，之后Product Holon将反馈结果通过Product Ant Holon释放到IP Holon中.Order Holon得到新的加工工艺规划之后，创建一定数量的Route Ant Holon与Resource Holon协商对剩余的加工工序全部进行重新调度.协商过程通过蚁群算法借助MATLAB.R2010a来实现，求解的运行结果见图7，获得的调度结果最优解为180，满足紧急订单的交货期要求.全局重调度后产生新的调度方案，甘特图如图8所示.

图7 全局重调度中最优解的进化曲线

图8 全局重调度后的甘特图

5 结 论

在Stigmergy机制的基础上，通过对设计Ant Holon、面向动态调度的Staff Holon以及定义信息传递所需的信息素，构建了动态环境下基于Stigmergy的Holonic控制架构，提出了该架构的动态调整机制.在对动态问题进行描述的基础上，给出了动态调度的一般流程以及Holon单元间基于这一流程实现动态调度的协商机制.通过算例应用说明了基于Stigmergy的Holonic控制架构下进行动态调度的基本过程，实现了对扰动事件的满意处理.

参考文献：

[1] KOJI I， YOSHITAKA T， NOBUHIRO S． A study on real-time scheduling methods in Holonic manufacturing systems[J]． IFIP International Federation for Information Processing，2005，168：301-312．

[2] PAULO S， CARLOS R， JOSé N． Scheduling in Holonic manufacturing systems[J]． Springer Series in Advanced Manufacturing，2007，10(7)：167-190．

[3] PAULO L， FRANCISCO R． A Holonic approach to dynamic manufacturing scheduling[J]． Robotics and Computer-Integrated Manufacturing，2008，24(5)：625-634．

[4] BORANGIU T， RILEANU S． Open manufacturing control with agile reconfiguring of Resource services[J]． Control Engineering and Applied Informatics，2010，12(4)：10-17．

[5] BO Xing， FULUFHELO V N． Ant stigmergy shop floor control architecture for intelligent Product oriented manufacturing system[C]//Systems Man and Cybernetics (SMC)， IEEE International Conference on. Oakland: IEEE Computer Press，2010：4182-4189．

[6] WANG Lei. Pheromone-based coordination for manufacturing system control[J]. Journal of Intelligent Manufacturing，2012，23(3)：747-757．

[7] PAUL V， HADELI， BART S G． MAS coordination and control based on stigmergy[J]． Computers in Industry，2007，58：621-629．

[8] JOSÉ B， PAULO L， DAMIEN T， et al． Enhancing ADACOR with biology insights towards reconfigurable manufacturing systems[C]//IECON 2011-37th Annual Conference on IEEE Industrial Electronics Society. Oakland：IEEE Computer Press，2011：2746-2751．

[9] HENDRIK V B， JO W， PAUL V， et al． Reference architecture for Holonic manufacturing systems：PROSA[J]． Computers in Industry，1998，37(3)：255-274．

[10] PAUL V， HADELI， BART S， et al． MAS coordination and control based on stigmergy[J]． Computers in Industry，2007，58：621-629．

[11] 陈勇，胡婷婷，鲁建厦．基于遗传算法改进的动态车间调度[J]．浙江工业大学学报，2012，40(5)：537-553．

[12] COWLING P I， JOHANSSON M． Using real time information for effective dynamic scheduling[J]． European Journal of Operational Research，2002，139(2)：230-244．

[13] 黄亚平，王万良，熊婧．基于改进蚁群算法的智能调度系统设计与开发[J]．浙江工业大学学报，2010，38(3)：251-256．