基于Stigmergy的Holonic控制架构与调度策略

汤洪涛　刘　璐　陈　明　鲁建厦

浙江工业大学，杭州，310032

基于Stigmergy的Holonic控制架构与调度策略

汤洪涛刘璐陈明鲁建厦

浙江工业大学，杭州，310032

针对制造执行系统递阶式的控制结构以及Stigmergy机制在Holonic控制架构中应用的局限性，通过在Holonic制造系统PROSA参考架构基础上为基本holon以及参谋holon分别设计对应的蚂蚁holon，构建了基于Stigmergy的Holonic控制架构，给出了该架构下各类holon单元的4种内部holon(数据holon、决策holon、通讯holon和结构holon)，并定义了应用于基本holon和参谋holon之间传递具体信息以及订单holon与资源holon之间协商加工方案的两种信息素。给出了作业车间调度问题的数学描述，以最长完成时间最短为调度目标，提出了在基于Stigmergy的Holonic控制架构下各类holon单元以两种信息素为媒介协商实现作业车间调度的基本策略，并通过算例验证了该策略的有效性。

作业车间调度；Holonic控制架构；Stigmergy协商机制；蚁群算法

0　引言

在车间生产过程中，从调度的角度看，制造执行系统(manufacturing execution system，MES)承担的是调度方案的执行工作。MES通常是建立在递阶控制结构上的，其控制信息的传递是自上而下的。随着生产加工的进行，MES往往无法完全遵守初始的调度方案，需要在出现扰动的时候能够进行准确的评估，作出准确的应对决策。因此，MES需要一种自治的方式来辅助其完成这一工作[1]。Valckenaers等[2]提出在MES中引入分散化的Holonic控制机制构成HMES(Holonic manufacturing execution system)，改变MES在执行初始调度的过程中面对扰动时的响应方式，从而保证其鲁棒性和敏捷性。

蚁群的Stigmergy机制是在一组分散分布的实体之间使用的一种间接协商机制，这种协商机制十分适合同样由分布式实体构成的基于Holonic控制架构的调度系统。文献[3-4]讨论了在HMEES中使用Stigmergy协商机制的方法。Barbosa等[5]指出，在HMS中引入Stigmergy机制能够加强控制系统的自组织性，使系统具有更好的可重构性。但是，在上述研究中Stigmergy机制的应用仅限于订单与资源这两类实体中，而对其他实体之间如何通讯并未作具体说明。

本文从蚁群的Stigmergy机制的原理及其与车间生产中对象的映射关系出发，构建了基于Stigmergy的Holonic控制架构以及各类holon的内部结构。通过对holon单元的内部结构以及相互协商过程中使用的信息素进行定义，把Stigmergy协商机制的应用范围扩大到Holonic控制架构中的所有实体[6]，从而进一步满足作业车间调度系统的高效化和智能化要求。在此基础上给出了在该架构下各类holon单元相互协商完成作业车间调度问题的基本策略，并通过算例验证了该策略的有效性。

1　基于Stigmergy的Holonic控制架构

建立基于Stigmergy的Holonic控制架构，旨在将Stigmergy协商机制在优化性能与通讯负荷方面的优势与HMES相结合，在发挥holon单元自治与协商特性的同时兼具良好的优化性能与较低的通讯负荷。这种结合通过对HMES中各类holon设计对应的蚂蚁holon(ant holon)来实现，并通过定义两种不同类型的信息素来打破传统Stigmergy机制仅在订单holon(order holon)与资源holon(resource holon)之间使用的限制，将这一范围扩大到整个Holonic控制架构中，从而进一步发挥Stigmergy机制在交互协商方面的优势。

1.1蚂蚁holon的设计

在蚁群的Stigmergy机制中，蚂蚁通过在从食物源返回蚁巢的路径上释放“信息素”来指导自身或其他蚂蚁，找到从蚁巢到食物源的最短路径。文献[7]通过分析蚁群觅食机制中的对象及其协调和控制方式，建立了该机制与车间生产中对象的映射关系，见表1。

表1　蚂蚁觅食机制中的对象与

