基于信息素的协调机制与任务分配研究

王 雷 唐敦兵 袁伟东

1.南京航空航天大学，南京，210016 2.中国船舶重工集团公司第七0二研究所，无锡，214082

0 引言

随着以全球化、动态化和用户驱动为显著特征的市场竞争的加剧，制造业面临着越来越大的挑战。因此，现代制造系统的运行环境越来越充满了不确定性，系统的生产任务经常是动态变化的，如不可预知任务的到达、增加和减少等。这些诸多的不确定因素，要求制造系统有一个良好的协调机制来快速地响应这些不确定性，从而在满足制造环境约束（如加工先后次序、交货期、设备负荷率等）的前提下，使得任务与资源得到合理的匹配。目前，任务分配的求解方法主要有基于拉格朗日松弛法的协调[1]、基于合同网（contract net protocol，CNP）的协调以及改进的CNP协调[2－5]、基于Petri网的协调[6－7]和基于生物行为的协调[8－9]等。

然而，拉格朗日松弛法也是一种给予最优化方法的启发式算法，因为它不提供保证最优化的解。因此，这种方法并没有得到广泛的应用。基于PN协调方法具有较强的建模能力，但存在建模复杂、效率低等问题。CNP模型可以成功地解决一个任务Agent在多个资源Agent之间的分配问题。基于CNP的协作是一种显式的协调机制，即参与合作的一方明确地向另一方提出合作要求。但随着任务的复杂，系统环境的动态变化，传统的CNP模型越来越显示其突出的问题，影响了协商过程中任务完成的效率，因此，出现了改进的CNP协调机制。对基于CNP协调机制的改进主要是引进他信度和阈值等概念，以达到提高CNP合作效率的目的[2－3]。尽管如此，基于 CNP协调机制仍然存在以下问题，如信息通信量大[9－10]、资源消耗大、计算量大、计算效率低、不确定性突出、决策效率低、容易出现死锁现象等。

基于生物行为的协调方法源自对群居动物行为的观察。蚂蚁的探路方法就是一个很好的实例[11]。蚂蚁在寻找从蚁穴到食物源的路径时，不能从外界环境中得到任何关于路径的全局信息。蚂蚁会在它经过的路径上留下一定量的化学物质（信息素），并可以感知到路径上的信息素。通过这种化学物质，使得蚁群具有强大的寻优能力。与基于CNP的谈判方法不同，基于行为的方法是一种隐式合作，各蚂蚁之间没有明确直接的协调与合作行为，各个蚂蚁甚至可以不知道其他蚂蚁的存在。各个蚂蚁只是依据系统的“暗示”来采取行动[12]。各个蚂蚁依据其内建的合作机制采取行动，每个蚂蚁的行动都在一定程度上对群体的利益做出贡献。蚁群优化算法（ant colony optimization，ACO）就是依照蚂蚁觅食原理，设计出来的一种群智能算法，该算法在任务分配问题[13]、作业调度[14]等组合优化问题上得到了广泛的研究与应用，但关于蚁群算法的研究几乎都是从优化的角度去考虑的。

本文针对CNP协调机制在制造系统任务分配过程中存在的问题，基于生物行为的协调方法，设计了基于信息素的隐式协调方法，从控制的角度研究生产任务分配的协调控制问题，并通过具体实例验证了该方法的有效性和可行性，为任务分配的协调控制提供一种可行的解决方案。

1 制造系统任务分配模型

制造系统的任务一般能够在许多单元内部完成加工，问题是如何在满足单元负荷率的前提下，保证总的加工成本最小。基于此，本文首先建立如下以成本为目标的数学模型和约束条件：

