基于多Agent的蚁群算法在车间动态调度中的应用研究
基于多 Agent的蚁群算法在车问
动态调度中的应用研究 *
陈文 王 时龙 黄 河
1．重庆 大学 机械 工程学院 ，重庆 400044；2．重庆大学 软件学院，重庆 400044
摘要 ：文章提 出了基于多代理的车间动态调度结构模型，并分析 了此结构模型的工作原理。对应用蚁群算法如何实现车间
的具体调度进行了分析与实现，从而为制造系统 中的动态调度提供 了一种新方法。通过仿真，验证了此方法在车间动态调
度问题的求解中具有很好的可行性与有效性。
关键词 ：车间动 态调度 ；多代理 ；蚁群算 法；全局优化
中图分类号 ：F273 文献标识码 ：A 文章编 号 ：1001—2265(2004}06—0056—03
Research on ant colony algorithm for multi— agent based workshop dynamic scheduling
CHEN Wen W ANG Shilong HUANG He
Abstract：A novel multi—agent—based workshop dynamic scheduling(WDS)model is presented and the principle of this model is
given．Then the realization of ant conoly algorithm for W DS and a new dynamic scheduling approach are introduced．Finally，the
feasibility and effectivity of this model and algorithm is comfirmed by simulation．
Key words：workshop dynamic scheduling；multi—agent；ant conoly algorithm；global optimization
1 前言
生产调度是制造系统中最关键环节之一，但是车间级生产
调度及优化已被证明为完全 NP复杂问题 ，传统的制造系统多
数是采用集 中式决策 的方 法 ，多年来 广大研 究者 研究 出 了大量
简化算法 ，如离散寻优算法 、启发式算法等，但都只能解决局部
问题，很难实现在全局控制下的最优化 ，而且某些规则算法只适
合于一种场合，很难保证其解的有效性_l J。文献[1]中提出了运
用生物遗传算法来实现生产调度算法。文献[2]中提 出了基于
现场 总线的多 Agent车间 动态调 度算 法 。针对上 述 问题 ，本 文
提 出了一种基于多 Agent的车间动 态调 度模 型 ，并运 用蚁 群算
法来构造车间动态调度算法。运用多 Agent结构可以实现全局
协调作业，从而使生产系统在满足一定约束条件下 ，实现资源的
合理 配置和有效利用 ，达 到成 本最低 的 目标 。通 过这种 方法不
仅可以有效解决 自动化生产系统中车间调度的具体寻优问题而
且可以实现全局动态调度及协同控制的目标。
2 基于 多 Agent的车间动态调度结构模型
实际的车间生产系统是一个动态生产环境，生产计划、加工
设备、调度目标等任何因素的变化都会引起生产调度的变化。
为了实现车间的协调运作 ，同时实现全局优化目标，从而更好地
完成车间调度任务，实现资源的合理配置，本文提出了基于多代
理的车间动态调度系统 ，并运用蚁群算法来构造车间的动态调
度算法。Agent的原意是“代理”，在文献[3]中，Lap．e将 Agent
定义为一种具有问题推理求解机制以及可以自主发挥作用的计
算实体。之所以要运用到多 Agent结构 ，是 由于多 Agent系统
是由多个 Agent组成的可以协调作业的网络与计算系统 ，系统
中的各个代理各 自有 自己不同的求解问题与求解方法，但是 A．
gent间可 以通过 约定 好 的统一通 信协 议进 行车 间 的动 态调 度 ，
以投标 、谈判等方式进行决策。采用多 Agent结构可以使系统
基金项 目：重庆市科技项 目(7210，7362)及回国人员启动基金资助
图 1 基于多 Agent的车间动态调度 系统结 构
不会因为系统的某个部分 出错而导致整个系统的崩溃，有利于
提高系统的稳定性，同时实现制造系统的分布式决策 ，使系统具
有很强的鲁棒性与可扩展性。
本文构造的体系结构模型如图 1所示，其基本的工作原理
如下 ：
(1)首先数据采集 代理起 到 实时 生产 监控 的作 用 ．采集 生
产过程中的现场数据，如机床状态、路线的运行情况等 ，并结合
生产计划，为评估与决策代理提供原始数据。
(2)集成代理将各个数据采集代理送出的各种数据进行有
序组合 ，并将其集成 ，通过代理中的预处理算法将各个数据转换
为系统可 以识别 的统一格 式 ，从而有 利 于提高 整个 系统 的计算
性能 。
(3)总控代理不仅要向决策代理提供各种数据以及可供选
56 组合机床与自动化加工技术
维普资讯 http://www.cqvip.com
用的各种评估与分析算法 ，如相关性算法、平均值算法等 ，而且
总控代理要负责对整个系统的运行进行实时监控。若数据出现
错误 ，可以发出要求数据采集代理改变其提供数据频率的指令，
从 而实现在监控 基础上 的全局优 化 目标 。
(4)评估与决策代理是整个 系统的核一fi,，是调度任务完成
的主要执行者，可以要求总控代理提供实时数据 ，并选用合适的
算法进行车间的具体资源配置。由于评估与决策代理起到车间
调度代理的作用 ，它可以通过谈判 、投标等方式进行决策，并将
决策结果及时地发送给合适的加工单元代理。当调度期间出现
问题 (如某条路线运行 的等待时 间过 长或出现返工现象 等 )可 以
向总控代理发出处理命令 ，使系统暂时停止调度与加工 ，并及时
从共享知识库中调出错误信息 ，供决策者分析与解决。当要处
理的加工任务过大时，可将任务进行分解，并由多个评估与决策
代理进行分布式决策，最后经过预处理算法将处理信息转化为
统一的决策结果并发布给合适的加工单元代理。随着决策事件
的不断增多，共享知识库中的数据信息将朝着更加有利于车间
动态 调度的方 向发展 。
(5)加工单元代理可以不问断地向评估与决策代理发出接
收加工任务 的指 令 。若某 机床 在加工 过程 中 出现问题 ，则设 备
监控代理会将所有经过此机床的加工路线定为不可用 ，并及时
将信息发布给决策代理，使决策代理重新对车间内的实时状态
进行评估与决策，从而从剩余 的可行加工路径中选择出一条可
行路径来完成加工任务，当机床的故障被排除了，则所有经过此
机床的加工路线又会重新被定义为可用。
3 蚁群算法
人们通 过研究发现 ：蚂蚁虽然 视觉 功能较差 ，但 具有寻找 蚁
穴和食物源之间最短(最优)路径的能力。根据蚂蚁的觅食原
理 ．发现了一种可以应用于各种优化组合问题求解的群体智能
算法 ，这就是蚁群算法 (Ant Colony Algorithm)，它是 由 Dorigo等
人[ ]首先提 出的 。蚂蚁之所 以具 有如此 强 的能力 ，是 由于 它在
寻找食物的过程中会释放出信息激素(pheromone)，这种信息激
素会随后续蚂蚁 的经过 而增加 ，但 也会 随着时 间 的推移 而不断
减少 ，从而依靠这种信息激素形成一种自组织行为 ，使得从最初
的随机加工路径搜索 ，最终达到蚁群整体寻优最佳化。当蚂蚁
在寻找食物的过程中存在着多条可行路线时，在相同条件下，蚂
蚁在较短路线上往返的时间较少 ，从而使较短路线上遗 留的信
息激素要比其它路线多，则后续的蚂蚁会沿着信息激素高的路
线前进。随着最短路径上的蚂蚁越来越多 ，使这条路径上的信
息激素也越来越高，从而越来越多的蚂蚁选择 了这条最短路
径 [ 。
设 t时刻在连接第 i， 两路径上留下的信息激素为 ， (t)，
第 m只蚂蚁从 i节点(本文中指的是机床)到 节点的概率：
m
当完成一次搜索 后时间更新 为 t+k，则 此时更新 的信息 素
的计算公式如下 ：
■(t+ )=dq(￡)+Al~j(t)
式 中：0<￡
挥发程度 ；△ (t)为蚂蚁在时间 t和 t+k之间引起路径 ／j上信
息素的增加值。
由于存在着许多可行加工路线 ，而且在一条路线上是由一
群蚂蚁在工作的，从而会有许多不同的 ， ．(t+k)值。通过比较
各个路径上的 ， (t+k)值 ，若某条路径上的 ， ．(t+k)值最大，
则在相同的约束条件下 ，可以判断出这条加工路径就是最短(最
优 )的。
4 蚁群算法在车 间动态调度系统中的应用
由于蚁群算法具有 自适 应 、分布式并行化 等特征 ，并 且不需
要进行大量的概率演算 以及建立复杂的数学模型，对于求解具
体的车间动态调度问题具有很好的可行性。
本文采用 如下方法实 现车 间 的动态调 度 ：首先通 过 蚂蚁 泛
滥[ j的方法，在整个车间网络中寻找到所有可行加工路线 ，并将
其作成工艺表。在每条工艺路线上放入一群蚂蚁 ，并将每只蚂
蚁看作 一个 Agent E ，当它经 过每条工艺 路线 时 ，要记 下各 条路
线上的各种信息，如各个区间的运行时间 t、设备状态以及所经
过的节点(机床)等。当蚂蚁沿原路返回到原先的节点时，蚂蚁
可以根据前进时所采集到的路线状态信息 ，作出增加 (或减少)
通过某段路线的概率值，如某路线过于拥挤时，则蚂蚁通过的时
延相应增加，从而使选择这条路线的概率降低 ，通过这种方法可
以更好地为后续的蚂蚁提供信息。本文通过正比关系将平均运
行 时间映射成成本 量 。通 过 比较 所有 可行 工艺路 线上 的成 本 ，
依据“成本越低，则该路线被选择的概率越高”的原则，选出最优
路线 。
当选出了最优路线后 ，第一个工件就可以进行加工。由于
最优路线上的机床此刻正处于加工阶段 ，若待加工工件再在这
条路径上进行加工，必然需要花费许多等待时间，而且会缩短这
条路径上机床的使用寿命，但是此刻其它可行路径却处于空闲
状态，从而出现了机床闲置的问题。因此此时可以再插入一群
蚂蚁进行搜索 ，搜索 出此 时的所有可行加工路径 ，并通 过蚁群算
法得出此刻的最优路径，通过上述重复搜索方法，使工件在满足
一 定的约束条件下，都可以在当前最优路径上进行加工。
5 仿真结果及分析
为了验证本文所提出的基于多 Agent的蚁群算法在车间动
态调度中应用的可行性与有效性，我们对车间调度系统进行了
仿真实验。我们考虑 8个都具有 4条(dl、d2、d3、d4)可供选
用的可行加工路线的车间，每个工件的加工由若干个工序完成，
每个工序由一个机床来完成，并且作业过程是不间断进行的，并
假设当加工过程中出现刀具使用矛盾时，处于最优路径上的机
床具有优先使用刀具的权利。将信息素的挥发度定为 0．2，移
动速度 =2．0cm／s，常量 P=10，仿真结果如表 1所示。
表 1 仿真结果汇总
车间 各生产线距离 各生产线加工的工件数
d1 d2 d3 d4 凡1 n2 n3 n4
1 15 16 30 25 38 37 29 32
2 20 16 23 26 51 54 49 46
3 10 8 14 30 51 53 47 37
4 25 17 13 28 38 44 47 36
5 22．4 14．8 19．5 16．2 26 31 28 29
6 8．4 5．7 18．4 6．9 59 65 49 62
7 12 21 20 15 51 44 44 49
8 40 21 28 12 22 29 26 34
从表 1中可以直观地看出：加工路线越短 ，它所加工的工件
数就越多，从而满足了实际的车间调度要求 ，而且可以看出最短
路径加工的工件数最多，但是其它加工路径上的机床也不会处
于空闲状态，不会使待加工工件都拥挤在最优(下转第 59页)
2004年 第 6 57
维普资讯 http://www.cqvip.com
图2创建变量框图
相互转换．适应工作的不同要求 ：
单击表格驱动设置对话框中的创建按
钮 ．选择正确的路径．并为这个文件 命名。
Exed自动打开该电子表格，其中仅包含规
格为“一般”的设计变量值。也就是刚才所
创建的设计变量。你可以为不同规格的气
缸命名．侧如 CLIR50—50B表示 50缸径
和 50行程的气缸 l然后相应的填人表 1中
的数据 ，如图4
双击每一种规格的图标，零件将 自动
按照对应的设计变量的值更新显示如图 5所示。
图 3 表格驱 动设置 对话 框
3 结 论
实践表明，利用 MDT中参敷设计法和表驱动技术 可使设
计者以零件的尺寸、几何形状和相互位置等关系来进行产 品造
型设计 ，进而刨建三维素材库，大大缩短了绘图时间
作者在进行三维汽车焊接夹具设计中在制作气缸蚊果图时
使用了 MDT参数化实体造型技术 在完成参数化种子零 件模
型的基础上，借助零件族数据库 ，可快速准确地生成系列中的任
何一个零件，与传统设计方法相比，减少了绘 图工作量，缩短了
设计周期
[参考文赫】
[I：邱宣怀 ．机械设计(第四版)．北京 ：高等教育出版社，1999
[2]TA1YO产品技术手册 +2001
图 4 气缸零件的驱动表
图 5 CLIR50—50B和 CLIR63—150B对应气缸
[3]李晗．Aulodesk Mechanical DeskTop 6．0零件造型实训教程
北京希望电子出版社，2002
—
4]赵景亮，王妍风，郑铁．中文 MDT6．0基础与实例教程
北京：希望电子出版社 ．2002
[5]二代龙震工作室编著．AutoCAD&MDT立体三维设计实
作 ．北京：电于工业出版社 ，2002
收 稿 日期 ：2003—10—27
作者筒介：张杨(1979一)．男 ．天津工业大学机械工程及 自
动化学院硕士研究生
(编辑 江复)
(上接第57页)路径上，这样不仅可以有效地提高机床的使用寿
命，而且可以在最大程度上减少等待时间 ．实现在全局控制下的
最优化及 倜控制的目标。当无法在规定的交货时间内完成加
工任务时．系统会将任务作外包处理。
6 结束语
本文采用了多 Agonl结构 ，从 而使车间动态调度系统在调
度决策时能了解全局情况，避免 了单个 Agent对全局不了解 的
情况，使系统不致于陷^局部优化的缺陷，同时采用多 Agent结
构可 使系统不会因某个部分出错而导致整个系统的崩溃．从
而有利于提高系统的稳定 I生，同时可以有效地解决调度系统在
有限时间、有限资源情况下 的资源分配与任务罚度 而且应用
到蚁群算法来构造车间动态调度算法，由于蚁群算法不需要进
行大量的概率计算与建立复杂的数学模型，因此可以明显地提
高整个调度系统的计算性 能，利用蚁群算法为车间动态调度问
题提供了一种新的解决思路：通过仿真，验证了本文所提 出的
方法具有很好的可行性与有蚊性 。
[参考 文献 ]
[1]李郝椿 基于生物遗传算法的 FMS生产调度算法．机械工
程学报 ，20OO(9)：91—93
问题的研究 中国机械工程，20o0(7)；757—759
I 3 Lane D M ．Mefadzean A G．Distributed Problem Solying And
Real— Time Mechanisms in Rohot A hilecture．Engineering
Applieation Afitifieal lnte~gonce．1994，7【2)：105～1 17
[4J Doffgo M，Maniezzo V．Co]ova／A The ant sys4~m optlmiza-
lion by conoly of cooperating agents J J IEEE Tram．On
Systems．M811．and Cvbernet 1996．Bf26)：29—41
．
5]Brendan Jennings，Rob Brennan，Rune Gust~t',．sson el丑1．FI—
PA —com ant agents for real— time eontrol of intellige nt net-
work traffic Computer Network，1999．31(19)：20l7～2036
[6]林国辉，马正新等．基于蚂蚁算法的拥塞规避路由算法．清
华大学学报 ，2003(1)：1～4
【7 J Gianni Di Carm，Mareo D0d ．Mobile Agents for Adaptive
Routing． Prcc 31st Annual Hawaii International Cortferenee
On System So ienee：74～ 83
收稿日期 ：2003—10—16
作者简介 ：陈文(1981一)，男 ，福 建福清人，重庆大学机械
工程学院硕士研究生。
王时龙(1966一)，男，重庆大学教授 ，博士研究生导师。
(编辑 江复)
维普资讯 http://www.cqvip.com
基于多Agent的蚁群算法在车间动态调度中的应用研究.pdf
