基于多Agent的柔性作业车间动态调度方法研究*

杨博见，杜 丽，郭景仁

（1.电子科技大学，成都 611731；2.中国航空发动机集团有限公司四川燃气涡轮研究院高空模拟技术重点实验室，绵阳 621703）

调度是整个制造系统的核心环节[1]，其目的是满足一系列约束前提下对资源进行合理分配使作业过程中某些指标达到最优。随着制造企业生产力逐渐提升，传统集中控制的静态调度方式在动态多变的生产场景下显得格格不入。一方面，小批量、多品种、个性化生产模式逐渐兴起，工艺路径愈加灵活[2]，柔性作业车间逐步取代以往的流水车间，针对柔性生产的调度研究愈发迫切[3]；另一方面，制造过程本质上是动态的，诸如订单数量波动、设备故障、原料紧缺等计划外的扰动是不可避免的[4]，如何设计调度策略使外部扰动对系统的影响降到最低成为生产调度研究中的另一个热点问题[5]。

在生产组织方式从静态集中的层次结构向动态分布式网络结构转变的趋势下，制造系统呈现出动态、复杂、自治等新特点[6]。多Agent系统 （Multi-agent system，MAS）作为一种新兴智能计算技术，其自治性、拓展性、移动性的特点与当前分布式、动态化的生产环境高度契合[7]，被认为是实现智能制造系统最有前景的方法之一，受到国内外学者的广泛关注[8]。目前框架设计与建模和协商机制是MAS的两个主要研究方向。Wang等[9]采用基于物理的映射方式将车间内实体划分为机床、运输、产品、物料库4类Agent，搭建了一种结合工业互联网与云端监控的多层次智能工厂框架。梁慰乐[10]搭建了一种混合架构的多车间动态调度系统，基于功能的映射方式划分了管理、资源、工艺、算法和监控5类Agent对象，实现了生产任务与扰动事件的跨区域处理。魏鑫[11]针对多目标作业车间调度问题提出了一种基于简化CNP（Contract net protocol）的区间协同拍卖协同策略，有效解决了传统CNP下调度中通信量大、Agent间劣质竞标以及调度结果全局性较差等问题。Zhang等[12]建立了基于蚁群优化的Agent协商机制，将蚁群算法中信息素的特征融入智能体决策模型中，通过信息素积累和蒸发产生的差异信息素图来解决常规调度与重调度问题。曹乐[13]应用内嵌Q – Learning的CNP作为上下层协商机制，搭建了基于多Agent的信息物理融合生产系统，实现硬件间的异构集成与生产任务的合理分配。

本文结合柔性作业车间特点对MAS进行了改进，从实际柔性生产中的物理实体和逻辑功能映射出5类Agent并形成一种混合式组织结构，在此基础上根据典型柔性生产中的任务分解、机床选择、任务分配3个步骤对多Agent协商机制进行改进，最后设计试验对该调度方案的有效性进行了验证。

1 多Agent柔性作业车间动态调度系统组织架构

图1所示的柔性生产线一般包含加工中心、立体刀库、有轨制导小车 （Rail guided vehicle，RGV）或机械手、立体物料库、上下料站、控制系统等设备。完整的柔性制造生产调度应包含的流程与功能总体可概括为工单输入与处理、工单任务分解、柔性生产调度规划、异常调度、数据管理。

图1 柔性生产线设备组成及分布示意图Fig.1 Flexible production line equipment composition and distribution diagram

对应以上设备分布与流程特征，基于多Agent理论，从制造环境中映射出5种Agent，可划分为基于物理的任务池Agent（Task pool agent，TPA）、任务Agent（Task agent，TA）、机器Agent（Machine agent，MA），分别与车间中的立体物料库、加工工件、加工中心对应；以及基于功能的调度Agent（Scheduling agent，SA）和监控Agent（Real-time monitoring agent，RMA），其内部分别封装了规则调度方法和异常调度策略。TPA主要完成工单输入与处理、工单任务分解；TA、MA、SA 3者通过协商完成柔性生产调度规划；RMA负责完成异常调度；数据管理则由5个Agent共同完成。

本文设计的混合式组织结构的柔性制造动态调度系统基本架构如图2所示。常规调度时，系统内除监控Agent以外的所有Agent共同构成集中式的组织结构，其中TPA处于管理层，接收与释放上层系统的计划任务；TA与SA处于处理层，对释放的任务进行排程；MA处于执行层，负责执行上层产生的调度计划。当出现扰动事件使系统进入异常调度状态时，RMA将与除TPA以外的所有Agent共同构成分布式的组织结构，各Agent之间通过信息互通，只需对其自身做出局部调整即可完成对扰动事件的处理。该结构具有易拓展、高鲁棒性和低成本的优点。

