基于信息素的多Agent车间调度策略

陈 鸣 朱海华 张泽群 金永乔 王盈聪 唐敦兵

1.南京航空航天大学机电学院，南京，2100162.上海航天精密机械研究所，上海，201600

0 引言

当前制造业生产模式呈现出多品种、小批量、混流化的特征，在实际生产过程中，用户的个性化定制需求，以及各种无法预测的扰动，使得整个生产系统变得复杂、动态、随机，因此，急需寻求一种相应的动态调度方法来应对当前动态多变的制造环境。

动态调度也称在线式调度，是指利用生产系统实时的状态信息进行生产调度的一种方法。动态调度方法可以分为两大类：传统方法和智能方法[1]。传统方法包括最优化方法、仿真方法和启发式方法。其中使用最为广泛的是仿真方法，这种方法采用离散事件仿真方式模拟生产过程中的各种情况，通过数据分析为实际生产提供决策支持。该方法适用于各种复杂的生产系统，但其模型构建复杂，开发周期较长。智能方法包括专家系统、人工神经网络、智能搜索算法和多Agent方法。专家系统(expert system,ES)是通过模拟人类专家来解决调度问题的一种方法，该方法需要完善的知识库，因此开发周期较长、成本较高[2]。人工神经网络一般采用Hopfield或BP神经网络模型，用来降低计算的复杂性或构建决策模型，但往往需要庞大的历史数据和训练时间[3]。智能搜索算法包括遗传算法、粒子群算法、蚁群算法等，这些方法能够获得较优或最优的调度方案，但是计算时间长，实时性不好。多Agent方法是指一系列分散的自治智能体(Agent)通过与环境交互来解决问题的方法[4]，该方法能够有效地提高制造系统的柔性和可重构性[5]，符合复杂、动态、随机的生产系统的要求。

传统的多Agent方法一般采用基于市场招投标机制的合同网协议(contract net protocol,CNP)作为Agent间的协商机制，但是这种协商机制需要Agent间频繁地进行直接交流，导致整个系统的通信量过大，大量时间用在处理信息上，而无法对事件作出实时响应。同时，由于通信量限制，系统往往只能采取单一报价原则，导致系统优化目标过于单一、不符合实际。此外，由于基本的合同网协议仅根据局部的信息作出决策，因此导致了整体的优化性能较差。桑泽磊等[6]提出了一种基于节拍的改进合同网协议，减少了协商步骤，降低了Agent间的通信量，但该方法并未解决优化目标单一、整体优化效果差的问题。潘颖等[7]将改进的遗传算法封装在策略Agent中，实现了完工时间、总负载、最大负载和加工成本的多目标优化，解决了传统多Agent方法优化目标单一的问题。赵良辉[8]完全摒弃了合同网协议，设计了一种基于时间流的多Agent调度策略，通过抽取各个机床Agent的可用工时对一段时间内的工件Agent进行集中的优化调度。但以上方法Agent间的通信量都很大，实时性得不到满足。

传统或改进的协商机制都是Agent之间的直接通信，需要花费大量时间在信息处理上，无法实现实时响应。本研究针对柔性作业车间调度问题(flexible job shop scheduling problem,FJSP)，借鉴蚁群中的间接通信原理，通过信息素来完成Agent之间的协商，同时，在信息素的构成中融入了更多的全局性能指标信息，来实现全局的多目标优化。另外，本研究同时对生产任务分配阶段和缓冲区工件选择阶段的调度进行了优化，并且考虑了独立的调整时间，更加符合实际。

1 问题描述

传统的调度中对生产车间做出了过多的假设，使得调度方法不能很好地应用于实际生产。本研究移除了一些不必要的假设，使得车间模型更加符合实际。

问题描述如下：①加工任务连续不断地到来；②工件具有工序加工柔性，即一道工序能在几台不同机床上加工；③每一工件都有相应的交货期；④订单下达时间是随机的，工件类型、工件交货期只有在订单下达时知道；⑤每台机床同一时间只能加工一个工件；⑥工件调整时间单独考虑且与机床上一道加工工序有关；⑦不考虑运输时间；⑧考虑机床故障，且当故障发生时任何工序都不能在该机床上加工直到故障修复；此外故障发生时机床上正在加工的工件按报废处理，并重新下料。