式中，j为任务，j＝1，2，…，n；i为制造单元，i＝1，2，…，m；k为单元i的设备；tjik为任务j在单元i中的设备k上加工所需要的加工时间；dj为任务j的交货期；cji为任务j在单元i中加工的完成时间；cjik为任务j在单元i中的设备k上加工的完成时间，cjik＝cji（k－1）＋tjik；αji为任务j在单元i中的单位加工成本；βji为任务j在单元i中的单位库存成本；γji为任务j在单元i中的单位延迟惩罚成本；Qj为任务j的数量；Tji为任务j在单元i中完成的最大迟误时间，Tji＝max（0，cji－dj）；Eji为任务j在单元i中完成的最大提前交货时间，Eji＝max（0，dj－cji）；f为任务j在单元i中的总成本；f1为任务j在单元i中的加工成本；f2为任务j在单元i中的库存成本；f3为任务j在单元i中的延迟惩罚成本；f4为单元i的负荷率。

式（1）表示总成本，由加工成本（式（2））、库存成本（式（3））和延迟惩罚成本（式（4））三部分组成。式（5）表明单元i的最大负荷率要小于1。

2 基于信息素的协调方法设计

在本文所设计的协调方法中，信息素仅仅被用作一种通信介质。在基于Multi－Agent的车间层控制系统中，存在着多种Agent，如任务Agent、单元Agent和资源Agent等。为了更好地传播信息素信息，不同的Agent（任务Agent、单元Agent和资源Agent）需要释放相应的蚂蚁Agent。这些蚂蚁Agent携带着信息素信息在车间系统中游荡，以便有效地协调任务的加工。

在这个基于信息素的协调方法中，不同的蚂蚁Agent有不同的游动方向，它们能够携带信息素信息向下游或向上游游动。任务蚂蚁Agent游动方向是从上游到下游，然而，单元蚂蚁Agent游动方向是从下游到上游。它们分别释放信息素信息到公共的环境中（图1），这些信息以一定的时间周期被更新和保存。通过这种方式，这些信息素信息就可以被其他蚂蚁Agent所感知并利用。

图1 蚂蚁Agent协调过程

由车间层向单元层传递信息素的信息用三元组来表示，即

式中，task＿id为任务的编号信息；quantity为任务数量信息；I为加工信息，包括加工工序、每一道工序需要的设备、交货期等信息。

相反，由单元层向车间层传递的信息素信息也用三元组来表示，即

式中，cell＿id为单元的编号信息；c为成本信息；l为单元的负荷率信息。

当任务到达到车间层，首先由任务Agent释放一个任务蚂蚁Agent，该任务蚂蚁Agent携带着信息素信息ρ（task＿id，quantity，i）向下游移动，然后该任务蚂蚁Agent根据以下步骤选择最具有吸引力的单元来加工该生产任务：

（1）上游的任务蚂蚁Agent释放信息素信息ρ（task＿id，quantity，i）到公共环境中。

（2）下游的任务蚂蚁Agent感知该信息素信息ρ（task＿id，quantity，i）。

（3）如果下游的单元蚂蚁Agent有能力接受该任务，那么单元蚂蚁Agent将ρ（task＿id，quantity，i）信息经过计算转化成自己的信息素信息ρ（cell＿id，c，l），然后该单元蚂蚁 Agent向上游游动并将此信息释放到公共环境中。

（4）当任务蚂蚁Agent感知一个较为合适的加工单元的信息素信息，然后将该信息进行保存，在保存之前首先检查该信息的有效性。

If（任务蚂蚁Agent没有该单元的信息）Then

｛保存该单元的信息素信息ρ（cell＿id，c，l）；｝

Else

｛任务蚂蚁Agent对该单元的信息素信息进行有效性检查：

｛If（l＜1）Then

｛选择该单元来加工该任务，并且更新该单元的信息素信息ρ（cell＿id，c，l）。｝

If（l＞1）Then

｛选择满足负荷率条件下的其他具有较小的生产成本的加工单元来加工该任务，并且保存该单元的信息素信息ρ（cell＿id，c，l）。｝

｝

｝

（5）重复步骤（1）～步骤（4）。

（6）结束信息素的释放，直到所有的任务都选择完合适的单元加工为止。

