在技术不断革新的今天，制造系统需要不断提高自身敏捷性、柔性、鲁棒性来保持竞争力。Agent技术是分布式人工智能的研究热点，被认为是构建制造系统的重要方法之一^[1]。作业车间调度是制造系统中的基本问题之一^[2]，对制造过程有着重要意义。基于Agent的车间调度大多采用合同网协议^[3](Contract net protocol，CNP)作为协商机制。

CNP是一种协作过程，用于分布式求解问题中节点之间的任务分配。节点间任务的发起者和参与者构成合同关系。合同网协议为Agent交互提供了一种有效且具有现实意义的协商机制，并在工业上获得了成功应用^[4-5]。尤其是在基于多Agent的制造系统中，合同网协议可以灵活应对不同情形，动态地完成资源分配^[6]。在基于多Agent的AGV(Automated guided vehicle)调度研究中，Mes等人^[7]在选择最佳Agent构架中利用合同网协议作为协商机制；Fazli等人^[8]根据任务的动态分配提出了改进FIPA (The foundation for intelligent physical agents) 合同网协议。传统合同网协议在交互过程中需要反复协商，信息通讯量过会大导致系统性能下降，许多研究者从多个角度提出了不同的改进方案。Schillo等人^[9]提出了合同网扩展协议，并对给定问题域下最优机制的决策标准进行了讨论。为了减少Agent间通讯量以及评估时间，甘璐等人^[10]提出了一种基于投标结果修正的合同网协议。王世进等人^[11]利用强化学习结和合同网协议来解决调度问题。张广胜等人^[12]提出代价时间Petri网以分析合同网协议协商过程。为避免投标并发操作导致调度质量下降的问题，赵良辉^[13]弃用了合同网框架，提出了一种基于时间流的调度模型。该模型虽然保证了调度的正确性，但失去了合同网协议的灵活性。由于招投标双方不能同时从自身角度对调度进行优化，这导致了整体调度性能的降低。

针对上述问题，本文在合同网协议的基础上，提出了基于节拍的改进合同网协议。该协议简化了合同网协议以减少Agent间的通讯量，通过节拍保证了投标并发操作的调度质量，并在竞标过程中引入阈值策略，进一步提高改进合同网协议的效率。最后，对一个基于节拍合同网协议的车间AGV调度系统进行仿真实验，验证该协议的可行性。

1 问题描述

在基于多Agent的作业车间调度中，通常用两类Agent分别模拟任务和机器，通过任务Agent(Task agent，TA)和机器Agent(Machine agent，MA)之间的交互，实现机器在任务上的分配，最终形成调度方案^[13]。TA和MA的协商频繁导致通讯量迅速增加。为了减少通讯量，本文对传统合同网协议进行简化，其结果如图 1所示。简化合同网协议可以使每次招投标过程的通讯次数减少至3次，这既保留了合同网协议的灵活性，又满足了应用场合的实时性需求。但是，这种简化的合同网协议在招投标过程中存在并发操作，并且可能导致竞标出错。下文以传统合同网协议和简化合同网协议为例，将具体描述招投标并发操作导致恶劣竞标的起因、过程和结果。

简化合同网协议中共有两类Agent：TA和MA。其中TA发起招标并决策，MA参与竞标并进行投标。TA和MA相互协商、协作共同完成任务，其过程如图 2所示。其中，TA={TA_i︱i=1,2,…,I}；MA={MA_j︱j=1,2,…,J}；双向实线箭头表示一个TA同时向一个或多个MA发起招标；双向虚线箭头表示一个MA同时接受一个或多个TA招标。TA从自身利益出发，在所有MA中选取投标书最优的MA进行合作。由于MA对不同TA的投标相互独立且具有并发性，这可能导致MA同时中标多个任务并导致劣质竞标。

假设TA₁和TA₂同时向MA₁发起招标，且MA₁能分别独立完成TA₁和TA₂的任务，但每次只能执行一个任务。TA₁的招标任务为T₁，TA₂的招标任务为T₂，T₁和T₂所需工时分别为5和10。简化合同网协议中，TA与MA招投标的具体交互过程如下：

(1) TA将任务封装在招标书中，并向MA发起招标；

(2) MA收到标书后进行评估，然后向TA发送投标；

(3) TA对投标书进行决策，决定是否签订合同。

两种合同网协议的招投标的过程和结果如图 3所示。传统合同网协议中，MA₁同时中标任务T₁和T₂，其虽然能够完成任务的调度，但投标书中完工时间和合同完工时间相冲突，缺乏了一定的柔性；简化合同网协议中，MA₁同时和TA₁、TA₂签订合同，这虽然能够减少Agent通讯次数，但两份合同中加工时间冲突，出现了任务重叠问题，因此不能按时完成任务。为解决此问题，下节提出了一种基于节拍的改进合同网协议。

2 改进合同网协议

针对简化合同网协议中投标并发操作，本文提出了一种基于节拍的改进合同网协议，并在Agent协商过程中引入了阈值策略，优化了TA和MA。

2.1 节拍合同网协议

节拍是一个时间区间，共有两个时间节点。开始节点为一轮招投标的发起时间节点，结束节点为签订合同的时间节点。一旦节拍开始，便不会被打断，直至节拍结束。当招标书处在一个节拍内正在被评估时，新来招标书不会被立刻评估，而是被放入招标书任务集，直至节拍结束才会被全部取出并在下一个新节拍中评估。其中，招标书任务集用于存储在一个节拍评估过程中收到的招标书。新节拍开始节点是上一节拍的结束节点。具体示例如图 4所示。