1.1 调整时间

调整时间(setup time)主要指机器在加工下一道工序前机器的清理，更换夹具、模具等辅助工件而进行的准备活动所花费的时间[9]。调整时间可以分为顺序无关调整时间和顺序相关调整时间[10]。顺序无关调整时间指与机器上道加工工序无关的调整时间，顺序相关调整时间指与机器上道加工工序相关的调整时间。大部分多Agent方法仅考虑了顺序无关的调整时间，并作为加工时间的一部分进行计算，这种假设简化了问题的复杂性，但不符合车间的实际情况，也不利于调度问题的优化。本文将更换夹具所用的时间作为调整时间来单独考虑。如果加工工件与机床前一个加工工件类型相同，则不需要更换夹具，此时调整时间为0，否则调整时间以加工时间的30%计入[9]。

1.2 性能指标

本文考虑的性能指标主要包括平均流经时间、最大流经时间、平均拖期时间、最大拖期时间、加工成本、加工能耗，其数学模型如下：

(1) 平均流经时间

(1)

(2) 最大流经时间

f2=max(Ci-Ri)

(2)

(3) 平均拖期时间

(3)

(4) 最大拖期时间

f4=max(Ci-Di)

(4)

(5) 总加工成本

(5)

(6) 总加工能耗

(6)

2 调度策略

2.1 基于多Agent系统的动态调度模型

基于多Agent系统的动态调度模型由工件Agent(job Agent)、机床Agent(machine Agent)、管理Agent(manager Agent)组成。各Agent主要职能如下。

(1)管理Agent。管理Agent具有注册功能，记录着当前所有Agent的信息和状态，可以为工件Agent提供加工机床的信息。此外，管理Agent实时监控机床的状态，当机床发生故障时，管理Agent通知相应的机床Agent，并注销当前机床；当机床修复时，重新进行注册。

(2)工件Agent。在任务分配阶段，即工件选择机床阶段，工件Agent通过向机床Agent招标来获得各机床当前的信息素值，计算各机床的转移概率，选择转移概率值最大的机床；在缓冲区工件选择阶段，工件Agent实时更新自己的信息素值，并在收到机床招标请求时发送当前信息素值。

(3)机床Agent。在任务分配阶段，机床Agent向提出招标请求的工件Agent发送自己当前的信息素值；在缓冲区工件选择阶段，机床Agent 向缓冲区工件Agent招标来获得各工件当前的信息素值，考虑顺序相关调整时间，计算各工件的转移概率，选择转移概率最大的工件进行加工。

2.2 动态调度策略

图1是本文提出的多Agent调度策略的UML序列图。管理Agent、工件Agent和机床Agent相互协作，共同求解出基于流经时间、拖期时间、加工成本、加工能耗的全局多目标优化调度方案。

图1 多Agent调度策略UML序列图Fig.1 UML sequence diagram of multi-Agent scheduling strategy

各Agent之间协商的具体步骤如下:

(1)机床Agent在管理Agent处进行注册。

(2)有工件释放工序时，工件Agent向管理Agent提出加工请求，管理Agent发送可以选择的加工机床清单。

(3)工件Agent向清单中所有机床Agent发起招标。

(4)机床Agent向工件Agent投标，发送当前的信息素值。

(5)工件Agent评估所有的投标值，选择转移概率最大的机床进行加工，并向对应的机床Agent发送“接受”消息。

(6)被接受的机床Agent回应确认，如果当前机床空闲那么直接进行加工，否则存入缓冲区等待加工。

(7)机床加工完成后，如果工件完成所有加工，那么存入仓库并注销工件Agent，否则工件Agent释放下一道工序，重复步骤(2)～(6)；同时，机床对自己缓冲区内的工件Agent进行招标。

(8)缓冲区内的工件Agent发送当前信息素值，进行投标。

(9)机床Agent在考虑调整时间的同时评估所有的投标值，选择转移概率最大的工件进行加工，并向对应的工件Agent发送“接受”消息。

(10)相应的工件Agent回应确认，机床对此工件进行加工，加工完成后重复步骤(7)～(10)。

