基于规则的柔性作业车间机床与AGV联合调度优化*

郭沛佩 付建林 江海凡 王 坤

(①西南交通大学先进设计与制造技术研究所，四川 成都610031； ②成都运达科技股份有限公司，四川 成都610031))

自动导引车系统(automatic guided vehicle system，AGVS)作为一种灵活高效的物流系统在制造、仓储配送等领域有着广泛的应用，目前柔性作业车间越来越多地采用AGV进行物料输送，柔性作业车间集成AGV联合调度问题应运而生。国内外对传统作业车间AGV调度研究已较多，但这些研究都假定每个工件的工艺路线是确定的[1]，而在柔性作业车间中，由于每个工件的每道工序都有不同机床可供选择，且在不同机床上的加工时间不同，工件的可变工艺路径又导致AGV路径选择不同，这些不同组合会有不同结果，也更符合现代多品种小批量的生产方式，因此优化柔性作业车间机床和多AGV的集成调度具有重要意义[2]。

集成调度问题是NP难问题，最先考虑了诸如数学建模或基于图形的算法之类的集中方法，尽管这些方法能找到最佳解决方案，但它们只能应用于小型场景[3]。国内外学者开展了一系列围绕柔性作业车间调度的研究，元启发式智能算法提供了有效的途径[4]，包括遗传算法[5]、粒子群优化算法[6]和模拟退火[7]等，但随着求解问题复杂度上升，这些算法的解空间呈指数爆炸性增长，计算时间长，且容易出现早熟与陷入局部最优问题。除此之外，启发式规则调度方法由于其易于实现，计算效率高、有健壮的鲁棒性，被广泛应用于车间调度问题。从实际生产系统的复杂性、规模性和可操作性角度考虑，启发式调度规则仍然是目前最可行和有效的求解方法[8]。柔性车间中，不同资源有不同调度规则，可采用单一规则或组合规则方式解决实际问题，杨小佳[9]等人为比较柔性装配作业车间中两类动态调度策略，采用了优先度规则方法研究不同扰动下的完全反应式调度，得出采用组合规则性能更优结论。Doh Hyoung Ho[10]等人则比较了不同组合规则，证明采用恰当规则组合可优化车间性能，朱伟[11]采用规则导向思想选择更合适的规则组合解决了柔性作业车间多目标集成优化问题，但他们所解决的调度问题针对的都是车间中机床与作业排序联合调度问题，基于规则的机床与AGV联合调度研究较少；Jens Heger[12]采用不同规则组合解决了对作业排序、机床和AGV这3类问题的调度，但并未考虑系统中所需配置AGV数量对调度结果的影响；文献[13]以最小化平均延迟时间为目标采用神经网络预测不同AGV和机器利用率下车间所适用的3类规则组合，但并未考虑不同任务水平对求解模型性能影响。

本文采用离散事件建模仿真方法搭建了一个柔性作业车间仿真模型研究机床与AGV联合调度问题，以最小化平均流动时间、完工时间、合适AGV平均利用率与完工数量为指标比较了3种工件路由规则与3种AGV调度规则的组合影响，确定出最优规则组合与所需配置的AGV数量，并在确定的最优规则组合下寻找最优的任务到达模式与AGV数量，得到柔性生产车间性能最优时的最佳规则组合、最佳AGV数量和最佳任务达到模式。

1 问题描述

1.1 柔性作业车间联合调度问题描述

柔性作业车间机床与AGV联合调度问题一般可描述为工件集J={J1,J2,…,Jn}在机床集M={M1,M2,…,Mm}上加工并由AGV集T={T1,T2,…,Tk}实现其搬运的过程。求解该类问题通常需满足如下假设条件：

(1)初始时刻，所有工件均处于待加工状态，所有机器均处于空闲状态。

(2)同一时刻，同一台机器只能加工1个工件的某道工序。

(3)同一时刻，同一工件只能被一台机器加工，且不允许中断正在加工的工序。