在生产车间中，原材料所在的仓库系统可以视为蚁巢，每台可供选择的设备可以看作蚂蚁觅食道路上的一个节点，而设备的不同加工时间就像路径的不同长度。若以最长完成时间最短作为生产调度的目标函数，则蚂蚁用于在蚁巢和食物源之间寻找最短路径的Stigmergy协商机制完全适用于车间的生产调度。并且这种间接通讯方式也为holon之间协调机制的设计提供了启发，可以在已有的Holonic控制架构中引进一种蚂蚁holon，如同蚂蚁在周围环境中散布和感知信息素一样，负责在制造环境中发现和传播信息。

经典的Holonic控制架构——PROSA架构[8]中定义了3种基本holon(资源holon、产品holon和订单holon)来分别对应制造系统主要涉及的3个相对独立方面：资源方面、产品和相关的工艺技术方面以及与交货期和供货相关的方面。此外，PROSA架构还定义了一种参谋holon(staff holon)用于为这三类基本holon提供专家信息，使基本holon能够正确解决问题。之后出现的一些Holonic控制架构多是在PROSA架构的基础上演化改进之后提出的[9-10]。因此，可以通过在PROSA架构中添加一类蚂蚁holon来建立基于Stigmergy的Holonic制造执行控制架构，其中各类holon的从属关系如图1所示。

图1　基于Stigmergy的Holonic控制架构中各类holon的从属关系

在基于Stigmergy的Holonic制造执行控制架构中，基本holon与参谋holon都能以一定的速率来创建各自对应的蚂蚁holon来负责信息的传播与接收。一方面，与真实环境中的蚂蚁一样，蚂蚁holon不仅要求数量很大，而且还要很“便宜”。其中，蚂蚁holon的数量可以通过设定创建速率来调整。另一方面，“便宜”是因为蚂蚁holon的内部属性与对应的holon相同，但并不具有与其对应的holon同等的功能，而只是负责感知和散发信息素，所以只需要有限的计算能力和通讯带宽[11]，而废弃这种holon只需释放一些计算机内存。

1.2holon单元的内部结构

通常情况下生产调度是由控制架构中的所有holon发挥自治与协作的特性共同实现的，holon之间协作的过程可能发生在任何需要的时间与地点，而且这一过程通常伴随着物料流、信息流以及与人的交互作用。所以，1个holon的基本内部结构应该包括以下4个部分：信息数据存储部分、决策制订部分、通讯处理部分以及物理操作和控制部分。为此，根据holon中递归嵌套的结构特性定义了4种内部holon：数据holon(data holon)、决策holon(decision holon)、通讯holon(communication holon)、结构holon(structure holon)，如图2所示。

图2　holon单元的内部结构

数据holon存储holon进行行为决策所需的信息，包括holon自身属性信息、其他holon信息等。决策holon根据数据holon中的信息进行行为决策，相当于执行制造控制功能，如对任务的调度、执行、监控以及对意外扰动的响应等。holon在一定的知识和信息基础上制订相应的决策，在一项决策执行之后，就变成新的知识被holon吸收，所以决策holon中除了决策机制之外，还应该包括学习机制和应对突发情况的自组织和自适应机制。通讯holon负责个体的holon与外界环境和其他holon的信息交互，支持各holon之间局部信息的分享。结构holon则为相关的仪器设备或操作者，负责执行决策holon作出的决策。这4类内部holon的属性见表2，表2中只给出了主要内容，未全部列举。

表2　内部holon的属性

1.3Stigmergy机制中信息素的定义

本文定义两种类型的信息素来供各holon之间进行协商活动，从而将Stigmergy机制的应用范围扩大到整个Holonic控制架构中，充分发挥Stigmergy机制优化性能高、通讯负荷低、适应性强等优点。

(1)第一类信息素。第一类信息素在基本holon以及参谋holon之间交换具体信息时使用。例如，当有订单下达到生产车间，订单holon便会创建order，蚂蚁holon在信息发布holon(information publish holon，IP holon)中留下信息素[N，O]，其中N为订单编号，O为订单信息，来供产品holon感知并获得相关的产品加工知识。信息发布holon模拟的是Stigmergy机制中蚂蚁所生活的环境，它是信息素的载体。这类信息素的运行机制强调Stigmergy机制中局部信息素的发布无需同步的特性。基本holon和参谋holon只需不断通过蚂蚁holon从信息发布holon中获取信息素或者将信息素释放在信息发布holon中，而无需通过约定的时间和地点交换信息。