此外，当机床出现故障时，管理Agent注销故障机床信息并通知相应的机床Agent，相应的机床Agent通知缓冲区工件Agent重新招标，故障机床上正在加工的工件按报废处理，同时管理Agent通知ERP系统重新下单；当机床故障修复时，机床Agent通知管理Agent，管理Agent重新注册机床信息，并更新机床状态。

2.2.1任务分配阶段

机床信息素

(7)

转移概率α,β,γ,δ是用来平衡信息素、加工时间、加工能耗、加工成本影响的平衡参数，其具体的设置值与实际的生产环境及企业看重的优化目标次序密切相关。其表达式为

(8)

式中，φmi为招标工件在机床上加工所需时间的倒数；μmi为加工能耗的倒数；ωmi为加工成本的倒数。

对于一个实际的生产环境及确定的优化目标次序，一般通过实验仿真的方法对参数进行设置调整以达到最佳效果。本文在对多目标进行优化时，以基于时间的优化指标(流经时间及拖期时间)为主目标，而基于成本、能耗的指标为次目标。通过仿真实验不断地调整参数，最终设置α=1,β=6.5,γ=1,δ=1，此时可以获得最佳的基于时间指标的优化结果以及一定的成本、能耗优化。

2.2.2缓冲区工件选择阶段

工件信息素

(9)

转移概率

(10)

式(7)和式(9)都是关于时间的函数，因此机床信息素和工件信息素都需要实时更新。

2.3 算法时间复杂度分析

假设有m台机床，n个工件，每个工件有r道工序，每道工序都具有工序加工柔性。

(1)任务分配阶段。每个工件Agent在任务分配阶段需根据信息素值为当前释放工序选择加工机床。由信息素计算公式可知，每台机床信息素的时间复杂度是常数，机床数最多为m，则每个工件的时间复杂度为O(m)。该段时间最多有n个工件调度，所以任务分配阶段的时间复杂度为O(mn)。

(2)缓冲区工件选择阶段。每次机床选择工件时都要遍历当前的缓冲队列，缓冲队列中最多有n个工件。工件信息素的时间复杂度为常数，所以每次机床选择工件的时间复杂度为O(n)。该段时间内最多有m台机床选择工件，所以缓冲区工件选择阶段的时间复杂度也为O(mn)。

综上所述，算法总的时间复杂度为O(mn)，与传统的多Agent方法相同。

3 实验验证与分析

传统的多Agent方法在任务分配阶段一般是以招标任务完工时间最早为决策依据，同时在选择缓冲区工件时采用FIFO原则，即先到先加工原则。而本文采用的是基于信息素的间接通信方式，并对任务分配阶段和缓冲区工件选择阶段都进行了优化。为了验证提出的基于信息素的多Agent方法的有效性，本文设计了相关的仿真实验，将两种方法进行了对比。

3.1 仿真实验设计

作业车间共包含8台机床，3台数控车床，3台数控铣床，2台加工中心。数控车床可以完成车削和磨削的加工，数控铣床可以完成铣削和钻孔的加工，加工中心可以完成所有类型的加工，详细的机床工艺能力信息如表1所示。

表1 机床工艺能力信息表

加工工件主要有4种类型，详细信息见表2。表中的加工时间指的是工件工序的平均加工时间，它在某一机床上的实际加工时间是工件工序的平均加工时间和机床加工系数的乘积。工件订单的到达时间间隔服从指数分布，并且每种工件类型的到达概率都为0.25，指数分布的平均值

(11)

实验设定车间利用率为0.9，所有工件平均加工时间取71.5，机床总数为8。

工件订单的交货期采用全部工作内容(TWK)方法[11]计算：

(12)

表2 加工工件信息表

本文取c=4和c=8，分别表示紧张的交货期和宽松的交货期两种情况，来验证本文所提方法在不同交货期情况下的适应能力。

机床故障时所需的修复时间以及两次故障之间的间隔时间服从指数分布，指数分布的平均值分别是平均故障修复时间(MTTR)和平均故障间隔时间(MTBF)，并且所有机床的MTTR和MTBF都相同，本文实验设定MTTR为85，MTBF为4 165。

3.2 仿真结果分析