(4) 同一工件的工序加工顺序固定且不可更改，不同工件的工序间没有顺序约束关系。

(5)同一AGV1次只能运输一个工件。

车间中每个工件包含系列工序Oij(i为工件号，j为工序号)，每道工序都将在M中的某台机床上加工，每加工完一道工序都需要T中的某台AGV搬运至下道工序位置，故柔性作业车间机床与AGV联合调度问题可看作是每道工序加工与运输问题的组成

1.2 主要的优先级规则

优先级调度规则方法指按一定的准则对待加工工件、加工设备、运输设备进行优先级排序，以提供1个合适的解决方案。本文采用不同工件路由规则(一道工序有多台机床可供选择时，从中选出一台机床的操作称为工件的路由，即调度机床)、AGV调度规则组合的方法研究此问题，并找到最合适的规则组合优化调度。文献[13]采用了一些常用的工件路由规则，文献[14]回顾了多种AGV调度规则,这些规则都能有效解决车间调度问题，据此本文所采用的规则如表1所示：

表1 主要的优先级规则

评价不同规则组合时，采用多重性能指标如表2所示。

表2 规则组合及其所需AGV数量的评价指标

1.3 规则组合下的AGV数量配置、任务到达模式问题描述

作为柔性作业车间的主流物料搬运设备，AGV数量将对表2中的评价指标产生较大影响：数量过少将导致搬运任务不能得到及时处理，工件大量堆积在系统中，各指标值过大，AGV过忙，可能造成无论采用何种规则组合同时调度机床与AGV，调度结果都十分不理想，所评价出的规则组合是没有实际意义的；AGV数量过多，即便不会对评价指标造成过大影响，也将直面资源浪费问题。故需要确定出系统所需配置的AGV最佳数量。考虑到不同规则组合可能对最佳AGV数量造成影响，故其需与规则组合同时评判。

在最优规则组合以及最优AGV数量配置下，系统性能不一定为最优，为进一步提升系统性能，可考虑前两种条件最优情况下任务到达模式影响，主要包括任务到达频率和任务投产方式两方面内容，研究过程中，各影响因素可能相互制约，最后相互确定出各自的最优选择。

2 验证实例及建模仿真过程

2.1 实例描述

本研究所设计的柔性作业车间共包含6台机床M1～M6，每台机床具备1～2种加工技能，以满足加工柔性。物料搬运设备采用AGV。加工产品有4类分别为：J1、J2、J3和J4，每类产品包含4道工序，其工艺路线及每道工序可供选择的机床及其加工时间如表3所示，如处理J1产品的第一道工序O11时可选择M4、M5两台机床，选择M4时，所需加工时间P11为100 s，选择M5时，P11为70 s。

车间实际生产时，工件到达时间间隔服从泊松分布，泊松参数λ=140，每类工件待加工数量为250件，采用J1～J4顺序生产投产方式，AGV数量待定，企图在此生产条件下，找到车间性能最优时的规则组合与所需AGV数量，以解决机床与AGV联合调度问题。

联合调度问题解决以后，可能存在原本的生产条件不合理的情况，为已找到的最优规则组合匹配一个更合适的生产条件，将进一步提升系统性能。此时规则组合为已知条件，待优化参数为泊松参数λ，AGV数量，投产方式及批量等。

表3 每道工序可供选择的机床集及加工时间

2.2 离散制造系统建模及仿真

PlantSimulation是一款面向对象的离散事件动态系统仿真软件，为建模、仿真运行和显示提供了一种完全面向对象的、图形化的和集成的工作环境[17]。利用Plant Simulation对设计的柔性作业车间建模及控制过程如下：

(1)车间布局及建模