(2)第二类信息素。第二类信息素应用于订单holon与资源holon协商搜索加工路径的过程中。这类信息素不包含任何具体内容，而是通过信息素的浓度高低来反映相应的资源holon对加工任务的吸引程度。由于在这一过程中信息素需要被频繁地感知和更新，故这类信息素通常以数值形式直接存储在资源holon中。这类信息素的运行机制模拟Stigmergy机制中蚁群觅食的过程。订单holon创建的蚂蚁holon在资源holon构成的网状图中，根据信息素的浓度选择一系列的资源holon节点，最终构成一条完整的加工路径。由于订单holon需要同时处理这两类信息素，为了区别以待，订单holon将创建两种蚂蚁holon(订单蚂蚁holon、路径蚂蚁holon)来分别对应处理这两种信息素，即路径蚂蚁holon与资源holon利用第二类信息素完成加工方案的搜索过程。

这两类信息素都具有挥发性，挥发速率ρ1、ρ2是可以设定的参数。对于第一类信息素，因为包含具体内容，其挥发速率ρ1通常较小，但是一旦被感知之后就会立即消失。如信息素[N，O]一旦被产品蚂蚁holon感知，表明产品holon已经接受了这一项任务，信息素[N，O]也就随之消失。这一特性保证了蚂蚁holon感知到的这一类信息素始终是有价值的、可用的，同时也保证了信息发布holon中始终都有一定的可用存储空间，降低了系统的通讯负荷。对于第二类信息素，当一条加工路径最终被选定为最优的加工路径时，这条路径上的所有资源holon中的信息素浓度将被加强。不在最优路径上的那些资源holon中的信息素则会随时间的推移不断挥发掉，即浓度会不断降低。这一过程将使加工时间较短的信息素浓度越来越高，对加工任务的吸引力越来越强，从而使路径蚂蚁holon的路径搜索过程逐渐收敛，最终得到最优解。

2　调度策略

2.1调度问题描述

作业车间调度问题一般可以描述如下：n个工件Ni(i=1,2,…,n)在m台机器Mk(k=1,2,…,m)上加工，每个工件由一组加工工序j(1≤j≤qi)组成，每道工序需要在指定的机器上加工，Oi,k,j表示第i个工件的第j道工序在机器Mk上加工。ti,k,j为工件Ni的第j道工序在机器Mk上的开始加工时间，Ti,k,j为工件Ni的第j道工序在机器Mk上的加工时间；di表示工件Ni的交货时间。需要满足的假设和约束条件如下。

(1)工件的每道工序一旦开始加工，在完成之前不允许中断。

(2)不考虑生产过程中出现的各种扰动。

(3)生产过程中的参数(如工件的加工时间、到达时间、交货期等)是确定的。

(4)每台机器在某个时刻只能加工一道工序，即工件i和工件p不能同时被加工：

tp,q,k-ti,j,k≥Ti,j,k

(1)

(5)在工件的前一道工序加工完成之后才能进行下一道工序的加工，即

ti,j,k-ti,j-1,k≥Ti,j-1,k

(2)

调度目标为最长完成时间最短，即

式中，tik为工件Ni在机器Mk上的完成时间。

2.2holon之间的协商过程

在本文中，默认当订单下达到生产车间时，已经过确认车间有能力进行加工。在不考虑扰动的情况下，当订单下达到生产车间后各类holon之间具体的协商过程如图3所示。图3的双箭头中，虚线表示使用第一类信息素，实线表示使用第二类信息素。

图3　各类holon的协商过程

协商过程具体步骤如下。

(1)当订单下达到制造车间时，系统便创建一个与该订单对应的订单holon。

(2)订单holon通过订单蚂蚁holon将信息素[N,O]释放在信息发布holon上，其中订单信息O包括订单要求加工质量和交货期等。

(3)产品蚂蚁holon读取到信息素[N,O]后反馈给产品holon，然后产品holon根据订单要求生成设计结果和工艺规划，再通过产品蚂蚁holon将信息素[N,P,I]释放到信息发布holon上，其中，P代表产品信息，如产品类型、产品设计结果等；I代表产品的加工工艺规划。