具体的实现流程见图2。

图2 基于信息素的隐式协调流程

3 基于信息素的协调机制效用分析

首先，基于信息素的隐式协调机制所需要的信息通信量小。我们可以通过一个简单的实例来印证这一优越性。假设某一时刻有n个任务需要加工，制造系统中有m个制造资源都有能力完成这n个任务。假设应用合同网的协调机制的话，每一个任务都要经历“标书信息发布→投标→中标通知→签约”这四个阶段，需要（2m＋2）次通信，因此需要的总的通信量为（2nm＋2n）次。但是，如果利用基于信息素的协调方式，完成这些任务的调度和加工需要的总信息量为n（m＋2）次。随着系统的复杂程度越来越高，基于信息素的隐式协调机制在通信量上的优势将会更加明显。

其次，基于信息素的隐式协调机制在工作过程中通过蚂蚁传播信息素信息，各蚂蚁的行动策略都是“利他”原则，因此不会出现冲突和死锁情况，而且都能够得到最优值或近优值。而在基于CNP等的协调过程中，所有制造资源都设法使各自获得最大的利益而采取不同的行动方式。尤其是规模比较复杂时，尽管经过多次协商，系统也最终达不到一致的结果。因此，合同网对系统性能的优化并没有保障。

再次，基于信息素的隐式协调机制中的各蚂蚁只需要依据环境作为通信中介，加上几条简单的行为规则和简单的通信就能实现较好的协调。各蚂蚁的行动策略都是“利他”原则，因此，基于信息素的隐式协调机制具有更好的易实现性。

最后，在基于信息素的隐式协调机制中，如果有资源出现故障，该资源只需要通过释放资源蚂蚁，然后该资源蚂蚁将故障的信息素信息释放到公共环境中，就不会有任务选择该资源。当有资源新加入制造系统时，相应的资源蚂蚁只需要到公共环境中感知由任务蚂蚁释放的信息素信息，如果有能力完成任务的话，只需要将相应的任务信息素信息经过计算转化成自己的信息素信息，然后释放到公共环境中，那么将会有任务蚂蚁选择该资源进行加工。而在基于合同网的协调机制中，如果在加工过程中有资源出现故障，然而这个时候所有任务的分配在工件到达时都已经完成，因此，前道工序任务的重新分配将直接导致后续任务的分配无效而必须重新分配。在这种情况下，任务的交货期等约束常常会被推迟而得不到保证，任务的完工时间、生产成本等指标将受到很大的影响。因此，基于信息素的隐式协调机制具有较强的鲁棒性。

4 实例分析

某一生产车间由3个智能制造单元组成，现有4个任务需要加工，此4个任务均可在3个单元内完成。单元1由设备1～设备4组成，单元2由设备5～设备8组成，单元3由设备9～设备12组成。任务的加工数量以及加工工艺信息见表1。库存成本信息、延迟惩罚信息以及交货期见表2。

表1 任务工艺信息表

表2 库存成本等信息

现采用前面设计的基于信息素的协调方法对第一个订单A001进行协调，具体的实现步骤如前文所述。下面以第一个订单A001为例详细说明各个单元的信息素信息的由来。

图3、图4和图5分别为订单A001在三个单元中的调度Gantt图。根据图3、式（2）、式（3）和式（4）求得订单A001在单元1中的加工成本f1、库存成本f2和延迟惩罚成本f3分别为f1＝6×（18×25＋12×20＋15×30）＝6840（元）、f2＝1×（210－135）＝75（元）、f3＝2×0＝0（元）。所以订单A001在单元1中的总成本f＝f1＋f2＋f3＝6915（元）。又根据式（4）求得单元1的负荷率为f4＝max｛18×6，12×6，15×6｝／210＝0.51。因此，单元1的信息素信息可以表示为ρ（cell＿1，6915，0.51）。

图3 订单A001在单元1中的调度Gantt图

图4 订单A001在单元2中的调度Gantt图

