多Agent分布式车间动态调度仿真系统研究

宋 娟

（宁夏大学 物理电气信息学院，银川 750021）

0 引言

制造车间调度问题（Job Shop Scheduling Problem，JSSP），是典型的NP-hard问题[1]，并且被认为是最难解决的问题之一。另外，由于车间调度问题是多目标的，具有复杂性和动态随机性，致使不确定时间出现的频率明显高于传统的制造环境，生产调度更多的表现为动态调度问题。

为适应时代化制造系统对柔性和快速重组的要求，提出以分布式MAS作为新的运作模式，综合OOT技术和CORBA通信机制，设计并实现了一种分布式制造车间调度仿真平台MASS，实现现代制造车间生产过程的动态调度，为将来MASS的实用化奠定基础。

1 MASS仿真系统的组成和相互关系

以典型的机械加工车间作为生产调度仿真系统的原型。为了满足生产调度的功能要求，该车间按照生产单元布局，每个单元中的机器至少能完成一种或是一类工件任务的加工，同时每个工件任务可有一个或多个单元完成。MASS基本布局如图1所示。

图1 基于MAS的分布式车间调度系统模型

生产调度系统由管理Agent、资源Agent和工件Agent组成，从面向对象的观点看，这些Agent分布在不同的物理环境中，通过局域网连接在一起。考虑到系统的规模需要，在仿真系统中，系统层设有1个管理Agent，每个单元设一个单元管理Agent，下设若干资源Agent和工件Agent。

多Agent系统（Multi-agents System）放松了对集中式、规划和顺序控制的限制，提供了分散控制、应急和并行处理，提供更快速的问题求解。这样，制造系统便可以通过分布在车间里的资源和个体Agent之间的联合来实现系统的集成。

2 MASS仿真系统设计

2.1 面向对象的MASS仿真功能模型

按照上述系统模型，设计了面向对象的仿真系统功能，结构如图2所示。

2.2 Agent之间协商机制

由于车间调度问题是多目标的，具有复杂性和动态随机性， Agent在做出自身决策的同时还要考虑系统内其他Agent的行为，系统的整体目标需要由Agent共同实现。因此，Agent之间的协作尤为重要。建立良好的协商、合作策略是Agent有效完成调度任务的基础，也是各Agent解决不同问题所采用具体调度策略的基础。

图2 仿真系统的功能模型

在这个系统中有至少两种Agent：管理Agent（Manage Agent，MA）和 下 级 Agent（Subagent，SA）。在 MASS中，单元 Agent、资源 Agent和工件Agent 都可以看作是MA的subagent。其中，MA负责任务的分解，监视任务的执行，并处理运行结果；SA负责任务的真正执行。

2.3 通信的实现

良好的通信机制是实现Agent之间信息交换与互操作的基础手段。Agent之间的通信可以采用基于WinSock的消息传递机制实现，也可以采用面向对象的中间件技术CORBA实现。这里采用CORBA技术实现MASS底层通信。CORBA作为分布式开放系统的互连协议，可以突破以往基于参数传递信息的局限，提供了以对象为中心的互操作技术。

根据Agent通信的要求，运用CORBA复杂对象包装/传递技术，即设计人员必须定义对象的状态如何在网络上传输的包装函数（marshalling functions）和接收过程的解包函数（unmarshalling function），定义了三类Agent的IDL接口，可以支持异构Agent之间的通讯与互操作。

3 MASS仿真系统实现

3.1 实验系统结构

系统按照如图1所示的布局，在仿真系统中设计了三个生产单元CA(Cell Agent)，每个单元都有三类机床：车床Lathe、磨床Mill和钻床Dill，每类有若干不同型号的机床可供选择。每个机器各有一个输入和输出缓冲区，分别能存放一个工件；每个单元有一个公共存储区；每个单元内各设两个AGV为这些机器运进所需的原料、运出操作完的工件。

3.2 仿真实验

设计本次试验的目的是验证MASS的可行性。试验中，任务的分配与执行调度选择先进先出（FIFO）调度策略。

1）管理Agent从调度任务表Task_list中选择优先级最高的任务，采用多点传送的方式，参考知识库中的信息，向有能力的单元CA1、CA2和CA3发布任务。任务包包括订单编号、工件编号、数量、工序和交货期，每一项操作信息为一个五元组，运行实例中发布的任务包为：

＜Order_No，Part_No，Quantity，Operation，Due_Date＞ = ＜Order1，Patrt3，2，3，186＞；

2）一旦CA1、CA2和CA3接到发布的任务信息，将接到的任务信息作为一个记录保存在任务表单Task_list中，参考工艺数据库中任务相关数据，包括加工设备类型，加工时间和服务成本，加工单元CA1预调度结果；

3）管理Agent从落选的两个单元Agent中选择一个作为后备单元，将相关信息保存起来，以备出现机器故障、任务拖延等异常情况时使用，目的是减少事故的处理时间、降低事故损害。同时，管理Agent还要通告单元CA2和CA3，结束该次任务的协商分配、过程。

实验结果证明了MASS能够完成预期的调度任务。虽然调度结果不是最优，但MASS调度问题的求解与通讯时间包含在工件的整个加工流动当中，求解时间短，响应速度快，应用于动态调度具有一定优势。

4 结束语

由于采用多Agent结构与基于CNP的调度协商机制，使现代制造车间动态调度得以有效实施。通过运用面向对象方法对MASS建模，设计并实现了一种开放式、动态变化MASS分布式仿真系统。通过CORBA机制实现了Agent之间的通信，模拟了制造车间多目标优化调度过程。实验结果证明该系统可应用于MAS控制系统仿真、设计及实际运行控制。Agent具有的智能性、自治性及合作能力等许多优良特性，为解决现代制造系统的车间动态调度问题提供了一条新的有效途径。

[1] Nabil Nasar, Elsayed EA. Job Shop scheduling with alternative machines[J]. International Journal Production Research, 1990, 28(9): 1595-1609.

[2] 乔兵, 等. 基于Agent的分布式动态作业车间调度[J]. 信息与控制, 2001, 30(4): 293-296.

[3] Garey M R, Johnson D S, Sethi R. The Complexity of Flow-shop and Job shop Scheduling, Math.Oper.Res. 1976,117-129.

[4] 邱郁惠. 系统分析师UML实战[M]. 北京: 机械出版社,2010.