基于多代理和规则调度的敏捷调度系统研究

作者：沈阳自动化所 王艳红 尹朝万 张宇

欢迎访问e展厅 展厅 8 CAD硬件/先进制造技术展厅 图形工作站, 绘图仪/大幅面打印机, 3D控制器/3D鼠标, ... 摘要：研究了在敏捷制造环境下制造车间生产过程的动态调度问题。针对敏捷化调度的特殊要求，提出了综合运用多代理机制与规则调度实现敏捷化制造车间生产过程动态调度的方法，建立了基于多代理生产组织和运行模式的生产过程动态调度系统框 架结构，研究了在多代理结构的基础上实现规则调度的方法，创建了适应实际生产环境的代理的模型结构，并以一类敏捷加工车间动态调度的仿真研究说明所提出方法的思路和可行性。 关键词：多代理；规则调度；动态调度；敏捷制造 0 引言 敏捷制造作为21世纪企业全新概念的先进制造模式，综合了并行工程、精良制造等多 种先进 制造模式的机理，以最低成本制造出顾客满意的个性化产品[1]。生产 调度主要 根据生产系统现状与生产目标，在满足一定约束的条件下，实现机器、材料、人力等 共享 资源的合理配置和有效利用，从而达到生产 成本最低的目的[2]。由于敏捷制 造车间的生产具有多品种、小批量、制造周期 短、质量要求高的特点，致使不确定事件（如加工任务的 突然加入或取消、工件到达的随 机性、操作延时、机器故障等）出现的频率明显高于传统的 制造环境。当生产任务变更及 突发事件出现 时，应结合现场的反馈信息，修改原定的作业计划，对系统资源进行动态重组，使敏捷制造 能够持续、有序、高效地运行。由于敏捷制造的特殊要求，生产调度更多的表现为动态调 度 问题。 动态调度常用方法有规则调度方法、运筹学方法、基于人工智能合作求解方法、仿真 方法等 [3]。规则调度方法是指在系统运行时，根据一定的规则和 策略决定下一步操作的方法。其优点是不必进行大量的计算，避开了“组合爆 炸问题 ”， 只要选择了合适的规则便可产生相应的调度策略，方便易行。缺点是灵活性差，难 以适应不确定变化。因而，单纯应用规则调度方法难以有效解决敏捷制造车间的动态调度问 题。 近年来，代理(Agent)在并行工程 、分布式求解等许多领域得到越来越多的应用。 它的主要特征是自治性、社交性、主动性和反 应性[4]。多Agent系统具有拓扑 结构可以动态改变的强大优势，即系统中的Age nt可以动态增加或撤消，而不影响系统中其 它部件，系统无须重启动。 为适应敏捷制造系统对柔性和快速重组的要求，本文提出以分布式多代理系统（Multi -Agen t system）作为新的生产组织和运行模式，综合运用多代理机制与规则调度的方法， 实现敏 捷化制造车间生产过程的动态调度。 1 多代理调度系统框架模型 多Agent系统由管理Agent、生产 Agent群和工件Agent群等组成一个具有协调、协商机 制的分布式系统。系统各主要Agent的 定义如下。 1.1 管理Agent(Manage Agent)——一个虚拟的车间调度员 管理Agent的功能主要包括任务规划、管理、协调和监控其它Agent， 以及自身规则库 的更新和维护等。 1.2 生产Agent(Manufacturing Agent)——车间中生产设备的代理 敏捷制造车间中所有加工、运输、装配、仓库等主要用于生产的设备和装置，均可定 义 为Agent，组成生产Agent群。 (1)加工Agent(Machine Agent)——车间中加工装置的代理，是生产Agent的一 个子集 。每个加工Agent通过设备接口与一个独立的加工单元连接。加工单元由一个或 多个加工中心或加工机床组成，具有加工功能。它可定义为一个三元组： M = < id，σ，α > 式中：Mid——加工Agent的唯一标识；σ——Agent的属性、状态、所具有的 信息特征；α——作用于该Agent的一组操作，描述其具有的行为。 (2)运输Agent(Conveyance Agent)——车间中运输装置的代理，是生产Agent 的一个 子集。每个运输Agent与一个独立的运输机、自动导引车（AGV）或移动运输机器人等 连接。运输Agent可定义为一个三元组： C = < id，τ，β > 式中：Cid——运输Agent的唯一标识；τ——运输Agent的状态、所具有的信息 特征；β——作用于该Agent的一组操作，描述其具有的行为。 同样，也可对制造车间中的装配装置、元件仓库或成品仓库等主要设备进行类似的定 义 。 工件是其它Agent的加工对象，在加工过程中，其状态不断变化，直接反 映和影响其它Agent的操作，故也定义为一个Agent组件。 1.3 工件Agent（Part Agent）——车间中被加工工件的 代理。可 定义为一个三元组 P= id，ω，δ 式中：Pid——工件Agent的唯一标识；ω——工件Agent的状态、具 有的信息 特征；δ——该Agent所连接的工件具有的任务信息，由管理Agent动态赋予 或取消。 多Agent生产调度系统框架结构如图1所示。多Agent在因特网或企业内部网环境支持下 工作，系统通讯与集成采用TCP/IP等标准协议，保证Agent间的信息交互。由于在不同情况 下系统中工作的Agent的数量不定，Agent间的通讯可以选择黑板法进行。 2 代理的模型结构 Agent可分为智能型的认知Agent和非智能型的反应式Agent。上述系统中工件Agent的 主要作 用是动态标定自身状态，并激发其它生产Agent的进程，它本身不具有判断、推理能 力 。因此，将其设计成非智能型的反应式Agent。而管理Agent和生产Agent具有一定的推理能 力 ，能根据本身的状态、任务目标及环境特征等信息，在分布式规则库的支持下进行推理 、决策，故可将它设计成智能型的认知Agent。各Agent按照自主决策与彼此协商相 结合的 方式，制定和执行具体调度策略，以一种清晰有序的方式带动生产系统 运转。 管理Agent的结构如图2所示。它通过人机接口接受车间管理人员下达的生产任务后， 与生 产Agent协商、确定作业计划，完成对系统生产资源、设备的优化管理，并接收生产Ag ent的 反馈信息，实现对生产过程的监控。它还根据生产任务下达工件清单，确定工件类加工优先 级，并结合工况信息给工件Agent动态分配工件。Agent间通过通讯接口实现通讯。 各生产Agent的结构相似，只是各自规划模块的具体功能略有差别，如图3所示。生产Agent通过设备接口与具体设备的控制器相连，规划器按照所控制设备的复杂程度可以进一步分解成若 干个功能模块，且可并行工作。各生产Agent的所有调度规则库自行设计和维护，并封装在 Agent内，为实现分布式规则调度奠定了基础。 工件Agent的结构如图4所示。由于不同加工任务、不同生产阶段系统中工件的种类、 数量不同，故系统中工件Agent的数量也在动态变化。其最大数量由管理Agent根据经验设定，具体生产调度中允许空工件Agent存在。工件Agent的任务数据通过与管理Agent通 讯动态赋予，保存在数据库中，内容包括该工件的种类代码、序号代码、加工工序和加工优先级等。状态属性由加工Agent或运输Agent根据该Agent对应的工件的实际状况通过管理Agent动态赋予，并成为激发其它Agent调用、执行规则的条件。 这样，除管理Agent起着宏观上的全局调度、协调作用外，各生产Agent 在微观上起着局部 规划、调度作用。 3 多代理结构下的规则调度机制 规则调度策略应用于敏捷制造车间系统中。首先，需要构造一个充分的、能动态修正、更新的规则库。其次，能够掌握车间的实时信息，选用合适的调度规则。由于Ag ent具有自主决策的能力和相对独立性，可以敏捷地响应环境变化，因此，本文提出的多代 理结构下的规则调度机制可满足上述要求。 每个Agent根据自身的特点和任务，定义自己的规则库，并能动态构造、修改、更新 自己的调度规则。规则库封装在Agent内。管理Agent具有全局公用规则库的功能，主要用于 系统中Agent初始状态的设定、多Agent系统的统筹和协调等。生产Agent的规则库则根据自 身功能和特性构造，在运行过程中，按具体条件调用。当没有合适的规则匹配时，Agent 自动启动实时调度模块，并将可行的调度策略作为新的规则更新规则库。 具体规则库的建 立和维护，可采取常 规的方法（如IF…THEN…形式）描述和建立调度规则。 系统运行时，每个Agent按照各自的规则并行工作，当需要增加或取消某些生产Agent时，Agent间交互的对象可能发生变化，但由于规则库封装在Agent内部，会随着Agent 的重组而动态重组，各规则库不必进行修改，系统利用Agent的智能性和交互性，在 管理Ag ent的统筹下进行协调。生产Agent每完成一项工作，向管理Agent及其它Agent通报；管理Agent依据各Agent的状态了解系统的运行情况，使调度系统能很快地掌握车 间的实时信息，为具体规则的选用和实施创造良好条件。 Agent模式与规则调度策略结合，满足动态调度的并发和同步要求。规则为Agent选择合适的操作步骤，实现有序化调度；Agent结构支持规则的分布，便于规则库独立进行修改 、补充 ，弥补了规则调度不适应动态变化、规则库庞大难以构建、维护等不足。因而，大大降低了 动态调度的复杂性，提高了规则调度的有效性。 4 敏捷调度实例 4.1 问题描述 图5为五个加工单元的敏捷制造车间示意 图。系统中每个加工单元可以是一台数控机 床或加工中心，自动地对工件进行加工。假定各 加工单元根据生产任务及配套的需要，加 工一种或多种工件，但每一时刻加工一个工件 。加工单元带有一个机器人、一个原始件输入缓冲区和一个加工件输出缓冲区。机器人自动 为机床装卸工件和刀具，输入、输出缓冲区为机床存储原料和加工过的工件。整个系统由 共 用的物料运输系统连接。假定根据生产规模的大小选某一台AGV在系统中运输工件， 可以随 机访问每个加工单元，其运行路径通过路径规划得到，规划结果保存在数据库中 。由于每次运输工件的数量有限，这里假定工件在运输之前，已按照AGV的运载能力、不 同 加工单元的缓冲区大小、工件规格等分成包，每次运一包或几包。 系统中省略了工件的装夹、清洗等环节。动态调度策略忽略刀具 、机器人、托盘等对 象，只考虑工件流的调度问题，以验证研究方法的可行性和有效性。 实际生产车间的加工任务通常具有一定的周期性，但不同工件在不同工序的加工 时间不 同，系统中还会有一些不确定延时（如人工换刀、等待工件等）及突发事件， 造成工件流 动的计划性和随机性并存。加之系统中某些资源共享（例如，某一台AGV为 多个加工中心运输工件），容易出现死锁等冲突。故工件流的动态调度就是保证工件在 系 统中平稳流动，避免工件短缺或阻塞。 4.2 调度仿真策略和示例 仿真系统中，工件流动态调度对象主要包括系统内的机器、设备（如加工机床、AGV运 输小 车或物料传送装置），以及待加工或加工后的工件等。将图5所示系统构造成一个多Agent 调度系统，包括管理Agent、加工Agent、运输 Agent和工件Agent等。 4.2.1 系统正常运行时工件流调度仿真 管理Agent根据任务、规模和系统当前对所需A gent数量、具体任务进行动态调度。例 如，采用分派与招标结合机制进行任务分配，相关规 则为（部分）： 规则M11： IF接到新任务，THEN发出信息包，将初步选定方案请求相关生产Agent协商，要求回复 信 息包； 规则M12： IF在规定时间内信息到达，THEN转向规则M3，ELSE重发任务通告信息包； 规则M13： IF生产Agent同意该计划，THEN发出信息包公布任务分配决定，ELSE根据生产Agent的 建议 得到进一步作业计划，再发出信息包请求相关生产Agent认可，AND转向规则M12。 系统正常运行时，管理Agent对生产Agent进行管理和监控。相关规则为（部分）： 规则M21： IF接到新任务或故障报警，THEN进行在线重新调度，ELSE随时查看生产Agent和工件Ag en t状态。 规则M22： IF发现某工位工件短缺或阻塞，THEN调度相关Agent紧急处理。 系统工作时采用简单、易行的按优先级加工和运输工件。加工的优先级由管理Agent 根据各类工件的交货期、工时及配套要求等综合因素动态赋予；工件运输的优先级由AGV折 衷管理Agent的要求、现场状况、加工Agent的运输请求和AGV的状态、优化性能要求等因素 确定。 当待加工工件的任务和工序确定后，由管理Agent按顺序将其指定给一个工件Agent， 如 果该工件的所有工序加工结束，送到成品仓库，该工件Agent释放，留作其它待加工工 件使用。相应的规则表示为： IF工件Agent i 空闲 THEN向管理Agent请求分配一个待加工工件 当有新任务下达或改变时，AGV通常首先响应，并以加工单元的输入缓冲区（上料）、 输出缓冲区（下料）、仓库等为主要服务对象。任务规划模块按服务工位请求的优先级， 在 规则的指导下，作出操作控制的指导计划。服务工位请求的优先级按急叫（如输入缓冲区 空、输出缓冲区满等）先服务、先叫先服务等优先级调度 策略，在规则库的支持下实现调 度。当完成任务后，变成空闲又没有运输请求时，根据各缓冲区存储工件的多少、 运输路 径长短等综合因素，主动运送工件。由于AGV的随动性强，对整个系统物流是否顺畅 所起的作用较大。相关规则可以表示为（部分）： 规则C1： IF有运输请求，THEN执行规则C2，ELSE执行规则C3； 规则C2： IF某加工Agent的输出缓冲区已满或临近满，OR某加工Agent的输入缓冲区已空或临近 空，TH EN响应运输请求； ELSE IF加工Agent的输入缓冲区工件队列最短，OR输出缓冲区工件队列最长，THEN响 应运 输请求； ELSE IF某项运输请求费用最低，THEN响应运输请求； ELSE IF运输请求最早，THEN响应运输请求。 规则C3： IF某机床上工件具有最短剩余加工时间，THEN AGV主动为其服务； ELSE IF某加工Agent的输入缓冲区工件队列最短，OR输出缓冲区工件队列最长，THEN AGV 主动为其服务； ELSE IF工件对系统性能指标最有利，THEN优先得到服务。 加工单元Agent的缓冲区管理器对在输入缓冲区内排队的工件进行优先级动态排序，按 照工 件的加工优先级高低选择工件进行加工。优先级高的先加工，相同优先级的先到先加 工。相关规则： IF工件优先级最高，THEN进行加工 ELES IF工件最先到，THEN进行加工 ELSE发出缺原料信息 当某项加工完成时，加工单元Agent通过通讯接口向系统发出通报及运输请求，并相应 改变 相关工件Agent的状态属性。相关规则： IF一工件加工完成，THEN发出信息包：声明加工完成、请求将加工后工件运到下一工 序、 输入缓冲区请求添料、要求改变加工后的工件属性。 4.2.2 系统出现突发事件时的调度仿真 管理Agent对生产Agent进行重组，并进行任务、工序的及时调节。管理Agent对故障处 理的 规则为（部分）： 规则M31： IF接到某加工故障报警，THEN发出信息包，内容包括初步紧急处理方案请求相关生产A ge nt协商，要求回复信息包，并要求AGV停止向该加工单元运送工件，尽快运出该Agent缓 冲区 内的工件； 规则M32： IF在规定时间内信息到达，THEN转向规则M33，ELSE重发故障通告信息包； 规则33： IF生产Agent同意该计划，THEN发出信息包公布故障处理决定，ELSE根据生产Agent的 建议得 到进一步作业计划，再发出信息包请求相关生产Agent认可AND转向规则M32。 4.2.3 仿真示例 图5所示系统在某加工过程中，有四个加工单元工作，单元5空闲备用。 Agent在规则 的支持下正常工作，工件流平稳分布。突然加工单元1出现故障 ，并在短时间内不能恢复。 管理Agent获悉后，在工期要求紧的情况下，按规则M31、M32 、M33与生产Agent协商，决定增加加工Agent 5继续完成加工单元1的任务。管理Agent动态 修 改相关工件Agent的加工运输优先级，指导AGV调整运输计划。加工Agent 5得到工件后开始 工作，其它加工单元则继续正常工作。AGV陆续将滞留在加工单元1输入、 输出缓冲区的工件 运出后，系统基本恢复正常。 若事故发生后，系统在满足工期的前提下，根据现有加工Agent2和Agent3生产任务未 饱和，可替代Agent1工作等条件，决定将加工单元1未完成的任务 分给加工Agent2和加工Agent3。管理Agent动态修改生产Agent和工件Agent的任务参数，A G V在管理Agent指导下，综合系统现有状况和加工单元1缓冲区清运任务的紧迫程度，按相 应规则动态调节运输计划，使工件流继续保持平稳、顺畅。在整个过程中，Agent没有停止 工作，系统没有重启动，故障的影响降至最小。 5 结束语 由于采用多Agent结构与规则调度相结合的机制，使敏捷调度得以有效实施。多Agent 结构简化了调度规则，支持规则的分布、重用和重组；规则调度保证多Agent按照任务需要 协 调、有序工作。特别是当有新任务或出现突发事件时，系统拓扑结构变化，但各Agent原有 的规则库不用修改，整个系统也不用停止工作重启动。仿真结果证实了本文所提方法 的可行性和有效性。 参考文献： ［1］ 蒋新松，张申生.敏捷竞争的挑战与思考［J］.计算机集成制造系统—CIMS , 1996,2 (1):3-9. ［2］ Roadammer F A, White K P. A recent survey of production scheduling［A］ . IEEE Trans. on SMC［C］. 1998,18:841-851. ［3］ Suresh V,Chandhuri D. Dynamic scheduling: a survey of research［J］.Produ ction Economics,1993，(32)：53-63. ［4］ K Kouiss, et al. Using multi-agent architecture in FMS for dynamic sch edu ling［J］. Journal of Intelligent Manufacturing.1997,(8):45-47.(end)

文章内容仅供参考 (投稿) (如果您是本文作者，请点击此处) (4/19/2005)