图5 订单A001在单元3中的调度Gantt图

同理，单元2和单元3的信息素信息分别可以表示为ρ（cell＿2，5063，0.65）和ρ（cell＿3，6545，0.43）。

因此，通过同样的方法，每一个任务Agent都选择合适的单元来完成其加工，协调结果见表3。从表3中可以看出，对任务A001Agent，由于cell＿2 Agent具有最小的加工成本，而且负荷率小于1，所以选择该单元来承担该任务。对任务A002 Agent，尽管cell＿2Agent具有最小的加工成本，但是其负荷率大于1，所以选择cell＿3Agent来承担该任务。同样任务A003Agent和任务A004Agent分别选择cell＿2Agent和cell＿3Agent来完成。因此，通过这种隐式的协调方法，各个蚂蚁Agent的行为都是“利他”的，不存在反复协商的过程，可以大大减小系统通信量大，避免死锁现象等。

表3 协调结果

5 结语

本文对基于信息素的隐式协调方法在制造系统任务分配中的应用进行了研究。建立了制造系统任务分配的数学模型。针对传统的CNP协调机制在任务分配过程中存在的不足，借鉴基于生物行为的协调思想，设计了基于信息素的隐式协调方法，给出了具体的实现过程，并分析了其优越性。具体的案例验证了该方法的有效性和可行性。下一步的研究方向是提高对制造系统面临频繁的动态干扰的处理能力。

[1]Tanaka S，Araki M.A Branch－and－bound Algorithm with Lagrangian Relaxation to Minimize Total Tardiness on Identical Parallel Machines[J].International Journal of Production Economics，2008，113（1）：446-458.

[2]王玉善，叶东海.多Agent系统中合同网协议的一种改进方案[J].上海师范大学学报（自然科学版），2005，34（4）：22－27.

[3]宋海刚，陈学广.FIPA合同网协议的一种改进方案[J].华中科技大学学报（自然科学版），2004，32（7）：31－33.

[4]Aknine S，Pinson S，Shakun M F.An Extended Multi－agent Negotiation Protocol[J].Autonomous Agents and Multi－agent Systems，2004，8（1）：1387－2532.

[5]Vojdani N.Distributed Manufacturing Control Using Fuzzy Contract Net[C]／／Proceedings of IEEE International Conference on Fuzzy Systems，New Orleans，1996：1655－1659.

[6]Hsieh F S.Developing Cooperation Mechanism for Multi－agent Systems with Petri Nets[J].Engineering Applications of Artificial Intelligence，2009，22（4／5）：616－627.

[7]潘全科，左凤朝，朱剑英.面向绿色制造模式调度的Petri网模型及优化算法[J].机械工程学报，2006，42（9）：48－53.

[8]Paulo L，Francisco R.ADACOR：A Holonic Architecture for Agile and Adaptive Manufacturing Control[J].Computers in Industry，2006，57（2）：121－130.

[9]Gao Q L，Luo X，Yang S Z.Stigmergic Cooperation Mechanism for Shop Floor Control System[J].International Journal of Advanced Manufacturing Technology，2005，25（7／8）：743－753.

[10]Xiang W，LeeH P.Ant Colony Intelligence in Multi－agent Dynamic Manufacturing Scheduling[J].Engineering Applications of Artificial Intelligence，2008，21（1）：73－85.

[11]Camazine S，Deneubourg J L，Franks N R，et al.Self－organization in Biological systems[M].Princeton：Princeton University press，2001.

[12]郜庆路，罗欣，杨叔子.分布式制造系统的控制协调及其方法分析[J].信息与控制，2003，32（4）：295－299.

[13]王灵霞，张远平，吴佩莉.蚁群算法求解分布式系统任务分配问题[J].计算机工程与设计，2008，29（6）：1472－1474.

[14]李言，刘永，李淑娟，等.面向多订单的JSP建模及其蚁群算法实现[J].中国机械工程，2009，20（18）：2198－2202.