图2 多Agent柔性作业车间动态调度系统组织结构Fig.2 Organization structure of dynamic scheduling system of multi-agent flexible job-shop

2 柔性作业车间动态调度策略

合同网协议 （Contract net protocol，CNP）在复杂环境下具有较好的灵活性和实用性，整体逻辑较为简单，能够对大规模任务进行分解执行。在基于传统CNP的多Agent调度方法中，通常采用具备任务性质和具备处理能力的两类Agent进行招投标交互，完成加工任务在加工设备之间的分配，最终得到调度计划。一个完整调度流程的协商过程如图3所示，整个过程中TA与m个MA之间至少经过4m次通信才能完成任务分配，当多个TA对自身任务进行释放时，系统内的信息流将会急剧增长；除此之外Agent的贪婪性驱使其只根据自身当前的状态做出决策，造成实际招投标过程缺乏一定的全局能力，并且协商过程中缺乏应急处理机制，出现异常时可能会导致调度系统出现锁死甚至故障。由此可知，该协商流程存在通信量大、单步优化以及动态性能较差等缺陷。

图3 基于传统CNP的调度协商流程Fig.3 Scheduling and negotiation process based on traditional CNP

本文从调度过程中任务分解、机床选择、任务分配3个步骤的运行机制入手，改进得到基于工序块的任务分解机制、基于加工精度的机床选择机制以及基于调度规则的动态时间窗调度方法，保证动态任务的合理分配，提升系统的动态性能以及对特定加工环境的适应力。

2.1 基于工序块的任务分解机制

近几年，以工序集中原则为基础的复合加工技术快速发展，车铣复合中心、五轴加工中心等复合加工机床应运而生。传统的柔性作业车间调度问题 （Flexible job-shop scheduling problem，FJSP）求解方法往往以工序离散的原则处理工艺路径中的工序，即系统在调度的过程中按照工件的工序顺序逐项释放、逐项加工。因此，在得到的调度结果中，同一工件的加工过程总是离散化的，其相邻的两道工序通常不在同一台机床上进行。这与当前复杂工件的实际加工方式是不符的，各工序加工准备时间的存在也会导致大量加工工件在多台设备间转移的用时不可忽视，如果调度计算得到的调度解与实际调度情况的偏差较大，调度解将会失去参考性。

本文基于工序集中处理原则提出一种基于工序块的任务分解机制。在分解工单时，将同一工件工艺路线中工艺类型相近、工序顺序相邻的工序组合成为1个工序块一次性释放，利用加工过程中必要的翻转装夹、在机检测等步骤自然地隔离不同的工序块，单个工序块内的所有工序将在同一台满足所有工序加工条件的机床上进行加工。以表1所示的工艺路线为例（其中翻转装夹、在机检测等准备步骤视作工序，但不会作为任务Agent释放），按工序块进行分解，工件会由原先的8道加工工序合并为3个工序块参与调度计算。

表1 示例工艺路线Table 1 Example process routes

采用基于工序块的任务分解机制主要有以下优点。

（1）任务分解方式与实际加工方式对应，考虑了工序的加工准备时间，提高了调度解的参考性与可执行性。以上述工艺路线为例，加工前的准备时间将由单工序的分解机制下的7段减小为2段，且并入加工时间期望。

（2）该机制与原先单工序处理机制的适应性相同，基于工序块的任务分解机制在本质上没有改变原先任务分解机制的主要流程，仅在任务总量上有所变化，原有的调度求解方法仍旧可用。（3）减轻了MAS系统内的通信负担，以m台设备加工上述工件为例，单工序的分解机制下，系统至少需经过8×（2m+ 2）次通信才能完成所有工序任务的释放，但在基于工序块的分解机制下，系统只需经过3×（2m+ 2）次通信。（4）可以更好地适应未来工序顺序柔性这一趋势。基于工序块的任务分解机制下工序顺序仅需要在工序块内部进行调整即可，并不会影响到调度计算，整体调度流程的柔性将得到提高。

2.2 基于加工精度的机床选择机制

加工质量是制造过程中重点关注的问题，在调度过程中应当采取适当的措施来保障复杂结构件的加工精度，提高首件加工合格率。目前复杂结构件的制造过程一般根据加工任务中工件的尺寸、加工类型提前选择合适的生产线，因此机床精度就成为唯一的机床选择决策指标。一般会对生产线进行周期性检测和评估其整体加工精度，并更新生产系统内对应信息以便于进行机床选择。

在传统的FJSP案例中，一般采用的是单工艺型或半全能型机床，但现阶段的柔性生产线已采用全能型的加工中心，以往基于加工能力的机床选择机制已不再适用。因此，根据当前柔性作业车间的设备情况，本文提出一种基于加工精度的机床选择机制。新机制下TA与MA之间协商的流程如图4所示，当TA将加工任务需求以招标请求的方式发送至MA时，MA将任务对应的工序块内需求的最高精度与自身精度进行比较，根据比较结果选择是否参与竞标。本文机床精度与TA内携带的加工任务规定的工件尺寸精度均采用IT公差等级进行描述。

