生产车间混合式控制结构模型和协商机制研究

王世进 段永瑞

同济大学,上海,200092

0 引言

生产控制系统的体系结构用于确立控制系统内实体的决策功能分配方式及这些实体间的相互关系,并由此建立一种用于协调不同决策实施过程的机制。控制体系结构是整个系统逻辑活动的支柱(backbone)[1]。设计具有适应性的体系结构,是车间控制系统在实现与上下层信息系统集成的同时,能对动态变化的车间外部需求和内部环境实现敏捷应变的基础和关键,因此具有重要的研究意义。在过去的40多年中,围绕着可靠性、可扩展性和适应性等要求,学术界和企业界对制造控制系统体系结构展开了大量研究,控制体系结构也不断发展,经历了集中式、递阶式、混合式和异构式4种形式的变迁[2]。近些年来,结合递阶式结构合理层次性和异构式结构自适应性的混合式结构日益受到重视。根据结构中异构与递阶程度的不同,混合式控制体系结构有多种不同形式,具有一定的灵活性,但在如何降低控制体系结构设计难度,实现车间生产动态适应性优化协调控制方面还存在许多值得进一步研究的问题。

近年来,基于Agent(或Holon)的混合式控制体系结构得到了广泛研究[3-7],这是由于Agent(或Holon)潜在的自治性、交互性、反应性和主动性等属性与制造环境中多个相互关联的独立系统之间信息和决策逻辑/地理上分布的性质非常适合[3]。基于Agent的混合式控制体系结构的基本思路是将整个系统分割成各个独立的自治Agent,从而将传统的集中决策与控制分散到众多的自治Agent上进行,具有异构式控制的特点;同时建立Agent之间的协调机制,协调Agent之间的行为,实现共同的优化目标,又具有递阶式控制的特点。因此,基于Agent的混合式体系结构得到了研究者的广泛青睐。如PROSA体系结构(product—resource—order—staff architecture)[4]、适应性生产控制系统(adaptive production control system,APCS)体系结构[5]、引入中介Agent的MetaMorph体系结构[6];Sunderesh等[7]设计的结合静态层次结构和实时任务分配机制的混合式控制体系模型等。

各种基于Agent的混合式控制体系结构的决策协商机制一般都采用合同网协议或其改进形式,但采用优化和学习机制以减小协商通信负荷和提高协商效率的研究尚不多见。鉴于此,本文提出内嵌结合投标和示例学习协商机制的混合式控制体系结构,为进一步改进协商和控制性能打下了基础。

1 基于Agent的车间控制系统适应性控制结构模型

提出的车间控制结构模型如图1所示。映射车间中不同的资源或功能,模型由系统优化Agent、单元协调Agent和单实体Agent(包括产品Agent、资源 Agent)形成三层递阶结构,允许同层Agent之间及不同层 Agent之间的交互。模型以同层Agent之间的自由协商交互为主,上层Agent根据上层性能指标为下层Agent之间的协商提供一定的协商辅助和决策参考,避免由于自由协商引起的系统混乱或不稳定状态。各Agent可位于对应的物理实体上,也可位于独立的计算机系统上。其相关结构和功能描述如下:

(1)产品 Agent。产品 Agent由系统优化Agent根据车间加工任务生成,对应系统的加工订单作业。其基本功能包括:确定加工序列;推算工序的最迟开始时间tLS;评价标书,选择最好的标书,确定工序加工分配。产品Agent包括标识码(唯一)、权重、下达时间tR,交货期 tD、可选工艺路线、状态信息、协商协议库等信息。当产品Agent中的状态信息表示产品或作业已经完成时,由系统Agent注销该Agent。

(2)资源Agent。资源Agent建模和封装车间内的加工资源。除表示机床外,也可以表示工作站、机器人、人、自动导向小车(automated guided vehicles,AGV)、传送带等。资源Agent根据自身加工能力、运行状态和产品 Agent要求,与其他资源Agent协商确定产品Agent的加工。资源Agent对所获得的加工任务进行局部调度,并根据车间实时情况对调度进行动态调整。资源Agent中存储的信息包括两部分:一是对应物理资源的加工与工艺的能力数据库,这些数据较为稳定;二是各个物理资源的状态数据库,包括运行状态数据、负荷状态数据、资源Agent的计划和调度数据等。其内部结构(图2)包括等待序列、协商协议模块、调度模块、学习模块、调度结果以及能力数据库、状态数据库、调度算法库和熟悉资源Agent库。当接收到产品Agent的加工请求后,资源Agent将加工请求放入协商等待序列中,根据权重程度依次排序,同时由该产品Agent中的工序路线信息,更新资源Agent对该产品Agent的熟悉资源Agent库。资源Agent与产品Agent就要加工的工序用基于招投标机制和示例学习方法的协商机制进行协商。在能力数据库、状态数据库所提供信息的辅助下,通过协商协议模块与产品Agent或其他资源Agent进行协商。调度模块确定资源上的优化调度,产生的调度结果作为指令发送给资源实体。学习模块可以容纳如Q—学习等强化学习方法以提高资源Agent的动态调度能力。