图中共有1个MA和4个TA，带有箭头的横向线段代表Agent间的通讯过程。竖线代表时间轴，其中字母A~H分别代表时间节点。MA₁在A节点收到来自TA₁的招标书代表一个新节拍的开始。MA₁接到招标书时，对其进行评估，并在C节点向TA₁发出投标书。TA₁在E节点做出决策，并与MA₁签订合同，此时节拍结束，节拍范围为A~E。在A~E节拍过程中，MA₁将B和D节点收到的招标书放入招标书任务集，并在该节拍结束后评估。因此，E节点又成为下一个节拍的开始节点，MA₁提取招标书任务集中全部任务并评估。针对多任务同时竞标情况，MA₁首先从自身角度评估，选择最有利于MA₁的任务发布投标书，并放弃其他任务。MA₁在F节点又收到来自TA₄的招标书，该招标书将被放入任务集暂不评估。在G节点，MA₁将投标书发送至各个TA。最终，MA₁在H节点收到竞标通知，并与发起者Agent签订合同。此时节拍结束，节拍范围为E~H。

上述流程按节拍依次进行，避免了因竞标的并发操作而导致出错，保证了竞标的有序性。利用节拍合同网协议，MA可以选取最优招标书投标实现自优化。

2.2 阈值策略

除了节拍外，改进合同网协议还引入了阈值策略以实现TA的优化。阈值又称临界值，是竞标决策中的重要参数之一。假设阈值MAX是TA能够接受投标书的最高报价。TA收到来自MA投标书后，提取标书中报价。若标书中报价高于阈值MAX，TA直接拒绝MA的报价以提高TA效率；反之，TA在竞标中选择报价最低的MA进行合作。阈值策略在改进合同网协议中的应用如图 5所示，TA设定阈值MAX以去除高报价投标，确保任务完成的成本。

在基于节拍的改进合同网协议中，节拍的引入成功地化解了投标并发而带来的矛盾并实现了MA的自优化，使MA在任务集中选择最佳TA进行合作；阈值的引入实现了TA的自优化，使得TA从自身利益出发，选择最佳的MA进行合作。

3 仿真实验 3.1 实验设置

本文以基于多Agent的作业车间AGV调度系统仿真实验为例，验证基于节拍的改进合同网协议在Agent协商过程中的可行性。实验中，机床和自动化立体仓库代表TA，AGV代表MA。TA和MA相互协商，共同完成AGV调度，最终生成甘特图。现假设系统中有一组生产任务，此任务中有6个工件，每个工件有多道工序需要加工，每道工序需要在相应的机床上加工一定的时间，工件的运输任务由2台AGV承担。实验布局如图 6所示，生产任务参数如表 1所示，AGV运输时间如表 2所示。其中J_i为工件编号，M_j为机床编号，L/U为自动化立体仓库。本实验需满足如下约束条件。

(1) 不考虑机床故障、AGV故障、碰撞、死锁等情况；

(2) 机床每次只能加工一个工件；

(3) AGV每次只能运送一个工件，且一开始停靠在L/U处。

实验测试的硬件环境为：CPU Intel Core ^TM2、2 GB内存、Windows 7操作系统。软件环境采用Java编译环境JDK1.7.0 ，集成开发环境为NetBeans 7.4，JADE4.3，数据库为MySQL Server 5.5。本次实验将在两种场景下进行。

场景1：无节拍合同网协议。

场景2：基于节拍的改进合同网协议。

3.2 结果分析

通过仿真实验，离线的生产任务计划调度甘特图如图 7所示，为AGV的调度提供了任务与机床的调度计划；场景1和场景2的AGV调度结果分别如图 8和图 9所示。图 9在基于节拍的改进合同网协议下，不仅完成了无逻辑错误的调度，而且完工时间由100缩短到85，大大缩短了完工时间。

在图 8和图 9中，每个任务的分配都是招标-投标-中标的竞标过程。机床对任务发起招标，AGV依据其工作状态、位置、运输任务等因素评估出竞标报价，机床选择最低报价完成竞标过程。在竞标过程中，阈值策略被用来优化竞标。例如，图 8(场景1) 中任务22为AGV2的第2个中标任务。在节拍合同网协议中引入阈值策略后，由于AGV2对于任务22竞标报价大于阈值，竞标未能成功。AGV2对于任务41的竞标报价不仅低于阈值而且低于AGV1，AGV2中标任务41，结果如图 9(场景2) 所示。

不同场景下设备利用率如图 10所示，场景2中的利用率明显全部高于场景1。AGV理论上完成一次运输任务的平均消耗时间为10.08。在基于节拍的改进合同网协议的实验中，2台AGV共执行了21个运输任务，其消耗时间频数分布如图 11所示。场景2下76.19%任务消耗时间在10以下，95.23%任务消耗时间在15以下。上述数据表明AGV在多个任务选择时，能够合理地优化AGV等待时间和任务选择。

对比完工时间、机床利用率、AGV利用率和运输任务消耗时间频数，基于节拍的改进合同网协议明显优于无节拍合同网协议。

4 结束语

针对传统合同网协议在基于Agent的制造系统中的弊端，本文提出了一种基于节拍的改进合同网协议。在这种简化的改进合同网协议中，通讯量和计算量被减少，节拍不仅规避了投标的并发操作导致的错误，而且利用并发操作优化了机器Agent (MA)；通过阈值策略，任务Agent (TA) 选择低报价MA进行优化，最终实现合同双方优化。最后，把该协议应用到基于多Agent的车间AGV调度实验中。结果表明：该协议能够很好解决Agent间合作冲突，起到良好的协商作用并完成任务。