图4 基于加工精度的机床选择机制下TA与MA的协商流程Fig.4 Negotiation process between TA and MA under machine tool selection mechanism based on machining accuracy

基于加工精度的机床选择机制在调度过程中能够保障工件的加工质量，并且MA会定期访问生产系统的机床精度数据库获取机床最近时段的精度，将获取到的数据存储至自身知识库，从而使调度系统能够对动态的环境做出良好的反应。

2.3 基于调度规则的动态时间窗调度方法

上层系统下达的工单任务经过分解和机床选择之后，还需按一定的方法对任务进行分配才能产生最终的调度解，任务分配的方法将直接决定调度解的优劣。传统CNP协商过程中的单步优化会导致劣质调度解的出现，为解决此问题，国内外学者在CNP的基础之上引入了时间窗的概念，同时在MAS中设置全局管理型的Agent，形成了一种基于周期调度的预反应式调度策略。但随之引入了时间窗长度的选取问题，选取过长会导致任务堆积，过短会退化为单步优化，尤其在时间窗长度固定时，其无法适应工件到达密度多变的小批量生产场景。

根据以上情况，本文提出一种动态时间窗的策略。其具体执行逻辑如图5所示，其中Z为表征产线状态的决策变量；min（eBiu）为开启时间窗的时刻下产线内所有机床的最早完工时刻；Tnow为开启时间窗的时刻；L为单个时间窗内参与调度的工序块数量上限，以避免待调度的工序块过多导致调度系统瞬时计算负担过大。Z与L的计算方法分别如式 （1）和 （2）所示。

图5 动态时间窗策略的具体执行逻辑Fig.5 Specific execution logic of dynamic time window strategy

式中，m为产线内机床的总数；mB为更新变量Z时产线内损坏机床的总数。

在整个动态时间窗运行的过程中，单个时间窗内等待调度的工序块数量会逐渐大于L，此时应采取一定的措施来选择符合条件的工序块参与调度计算，否则会使所有工件的等待时间及完工时间难以得到保证。调度规则具有较低时间复杂度，动态性能较好的特点，是解决实际生产中动态调度问题的一个有效方法。本文采用基于到达时刻的最先到达最先加工规则 （First come first service，FCFS）对工序块进行选取，以保证工件的等待时间以及完工时间。FCFS的具体执行逻辑如图6所示。

图6 FCFS的具体执行逻辑Fig.6 Specific execution logic of FCFS

2.4 柔性作业车间异常调度策略

任何制造过程都避免不了异常事件的发生，本文针对设备故障与急件插单两类扰动设计了异常调度策略，其异常处理流程如图7所示。

图7 设备故障与急件插单扰动下的异常处理流程Fig.7 Exception handling process under disturbance of equipment malfunction and urgent order

由于急件插单扰动下插单工件需要尽早完工，TPA将会以新的方式释放加工任务，在其知识库中设置一个用于表征插单状态的决策变量D，其具体描述见式（3）。单个时间窗内参与调度的工序块数量上限L也将变更为式 （4）的计算方式。

3 仿真试验与结果分析

本文在JDK 4.5.0（Java development kit）环境下借助Eclipse 4.14.0开发工具与JADE 4.5.0（Java agent development framework）搭建调度平台，调度平台的功能主界面如图8所示，该平台主要包含用户管理、任务管理、调度控制、生产监控、帮助5个模块。将主要借助调度控制和生产监控模块进行基于固定时间窗调度策略 （Scheduling strategy based on fixed time window，SSBFTW）与基于动态时间窗调度策略（Scheduling strategy based on dynamic time window，SSBDTW）的对比试验，以及SSBDTW处理扰动事件的有效性试验，仿真结果将由甘特图展示，甘特图显示界面如图9所示。

图8 调度平台功能主界面Fig.8 Main interface of scheduling platform

图9 调度平台甘特图显示界面Fig.9 Gantt chart interface of scheduling platform

3.1 试验环境设置

试验中模拟柔性生产线由4台全能型加工中心组成，加工能力如表2所示，其基础数据来源于文献[11]，可处理包括人工翻转装夹、在机检测在内的10种工艺类型。人工翻转装夹、在机检测的加工系数固定为1.0，其余工艺类型的加工系数由区间[0.7，1.3]内取随机数并精确到小数点后一位得到。

表2 机床加工能力信息[11]Table 2 Machine tool processing capacity information[11]