(3)系统优化Agent。系统优化Agent负责与车间外部的联系,主要接收车间上层指令,把车间信息反馈给上层信息系统,方便车间与制造系统中其他信息系统的集成等;同时监控车间内各Agent的状态;动态生成和注销资源Agent、产品Agent。其结构主要包括元数据转换模块、系统桥接模块、车间状态监控模块、系统性能指标库和协调模块等。

(4)单元协调Agent[1]。单元协调Agent表示资源Agent和产品Agent以逻辑方式组成的单元,实现产品任务或特定作业的加工。该Agent主要负责与其他单元协调Agent单元的生产任务协调,辅助产品Agent就具体的工序加工任务与资源Agent的协商。其结构主要包括单元性能指标库、控制模块、推理工具和协商模块等。

2 基于投标和示例学习的协商机制

Agent之间的协商过程取决于协商机制。Agent协商机制是一组用来组织和约束Agent之间对话序列和决策的规则集。现有的各种制造控制系统,在定义各 Agent之间协调和合作关系时,几乎都是采用合同网协议或其改进形式[3,5-6]。但是传统的合同网协议仅仅规定工作过程,本身没有优化能力,而且当系统中Agent数量较多时,合同网协议过程中的招投标通信将大幅增加系统的网络通信负荷,而各种改进合同网协议在实现上有一定的难度。为此,以合同网协议中最核心的投标(bidding)过程为基础,结合调度算法和基于示例学习方法,提出一种新的协商机制,目的是在易于实现和减小通信负荷的前提下,能应对车间可能出现的各种扰动情况(如机床故障、急单进入等),从而提高协商效率和性能。图3是协商机制的统一建模语言(unified modeling language,UM L)活动图,即整体活动流程。图3中tC为系统当前时间,t为系统中任意两Agent间一次通信所耗费的最长时间,tEF为工序的最早完成时间,tij为产品Agent i和资源Agent j之间的一次通信时间,K为产品Agent欲发送投标请求的资源 Agent数,避免以广播方式发送投标请求。该协商机制的整体思路是:当一产品Agent工序的最迟开始时间tLS＞2t+tC(即产品Agent的交货期比较紧)时,采用基于示例学习方法直接确定工序加工任务的分配计划,以提高协商效率,降低通信负荷;否则,就采用完整的投标协商机制。

2.1 时间约束算法(算法1)

该算法主要用来确定产品Agent所表示的各作业工序的计划下达时间tR、交货期tD和最迟开始时间tLS,具体算法如下:

其中,Pi为产品Agent i(i为作业总数,i=1,2,…,n)所表示的作业;in为Pi的工序总数;Oij(j=1,2,…,in)为Pi的其中一道工序;M(Oij)表示能加工工序Oij的机床集(由资源Agent映射);tP(Oij,Ml)为工序Oij在机床Ml(l∈M(Oij))的加工时间。

每道工序等待机床投标的时间确定为tLS(Oij)—tR(Oij)—t。一旦等待时间结束,产品Agent就选择具有 min(tij+tEF)的机床,即min(tij+tEF)是产品Agent i的目标。在具体情况下,根据订单的不同需求,通过评价和选择逻辑,Agent可以动态改变目标,如采用加工成本尽可能小和总通过时间最小[3]。如果有两台以上机床具有相同的最小值,则进一步选择当前负荷小的一台。

2.2 资源调度模块(算法2)

该算法主要用于确定资源Agent所表示资源(主要是机床)的优化调度。每个资源Agent都有自己的目标,根据该目标评估选择产品Agent的投标。本文定义资源Agent的目标是机床利用率和工序最小平均延误的权重和。该目标可以表示为

这里,w1＞0,w2＞0,w1+w2=1,如果tD(Oij)—(tS(Oij,Ml)+tP(Oij,Ml))＞0,则 w2=0。其中,~L、~Uml为接收到新投标请求前的机床负载和利用率;tC(Oij,Ml)为工序Oij在机床Ml上的加工结束时间;tS(Oij,Ml)为工序Oij在机床Ml的开始加工时间。

在接收到新招标时,设Tl为在机床Ml上已经安排加工的工序集,Ol为其中的一道工序,tS(Ol)、tC(Ol)分别为Ol的开始加工时间和结束时间,则资源调度模块具体算法可以描述如下:

(1)确定 T1={Ol|∀Ol∈ Tl,且Ol为Oij在工艺路线上的前面工序},T2={Ol|Ol∈Tl,tC(Ol,Ml)＜tR(Oij,Ml)}。