(4)订单蚂蚁holon读取到信息素[N,P,I]后，带回给订单holon。

(5)订单holon根据信息素的内容一次性生成一定数量的路径蚂蚁holon，这些路径蚂蚁holon携带工艺规划和订单信息与资源holon进行协商，确定初步的加工方案。

(6)订单蚂蚁holon把确定的加工方案信息素[N,M]释放到信息发布holon上，其中，M代表加工方案。

(7)参谋蚂蚁holon读取到信息素[N,M]后，根据其拥有的专家知识和经验，从全局的角度对方案进行可行性评定。若该方案可行，则通过参谋蚂蚁holon向信息发布holon释放方案确认信息素[N,M,OK]，其中OK代表可行。订单蚂蚁holon与资源蚂蚁holon读取到信息素[N,M,OK]后，开始根据这一方案进行加工。否则，参谋holon向信息发布holon释放信息素[N,M,NG]，其中NG代表不可行。订单蚂蚁holon与资源蚂蚁holon读取到该信息素后，返回步骤(4)，开始重新生成初步的调度方案。

2.3加工方案搜索机制

在2.2节的步骤(5)中，路径蚂蚁holon与资源holon协商确定初步加工方案的过程采用蚁群算法的原理来实现，为了能够完全模拟蚂蚁觅食过程中的路径形成机制，需要先根据订单构建对应的析取图。图4是一个3×4规模的生产车间调度问题的析取图。图4中，节点U、V是虚拟的起始节点和结束节点；h为节点编号，r=1,2,…,10，代表各个资源holon；每个节点编号上对应的(p,m)表示工件p在机器m上加工。实线弧为连接弧，代表加工的路线，如果连接节点(p,m1)和(p,m2)是实线弧，则工件p需要先在机器m1上加工后才能在机器m2上加工。属于两个工件且需要在同一台机器上加工的两个操作由两条方向相反的虚线弧(又叫析取弧)组成。从一个节点发出的所有弧，其长度都代表加工时间，从起点发出的弧的长度为0。

图4　3×4规模的生产车间调度问题的析取图

一个可行的加工方案相当于路径蚂蚁holon从起点U出发，从每对析取弧中选择一条直至到达终点V，并且中间不存在回路，这样的选择决定了该台机器加工操作的顺序。以最长完成时间最短为调度目标，一个可行加工方案的最长完成时间取决于起点U和终点V的最长路径。路径蚂蚁holon在由资源holon构成的析取图中从起点到终点的过程就如同蚁群中蚂蚁从蚁巢到食物源的过程，可以通过以下过程来模拟[12]： 路径蚂蚁holon从析取图的起点出发，根据可选资源holon节点中的信息素为下一步加工选择适合的资源holon，直到路径蚂蚁holon遍历所有的资源holon节点到达终点。当所有的蚂蚁holon都完成路径选择到达终点后，选择出最优的加工路径，并更新这条路径上的资源holon节点中的信息素，整个过程如图5所示。

图5　路径蚂蚁holon与资源holon的协商过程

状态转移规则和信息素更新规则如下。

(1)状态转移规则。在资源holon的选择过程中，路径蚂蚁holon并不是仅仅根据资源holon节点的信息素浓度来单纯选择信息素浓度最高的资源holon节点，因为这样容易使路径蚂蚁holon对节点选择过程陷入局部最优，并使最短路径的求解过程过早收敛。为了获得更好的求解结果，在选择过程中还要增加一些启发式信息，来平衡路径蚂蚁holon在最优加工路径的求解过程中的随机性。因此，路径蚂蚁holon依据由资源holon节点的信息素浓度和启发式信息共同决定的概率来选择下一步的节点。这一概率定义为[13]

(3)

信息素因子α的大小反映了路径蚂蚁holon在最短路径搜索中随机性因素作用的强度，其值越大，路径蚂蚁holon选择以前走过的路径的可能性越大，搜索的随机性越弱。α值过大也会使路径蚂蚁holon的搜索过早陷于局部最优。启发信息因子β的大小反映了路径蚂蚁holon在最短路径搜索中先验性、确定性因素作用的强度，其值越大，路径蚂蚁holon在某个局部点上选择局部最短路径的可能性越大。若β=0，蚁群就会选择信息素浓度最高的路径。