本文共在5种不同的情景下进行了对比实验分析，以验证本文所提方法的有效性和优越性。情景1是在不考虑机床故障及独立调整时间，并且在宽松交货期的情况下，比较传统多Agent方法和本文所提方法的优劣；情景2是在不考虑机床故障及独立调整时间，并且在紧张交货期的情况下，比较两者的优劣；情景3是在不考虑独立调整时间，但考虑机床故障，且在宽松交货期的情况下，比较两者的优劣；情景4是为了验证考虑调整时间的有效性，在考虑调整时间、不考虑机床故障，且交货期宽松的情况下，与情景1中的实验结果进行对比，突出单独考虑调整时间优化的有效性；情景5在不考虑机床故障，但考虑独立的调整时间，且在宽松交货期的情况下，验证考虑成本、能耗的多目标优化的有效性。

由于在实验开始阶段车间加工工件少，会有一段波动期，这严重影响了比较实验的客观性，因此必须在波动期结束后进行比较。通过对平均流经时间及平均拖期时间的观察，发现在第500个工件到达后，系统进入稳态。因此，选择对第501～2 500个到达的工件进行比较分析。

在情景1下的实验结果见表3。由实验结果可知，本文提出的基于信息素的多Agent方法在宽松交货期下，平均/最大流经时间及平均/最大拖期时间这4个性能指标都远远优于传统的多Agent方法，验证了本文所提方法的有效性。

表3 情景1实验结果(不考虑机床故障及独立调整时间，交货期宽松)

在情景2下的实验结果见表4。由实验结果可知，本文提出的基于信息素的多Agent方法，在紧张的交货期下，优化性能依旧远远优于传统的多Agent方法，验证了本文所提方法面对紧张交货期的适应能力。

表4 情景2实验结果(不考虑机床故障及独立调整时间，交货期紧张)

在情景3下的实验结果见表5。由实验结果可知，本文提出的基于信息素的多Agent方法，在遇到机床故障扰动时，依旧能有很好的优化性能，且远远好于传统多Agent方法，验证了所提方法应对机床故障扰动的有效性。

表5 情景3实验结果(不考虑独立的调整时间，考虑机床故障，交货期宽松)

在情景4下的实验结果见表6。与情景1中本文方法实验结果比较可以发现，考虑独立的调整时间，可以大大提升优化效果，因此，考虑独立的调整时间是十分有效的。

表6 情景4实验结果(考虑独立的调整时间，不考虑机床故障，交货期宽松)

在情景5下的实验结果见表7。由实验结果可知，在考虑多目标优化的条件下，平均流经时间、最大流经时间、平均拖期时间、最大拖期时间这4个性能指标相对情景4的结果并未降低很多，而对应的加工成本降低了4.7%，加工能耗降低了4.5%，大大节约了生产的成本和能源。

表7 情景5实验结果(考虑独立调整时间，不考虑机床故障，交货期宽松，多目标)

在考虑独立的调整时间、不考虑机床故障、交货期宽松的条件下，本文进一步分析了能耗、成本指标与基于时间的指标(平均流经时间、平均拖期时间)之间的约束关系以及参数设置对多目标优化效果的影响，见图2和图3。两次分析实验数据均是在保持时间指标平衡参数α,β,ε,θ值不变的情况下，单独对γ或δ取值得到。由图可见，能耗、成本指标与基于时间的指标近似成负相关性，随着γ、δ值的不断增大，总能耗与总成本指标不断下降，而平均流经时间和平均拖期时间却逐渐上升。据此，企业在生产中可以结合实际需要，选择进一步放宽时间相关指标，增强成本能耗相关指标来达到节约成本能源的目的。

图2 γ值对调度结果的影响Fig.2 The effect of γ on scheduling results

图3 δ值对调度结果的影响Fig.3 The effect of δ on scheduling results

4 结语

本文针对FJSP问题，借鉴了蚁群中的间接通信原理，使得Agent间可以通过信息素完成间接通信，大大减少了通信量，增强了实时性。通过在信息素中加入更多的全局信息，实现了全局的多目标优化。此外，对任务分配阶段和缓冲区工件选择阶段都进行了优化，并且考虑了独立的调整时间，进一步提高了优化性能且更加符合实际。最后，通过实例仿真，验证了本文所提多Agent方法的有效性。