(2)初定 tS(Oij,Ml)=max(tC(Ol),tR(Oij)),Ol∈T1∪T2。

(3)当tS(Oij,Ml)≤tC(Tl)时,①确定T3={Ol|∀Ol∈(Tl—T1∪ T2),tS(Oij,Ml)＜tS(Ol)＜tC(Oij,Ml)or tS(Oij,Ml)＜tC(Ol)＜tC(Oij,Ml)};②如果 T3=∅,计算Gml,否则,向后移动工序Oij,改变tS(Oij,Ml)。

(4)比较得到的各个Gml,选择具有最小Gml的tS(Oij,Ml)。

确定工序的开始加工时间后,生成标书,确定tEF(Oij,Ml)=tS(Oij,Ml)+tP(Oij,Ml)和机床负载。当同时接收到多个产品Agent的投标请求时,机床分别比较接收各个工序可能获得的目标值,如果各个工序的开始加工时间合理,则全部接收;如果选择多个工序存在冲突,就选择具有最大目标值的工序,并返回该工序的最早结束时间和接收后的机床负载,同时拒绝其他产品Agent的请求。

2.3 基于示例的学习方法(IBL算法)

为了减小通信负荷,引入了基于示例学习(instance based learning,IBL)的机制。基于示例学习是一种基于记忆的机器学习方法。k近邻方法(k—nearest neighbour,kNN)是这种学习方法的典型代表[8],该方法的基本思想是找出新示例的k个近邻,看这k个近邻中多数属于哪一类就把该新示例归为那一类。该方法具有学习速度快、学习结果易理解以及具有较高预测准确性等特点[8]。Deshpande等[9]把kNN方法与合同网机制结合用在虚拟的分布式医院系统的资源共享上,并通过仿真示例验证了其有效性。本文提出的是基于示例的学习方法。

工序分配的示例历史库存储在系统优化Agent中。随着新的订单不断进入,车间中工序分配示例将不断增加。为了减小数据库的存储负荷,系统优化Agent采用先进先出的循环队列存储历史示例。循环队列的长度为l,l可以固定不变,也可以根据车间情况实时调整。这样,历史示例表示为HI={I1,I2,…Il}。一个工序的分配情况是否可以作为历史示例,需要根据实际加工延误确定。如果系统优化Agent监测到工序加工的实际情况是tC(Oij,Ml)—tD(Oij)＞θ(θ为系统的延误限定参数),则认为实际加工延误,不能加入示例历史库;反之,就插到历史示例循环队列的末尾,作为新的历史示例,同时旧的示例自动从循环队列中删除。

2.4 扰动情况的协商方法

当一台机床发生故障时,原先计划在该机床上加工的工序需要重调度。表示故障机床的资源Agent在警示故障后就被系统优化Agent注销。原先分配在故障机床上的工序及其受影响的后续工序都根据图3所示(灰色部分)协商机制进行重调度,分配到其他可选机床上;如果工序没有其他机床可选,则工序所属产品将一直延误等待直到机床恢复正常才重新开始加工;如果工序加工过程中,机床发生故障而且工序加工不允许中断,则工序所属产品取消。异常情况下的重调度由单元协调Agent负责,利用过滤定向搜索(filtered—beam—search based algorithm)算法[10]实现。

以机床故障为例(图3中灰色部分),由于加工不允许中断,已开始加工但尚未完成的工序将不纳入重调度范围,确定这些工序所在机床的继续占用时间为t0+Δtk(k=1,2,3,…,M),其中Δtk为工序在机床Mk上的剩余加工时间;在t0时刻空闲的机床的剩余加工时间Δ tk=0。动态调度决策器把这些信息转换成瞬时静态调度问题模型,并激活过滤定向搜索算法进行调度。得到的新调度衔接原有的旧调度,衔接时确定各机床的最早开始时间为max((t0+Δ t),(t0+Δtk));其中,Δt为应用算法计算新调度所需的时间,它与算法效率有关。Δt越小,动态调度效率越高。

3 原型系统设计

为了验证控制结构模型的可行性和协商过程,利用JADE[11]构建了原型系统。

3.1 原型系统软件体系结构模型

如图4所示,结构从下到上分为4层,分别是提供网络通信的底层网络协议层,提供软件运行环境和数据访问环境的操作系统、数据库层,提供JADE运行环境和Agent之间消息通信服务的Java虚拟机、网络协议堆栈(remote method invocation over the internet inter—ORB protocol,RMI/IIOP)层及基于JADE(Java Agent development framework)平台的控制系统应用层。