利用PlantSimulation对设计的柔性作业车间建模如图1所示:建立6台柔性机床，依次命名为M1、M2、M3、M4、M5和M6，每台机床都有一个入口缓冲BufIn和出口缓冲BufOut,如BufInM1和BufOutM1。生产订单由jobsource对象产生，产生的四类工件命名为J1、J2、J3和J4。AGV由AGVSource对象产生，其长度为1.5 m，行驶速度为1 m/s，加速度为0.5 m/s2，系统所能容纳的AGV最大数量为6，AGV在没有运输任务的情况下，将停靠在Parking区域轨道(最左侧轨道)上。所有工序加工完成的工件最终将被代表系统出口的Drain对象回收。

(2)仿真过程控制

仿真过程控制包括生产订单控制、工艺流转控制、物流运输任务控制3方面内容。生产订单由source对象控制，有顺序生产和顺序循环两种投产方式，任务到达频率也在此处设置。工艺流转控制主要保证工件每加工完一道工序便能读取到下步工序信息，以便后续加工任务展开。物流运输任务控制则实现工件在机床与机床之间流转，流转的搬运任务由AGV完成。工件在进入系统或加工完一道工序离开sourcebuf、BufOut等出口缓冲时将触发路由控制程序，按待加工工序读取该工件的工序表，然后按照给定的路由规则为该工件调度下道工序的加工机床并记录其加工时间，同时工件在出口缓冲离开事件意味着搬运任务的产生，此时触发的路由程序还要将工件从当前工序到达下步工序的搬运任务信息实时存储，这样上层程序检测到有待执行搬运任务时，将按照给定的调度规则为其调度空闲AGV，任务一旦被执行，便从任务表中删除。

3 仿真试验及结果分析

3.1 最优规则组合及其所需AGV数量分析

本研究主要考虑上文提到的3种路由规则和3种调度规则的组合影响，共有9种规则组合待比较。仿真运行时，利用试验管理器管理试验，在同一种规则组合下，AGV数量为1～6，每次试验重复5次，共进行270次试验。

试验结果分析如下：图2～4所示为9种规则组合下的3种性能指标变化趋势图，在不同规则组合下，各指标走势相同，但各点数值有差异，该结果表明，采用规则调度方法能解决柔性作业车间中机床与AGV联合调度问题，且针对同一车间存在一个最优规则组合优化调度结果。

从图2～4可看出在所有规则组合下系统的性能指标1工件平均流动时间随AGV数量增加呈逐步下降趋势，在数量为4时开始趋于稳定。性能指标2完工时间随AGV数量增加也呈逐步下降趋势，且在AGV数量为3时稳定，但此时的平均流动时间值远大于AGV数量为4时的值，故AGV应配置4辆，此时4辆AGV的平均利用率均在81%左右，相比3辆AGV时的88%左右平均利用率，配置4辆AGV时繁忙程度也更合适。综合比较，该模型在所有规则组合下的小车数量最优值为4。结果表明，在同一任务水平下，采用不同的规则组合不会对所需AGV最佳数量造成太大影响，但会在不同程度上改善系统性能。

在所有规则组合下，AGV数量为4时，系统性能达到稳定，可采用此时的指标值评判规则组合，由于完工时间与AGV平均利用率两项指标的稳定值在不同规则组合下变化不大，故选择平均流动时间评判，其结果如图5所示，可以发现无论何种调度规则下均为路由规则LWT优于LUM，再远优于SQ。无论何种路由规则情况下，调度规则均为STT最优。最终确定该模型最适用的AGV数量与规则组合为：小车数量为4时的LWT/STT组合。为更直观体现最优规则组合对平均流动时间影响，定义系统性能提升指数μ，按式(1)计算。

(1)

得到最优规则组合较于其他组合系统性能最大提升6%。

3.2 最优任务到达模式及其所需AGV数量分析

上文所找到的最优规则组合，是在已知生产条件任务到达频率服从泊松140分布，顺序投产下研究的，针对此最优规则组合，可能还将存在更优的任务到达模式，进一步提升系统性能。

(1)任务到达频率分析

固定规则组合为STT/LWT，变化泊松参数λ值从40～220，AGV数量从1～6，研究最优规则组合下最优的任务到达频率及所需AGV数量。仍采用试验管理器管理试验，每次试验重复5次，共进行300次试验，试验结果分析如下：