(2)信息素更新规则。路径蚂蚁holon的另一个功能就是改变最终选定的最优路径上的资源holon节点的信息素浓度。更新的公式为[14]

(4)

(5)

式中，Q为常数，表示路径蚂蚁holon完成一次搜索后释放在所经过的路径上的信息素总量；Lk为第k个路径蚂蚁holon从起点U到终点V所经过的总距离。

3　算例分析

本文以6×6的Muth&Thompson JSP基准问题为例来说明上述调度策略，已知最优解为55个单位时间。假设在t时刻编号为001的订单下达到生产车间，该订单包含6个加工任务以及每个任务的加工要求。6台加工机器分别抽象6个资源holon。

首先，系统为该订单创建一个与之对应的订单holon，订单holon通过订单蚂蚁holon将信息素[001,O]释放在信息发布holon上。产品蚂蚁holon读取到信息素[001,O]后反馈给产品holon。然后，产品holon根据订单要求O生成设计结果和工艺规划，见表3。最后，通过产品蚂蚁holon将信息素[001,P,I]释放到信息发布holon上。

表3　Muth&Thompson 6×6基准问题

表3中，N1的第一个加工工序在机器3上加工，加工时间为1个单位时间；第二个加工工序机器1上完成，加工时间为3个单位时间，以此类推。

订单蚂蚁holon读取到信息素[001,P,I]后，带回给订单holon。订单holon根据信息素的内容一次性生成一定数量的路径蚂蚁holon，这些路径蚂蚁holon携带着工艺规划和订单信息与资源holon进行协商，确定初步的加工方案。加工方案搜索过程利用MATLAB R2012a编程求解，取最大迭代次数为200，α=0.8，β=0.4，ρ2=0.5，τ0=1，蚂蚁数为100，Q=1。最后的运行结果如图6所示。

图6　最佳加工方案进化曲线

订单蚂蚁holon把确定的加工方案信息素[001,M]释放到信息发布holon上。参谋蚂蚁holon读取到信息素[001,M]后，根据其拥有的专家知识和经验从全局的角度评定该方案可行，之后通过参谋蚂蚁holon向信息发布holon释放方案确认信息素[001,M,OK]。订单蚂蚁holon读取到信息素[001,M,OK]后，决定开始根据这一方案进行加工。

上述过程就是作业车间中从订单下达到提出一个初始加工方案的完整过程，最终得到的最长完成时间为55个单位时间，与已知的最优解相同。在此过程中，基本holon与参谋holon通过蚂蚁holon使用信息素进行信息的交互与协商，最终实现生产调度的功能。

4　结语

本文通过创建多种属性的蚂蚁holon构建了基于Stigmergy的Holonic制造执行控制架构，并定义了该架构下holon单元的内部结构，使得holon自治与协商的过程更加清晰和明确。通过定义两种形式的信息素，使得holon之间协商所需的信息都能够通过信息素的形式来表达，为在整个Holonic控制架构中使用Stigmergy机制提供了必要条件。在此基础上，提出了在基于Stigmergy的Holonic控制架构下各holon单元协商完成作业车间调度问题的基本策略，最后通过一个基本案例证明了该策略的有效性。本文仅针对基于Stigmergy的Holonic制造执行控制架构下的作业车间调度问题进行了初步研究，未考虑调度执行过程中可能发生的扰动事件，后续研究将侧重于扰动事件对生产过程的影响，实现基于Stigmergy的Holonic制造执行控制架构下作业车间的动态调度。

[1]Valckenaers P, Van Brussel H, Verstraete P, et al.Schedule Execution in Autonomic Manufacturing Execution Systems[J].Journal of Manufacturing Systems，2007，26(2)：75-84.[2]Valckenaers P, Van Brussel H.Holonic Manufacturing Execution Systems[J].CIRP Annals Manufacturing Technology，2005，54(1)：427-432．