工单任务将以下述规则从如表3所示的5种工艺路线各不相同的示例工件中产生：在区间[1，4]取每种工件的个数βi（1≤i≤5），使每个工单均包含上述5种示例工件，工单内总工件数且工件的到达顺序随机。各示例工件的工艺路线原始数据主要来源于文献[14]～[16]。

表3 示例工件工艺路线[14–16]Table 3 Process routes for sample artifacts[14–16]

实际生产过程中，由于各工件的状态不完全相同，不同工序块的加工前准备时间可能不相同，当这些实际的准备时间与试验设定的准备时间产生偏差并累积，试验结果便会与实际结果产生差异。但由于在实际生产中，工件的加工前准备时间一般仅为数十秒，而加工总时长可达数百分钟，加工前准备时间的偏差对试验结果造成的影响较小，在此忽略不计。

3.2 动态时间窗与固定时间窗调度方法对比试验

本试验以最大完工时间及设备利用率作为性能评价指标对比SSBFTW与SSBDTW随工件到达密度的变化情况 （SSBFTW方法中取示例工件所有工序的平均加工时间为时间窗长度）。为尽可能保证得到的变化趋势具有普遍性，根据工单规则构建如表4所示的3个批量分别为10、15、20的示例工单进行3组试验，每组试验工件到达密度由大到小设置为[0，5]、[5，10]、[10，15]、[15，20]、[20，25]（相邻两工件的到达时间差在对应区间内随机取得，首个工件默认初始时刻到达），考虑平台启动时间、Agent通信延误等偶然因素对试验的影响，以每个工单每个档位进行5次试验取平均值作为对应档位的结果。

表4 各示例工单内的工件信息Table 4 Artifact information in each sample worksheet

SSBFTW与SSBDTW对比试验结果由图10所示，分析可知： （1）调度结果的最大完工时间与工件到达密度呈负相关，在工件到达密度较大时两种方法最大完工时间较接近，但SSBDTW调度结果的最大完工时间随工件到达密度的变化将显著优于SSBFTW； （2）调度结果的设备利用率随工件到达密度减小而减小，但SSBDTW调度结果的设备利用率均优于SSBFTW；（3）总体上，SSBDTW受工件到达密度变化的影响相比SSBFTW小。由此可见，SSBDTW在工件到达密度变化的小批量、多品种生产场景下具有更好的调度性能和适应性。

图10 SSBFTW和SSBDTW对比试验结果Fig.10 Comparison of SSBFTW and SSBDTW experimental results

3.3 异常调度策略有效性验证试验

本文选取工单2设置两组试验分别验证SSBDTW在设备故障、急件插单扰动下的有效性。处理设备故障的试验中，随机取得故障发生时刻为第93 min，故障机床为MA4，故障维护时间为137 min， MA4维护后的精度将由IT6下降至IT8；处理急件插单的试验中，随机取得插单时刻为第85 min，插单工件为示例工件3。设备故障、急件插单及无扰动状态下调度结果性能对比如图11所示，3种状态下以档位[0，5]为例的调度结果甘特图如图12所示。

图11 设备故障、急件插单与无扰动状态下的调度结果性能对比Fig.11 Performance comparison of dispatching results under equipment failure, urgent order and undisturbed state

图12 工单2 [0，5]档位调度结果甘特图Fig.12 Gantt chart of scheduling results of work order two [0, 5] stalls

由上述试验可知： （1）设备故障扰动的调度结果相比无扰动的，最大完工时间由562 min增加到575 min，性能下降约2.31%，减少的4个工序块为直接受机器损坏影响的工件TestJob_11的剩余未加工工序块，即设备发生故障后系统停止加工受损坏影响的工件，对剩余任务重新规划且与损坏前衔接较好，MA4在结束维修恢复使用后处理的工序块的精度需求也均未高于IT8；（2）急件插单扰动下的调度结果相比无扰动的，最大完工时间由562 min增加到613 min，性能下降约9.10%，增加的4个工序块为插单工件InsertJob_1的所有工序块，插单工件到达后系统便将其安排在最早可以开始加工的机床上进行加工，且插单工件的后续工序块均被连续释放，保证插单工件的优先完成。证明了本文调度策略处理异常扰动的有效性。

4 结论

本文通过分析生产调度问题的现状，发现其在当前柔性生产场景下应用效果并不理想，未充分利用加工环境中的动态数据，导致系统的实时性、灵活性较差。因此结合实际柔性作业车间生产流程，基于多Agent构建了柔性制造动态调度系统，并根据柔性作业加工特点以及调度过程中不同阶段的运行机制对传统CNP进行了改进，形成了以基于调度规则的动态时间窗调度方法为核心的动态调度策略。最后借助具备可视化交互界面的动态调度平台设计试验验证了本文动态调度策略的可行性，对当前实际柔性作业车间的生产活动具有一定的指导意义。