如图6所示，在不同的任务到达时间间隔下，工件的平均流动时间随AGV数量增加呈不同变化趋势，具体趋势分析及取舍结果如表4所示。

表4 不同值下平均流动时间随AGV数量增加变化趋势

其中λ<100时，AGV数量增至5而平均流动时间突增，这是由于各机床加工能力不足，任务投产频率过快，工件被搬运到机床入口缓冲区的频率也过快，工件大量堆积在入口缓冲中，等待加工时间过长所造成的。

如图7所示，相反增大任务到达时间间隔会不断增大系统的完工时间。结合前面分析，完工时间指标下，选择泊松120、AGV数量为4的情况为最优。从图8可看出增大任务到达时间间隔也会不断降低所需AGV的平均利用率，选择泊松120、AGV数量为4的组合时AGV平均利用率为86.8%，利用率较高，应选择数量为5时，利用率为77.2%更合适，此时指标1平均流动时间相比于AGV数量为4时的20 min也更稳定更低，为17 min，与最终的稳定值更接近。

原生产条件泊松140分布时，在AGV数量为4时各指标均达到最优，虽然其平均流动时间为16 min，利用率为81%，都比泊松120。5辆车时更好一些，实则很接近，但其完工时间高出6个多小时，最终确定最优任务到达时间间隔服从泊松120分布，最佳配置AGV数量为5。

新确定的泊松120、AGV数量为5的生产条件，可能会对已确定的最优规则造成影响，为验证此影响是否存在及是何影响，在此条件下再次进行规则组合比较，验证结果如图9所示，最优规则组合仍为LWT/STT，试验前提条件成立，此时最优规则组合下的平均流动时间值较之其他组合系统性能提升指数μ最大达到26.8%，再次证明采用STT/LWT规则组合将提升系统性能，同时也说明不同的任务到达频率将会影响规则组合对系统性能的提升指数，也有可能改变最优规则组合：SQ路由规则由最次变为次优。两种生产条件下系统性能稳定时的平均流动时间值相差不大，为更直观表达改变任务到达频率对系统性能影响，定义完工时间指标下的系统性能提升指数φ，按式(2) 计算：

(2)

得到泊松120、AGV数量为5情况下系统性能较之泊松140、AGV数量为4时提升18%。

(2)任务到达方式分析

在最优规则组合、最优任务到达时间间隔下，选择最优任务到达方式，包含投产方式与批量两方面内容。具体试验内容如表5所示。

表5 任务到达方式试验内容

第1、2种任务到达方式下的仿真结果如图10～11所示，在小车数量为5时，系统的加工能力分别饱和在5 030件与5 027件，相差不大，但后者工件的平均流动时间增加了近两分钟。故前一种到达方式更好。

第3种到达方式下的仿真结果如图12～13所示，结果表明在泊松120到达时间间隔下，一旦任务一次到达两个及以上，工件在系统中的平均流动时间将大幅增加，而系统加工能力却得不到大幅提升，这是由于工件一次到达过多而机床加工能力不足所造成的。故适应该模型最优的任务到达方式应为顺序投产、批量为1。

4 结语

柔性作业车间机床与AGV联合调度问题是典型NP难问题，求解过程具有一定复杂度，为此采用基于优先级规则组合的方法，本文考虑了工件路由规则和AGV调度规则两方面的规则组合，基于离散事件建模与仿真方法对9种规则组合进行对比研究，结果表明，将LWT作为工件路由规则、STT作为AGV调度规则可提供良好的结果，在此种规则组合下，进一步可确定最优的任务到达模式为采用顺序投产、批量为1、到达频率服从泊松120分布，以及系统应配置AGV的最佳数量为5。在这些最优条件下，系统性能平均流动时间将缩短26.8%、完工时间将缩短18%，证明了采用合适的优先级规则组合、任务到达模式以及AGV数量可以有效解决机床与AGV联合调度问题、优化系统生产性能。