[3]Verstraete P，Valckenaers P.Towards Cooperate Planning and Manufacturing Execution Systems[C]//The 12th IFAC Conference.Saint-Etienne,2006:371-376.

[4]Karuna H，Verstraete P，van Brussel H，et al.Production Planning and Control in Bio-inspired Holonic Manufacturing Execution Systems[C]//8th IFAC International Workshop on Intelligent Manufacturing Systems. San Vicente del Raspeig，2007：42-49．

[5]Barbosa J，Leitao P，Trentesaux D，et al.Enhancing ADACOR with Biology Insights Towards Reconfigurable Manufacturing Systems[C]//IECON 2011-37th Annual Conference on IEEE Industrial Electronics Society. Melbourne,2011：2746-2751．[6]WangLei，TangDunbing，GuWenbin，etal.Pheromone-basedCoordinationforManufacturingSystemControl[J].JournalofIntelligentManufacturing，2012，23(3)：747-757.

[7]GaoQinglu，LuoXin，YangShuzi.StigmergicCooperationMechanismforShopFloorControlSystem[J].TheInternationalJournalofAdvancedManufacturingTechnology，2005，25(7)：743-753．

[8]BrusselHV，WynsJ，ValckenaersP，etal.ReferenceArchitectureforHolonicManufacturingSystems:PROSA[J].ComputersinIndustry，1998，37(3)：255-274．

[9]LeitaoP，RestivoF.ADACOR：aHolonicArchitectureforAgileandAdaptiveManufacturingControl[J].ComputersinIndustry，2006，57(2)：121-130．

[10]PujoP,BroissinN,OunnarF.PROSIS:anIsoarchicStructureforHMSControl[J].EngineeringApplicationsofArtificialIntelligence，2009，22(7)：1034-1045．

[11]ValckenaersP,HadeliK,GermainBS，etal.MASCoordinationandControlBasedonStigmergy[J]．ComputersinIndustry，2007，58(7)：621-629．

[12]Scholz-ReiterB，deBeerC，FreitagM，etal.Bio-inspiredandPheromone-basedShop-floorControl[J].InternationalJournalofComputerIntegratedManufacturing，2008，21(2):201-205．

[13]ShiKe，QinXuan.StigmergyBasedAutonomousShopFloorControlwithWirelessSensorNetworks[C]//9thIEEEInternationalConferenceonIndustrialInformatics.Lisbon，2011：375-380．

[14]DorigoM,ManiezzoV,ColorniA.TheAntSystem:OptimizationbyaColonyofCooperatingAgents[J].IEEETransactionsonSystems，ManandCybernetics-PartB，1996，26(1)：1-13．

(编辑陈勇)

A Stigmergy-based Holonic Control Architecture and Scheduling Strategy

Tang HongtaoLiu LuChen MingLu Jiansha

Zhejiang University of Technology,Hangzhou,310032

Aiming at the hierarchical control architecture of manufacturing execution system and the application limitations of Stigmergy in Holonic control architecture, a Stigmergy-based Holonic control architecture was proposed by introducing an ant holon for every basic holon and staff holon.Four internal holons (data holon,decision holon,communication holon and structure holon) were designed for each holon unit.According to different application scopes two types of pheromones were defined. Aiming at the optimization objective of total completion time,a basic Job Shop scheduling strategy achieved by each holon unit under the Stigmergy-based Holonic control architecture was proposed. The validity of the method was verified through an example calculation.

job-shop scheduling; Holonic control architecture; Stigmergy negotiation mechanism; ant colony algorithm

2013-10-16

国家自然科学基金资助项目(70971118,71101129)；浙江省自然科学基金资助项目(Y1111118，LY12E05021)；浙江省科技厅重大科技专项和优先主题项目(2009C11164)

TH186DOI：10.3969/j.issn.1004-132X.2015.01.009

汤洪涛，男，1976年生。浙江工业大学工业工程研究所副教授。主要研究方向为生产过程管理、制造执行系统、生产计划与调度、生产与物流系统建模与仿真。发表论文30余篇。刘璐，女，1989年生。浙江工业大学工业工程研究所硕士研究生。陈明，女，1987年生。浙江工业大学工业工程研究所硕士研究生。鲁建厦，男，1963年生。浙江工业大学工业工程研究所教授。