结构模型中所涉及的各实体Agent用Java语言在JADE平台上开发,位于不同的容器内,容器可位于网络内不同PC上。容器分为主容器和Agent容器。主容器内包括黄页目录管理器(directory facilitator,DF)和Agent管理系统(agent management system,AMS)。每个Agent都必须在Agent管理系统上注册并获得Agent唯一标识名才能运行。黄页目录管理器为各Agent提供服务注册、服务查询等功能。系统优化Agent位于主容器内,其他Agent可位于主容器内,也可位于Agent容器内(不同的Agent容器可以位于不同电脑上)。各个Agent异构分布,通过消息传递系统(message transport service,MTS)相互合作协商完成控制任务。

3.2 包图设计

图5是原型系统包图的核心部分,主要描述了领域层和技术服务层中的包以及包所含的各个类。领域层内的包集中表示车间调度功能,包括单元协调包、系统优化包、产品包、资源包和包含各核心算法的启发式算法包。技术服务层描述JADE库的包和类,主要包括描述Agent界面的jade.gui包,描述Agent命名的jade.lang.ad包,描述Agent行为的jade.core.behaviours包以及描述Agent交互协议的jade.proto包等。两个层次包和类之间的相互关系(主要是依赖和泛化关系)也在图5中进行了表述。

3.3 仿真界面

JADE平台上开发的Agent,相互交互之前必须在Agent管理系统上注册。注册后,由远程监控Agent(remote monitoring agent,RMA)实时管理。本文仿真设计了产品Agent、系统优化Agent和3个单元协调Agent的简单系统,其仿真界面如图6所示。3个单元协调Agent分别位于网络的 3台不同电脑上(电脑名分别是wsjwangjing、yjb、iem —zbh),系统优化 Agent和产品Agent位于wsjwangjing电脑的主容器内。得到的RMA界面如图6a所示,3个单元协调Agent分别为CCA—WSJ、CCA—YJB和CCA—WHT。系统优化Agent的界面和单元协调Agent的界面分别如图6b和图6c所示。系统优化Agent通过产品(作业)控制树管理作业招标,定义和设定当前作业的招标参数,并显示当前作业的调度信息。单元协调Agent主要接收作业招标,对当前作业招标进行评估并作出决策,以及实现单元内产品Agent(作业)和资源Agent的实时调度结果。

4 结束语

提出了一种基于Agent的适应性混合式车间控制系统体系结构。为了提高Agent之间的协商效率和性能,减小通信负荷,应对车间可能出现的各种扰动情况,设计了基于投标机制和示例学习的协商机制,并重点分析了协商机制的4个核心算法(时间约束算法、资源调度模块、IBL算法和扰动情况算法)。最后,在JADE环境中构建了原型系统,分析了软件体系结构、包图和仿真界面。提出的混合式控制体系结构为进一步改进协商和控制性能打下了基础。

[1]Heikkila T,Kollingbaum M,Valckenaers P,et al.An Agent Architecture for M anufacturing Control:Manage[J].Computers in Industry,2001,46(3):315-331.

[2]周炳海,王东,奚立峰,等.基于 Agent的制造单元混合式控制系统研究[J].计算机集成制造系统—CIMS,2004,10(3):292-297.

[3]Chan F T S,Zhang J.A Multi—agent—based Agile Shop Floor Control System[J].International Journal of Advanced Manufacturing Technology,2002,19(10):764-774.

[4]Brussel H V,Wyns J,Valckernaers P,et al.Reference Architecture for Holonic Manufacturing Systems:PROSA[J].Computer in Industry,1998,37(3):255-274.

[5]Ottaway T A,Burns J R.An Adaptive Production Control System Utilizing Agent Technology[J].International Journal of Production Research,2000,38(4):721-737.

[6]Maturana F,Shen W,Norrie D H.Metamorph:An Adaptive Agent—based Architecture for Intelligent Manufacturing[J].International Journal of Production Research,1999,37(10):2159-2173.

[7]Sunderesh S H,Robert J G,Byung—In K,et al.Intelligent Agent Based Framework for Manufacturing Systems Control[J].IEEE Transactions on Systems,Man,and Cybernetics—Part A:Systems and Humans,2002,32(5):560-571.

[8]Aha D W,Kibler D,Albert M K.Instance—based Learning Algorithms[J].Machine Learning,1991,6(2):37-66.

[9]Deshpande U,Gupta A,Basu A.Performance Enhancement of a Contract Net Protocol Based System Through Instance—based Learning[J].IEEE Transactions on System,Man,and Cybernetics—Part B:Cybernetics,2005,35(2):345-358.

[10]Wang Shijin,Xi Lifeng,Zhou Binghai.Filtered—Beam—Search—Based Algorithm for Dynamic Rescheduling in FMS[J].Robotics and Computer—Integrated Manufacturing,2007,23(4):457-468.

[11]Bellifemine F,Caire G,Poggi A,et al.JADE:a Software Framework for Developing Multi—agent Applications.Lessons Learned[J].Information and Software Technology,2008,50(1/2):10-21.