基于变邻域遗传算法的离散制造物料配送调度优化

李广博，于 东，胡 毅

(1.中国科学院大学，北京 100049；2.中国科学院沈阳计算技术研究所 高档数控国家工程研究中心 ，沈阳 110168；3.沈阳高精数控智能技术股份有限公司，沈阳 110168)

0 引言

离散制造车间加工件种类繁多，加工工艺复杂，对车间实时监控和物流调度有较高要求。目前,许多的企业采用RFID技术实现对车间设备的实时监控，使用自动导引车(Automatic Guided Vehicle，AGV)来实现加工件的集中管理和无人搬运[1]。AGV具有精确的室内定位能力以及自动驾驶能力，可以与离散制造车间生产无缝融合，结合AGV搬运与FJSP车间调度的优化研究对实现生产物料的高效稳定运送和提高企业生产效益具有重要的意义。

近年来，人工智能方法在调度研究方面取得了长足进展，以遗传算法、粒子群算法等为代表的智能算法被诸多学者研究改进并取得了良好的效果。欧阳森山等[2]采用粒子群算法求解评价与遗传算法结果择优进化的方式进行协同求解；黄海松等[3]和YUAN Y等[4]分别对模拟退火算法和邻域结构进行改进；以上算法均未对加工件搬运时间进行计算。王雷等[5]改进了遗传算法对含AGV柔性车间作业调度进行求解，但作者只考虑了工件运输时间，忽略了AGV的调度时间； Zheng Y等[6]采用禁忌搜索算法研究了机器和自动引导车辆调度问题，但只考虑了一台AGV的情况；龙传泽等[7]采用遗传算法与启发式混合算法对含有AGV的JSP问题进行研究，没有对机器柔性调度进行研究。

针对遗传算法局部搜索能力差的问题，根据已有文献的研究，设计了一种变邻域混合算法对AGV柔性车间调度问题进行求解，调整了遗传算法种群初始化方式，使用随机方式与机器使用率优先的初始化策略，采用了工序、机器与AGV编号的分段编码技术，使用锦标赛选择方法对个体进行选择，并融合了基于移动和交换工序的变邻域搜索算法提高了算法的求速度和解的质量。

1 问题描述

1.1 AGV调度模型

以某飞机制造企业离散生产车间为模型，含有AGV搬运的柔性车间作业模型如图1所示，通过立体仓库将工件分配到AGV上，再由AGV将工件运送到相应工位上进行加工，每个工位上都存在物料缓存区，将待加工的工件和加工完毕的工件放到缓存区，通过调度系统可以实现AGV对工件在工位之间的搬运控制。

图1 AGV搬运模型示意图

含有AGV搬运的FJSP问题是传统FJSP问题的扩展，不仅需要考虑工序的顺序约束和每道工序可用机器集的选择情况，还需要考虑AGV对加工件的搬运调度。模型中所涉及的机器、工件、AGV等需要符合的约束规则如下：

①工件的某道工序一旦选定对应的工位机器在完工前不允许更换。

②工件的某道工序从开始被工位设备处理到完成必须保持连续。

③所有的工件都有同级别的优先度，都可以从零时刻开始被机器加工。

④AGV必须等待工件当前任务处理完毕后，才可以将工件送到下一台工序的机器工位。

⑤AGV运送工件上下料的时间忽略不计。

1.2 数学模型

本文参数符号定义如下：

n:工件总数，工件Jj:{J1,J2,…Jn}；

m：机器总数，机器Mi:{M0,M1,…Mn}，其中M0表示立体仓库；

w：AGV总数，AGVAi:{A1,A2,…An}；

kj:第j个工件的工序总数；

l:工序序号，l= 1,2,3，kj；

Ojk:第j个工件的第k道工序；

Mijk:表示在工位机器i上对工件j的第k个待处理工序进行加工；

mjk:可以对工件j的工序k加工的机器数；

yijk:工位i上对应工件j第k道工序的时间；

sjk:工件j的工序k开始被加工时间；

cjk:工件j的工序k被机器处理完成时间；

ativ:AGV从机器i到机器v所花费的时间；

rtijkw:AGV搬运工件j的工序k到机器i时刻；

Wtj:AGV完成搬运工件j到达仓库的时间；

评价指标函数：

(1)

约束条件：

①工件加工顺序约束，最大加工时间不能小于任意工件完工时间，工件某道工序开始时间不能超过工件完成时间。

cjk≤sj(k+1)

(2)

cjk≥sjk+qijk×yijk

(3)

②在相同工位上某一时刻只能对一道工序进行处理，其中E代表足够大的正整数。

qijk+sjk≤shl+E-E×rijkgl

(4)

cjk-sj(l+1)≤+E-E×rijkg(l+1)

(5)

③AGV在工件上一个待处理工序完成才能开始搬运工件到下一个设备上。

sjk+qijk≤ativ+rtijkw

(6)

2 混合算法设计

2.1 编码与初始化

含有AGV搬运的FJSP问题由机器选择、工序排序以及AGV序列编码三个子问题构成，根据不同机器加工时间、空闲情况等约束为每道工序选择合适的机器，然后对工件的工序进行排序，最后按均匀分配的方式根据工序编码生成AGV搬运序列，确定加工顺序和时间。对Ho等[8]编码实现进行了改进，机器选择部分由二进制编码改为整数编码。表1所示为一个3×4FJSP问题实例，表中的整数代表工序在相应工位上所需要花费的时间，AGV在机器之间的搬运时间如表2所示。

表1 3×4 FJSP问题实例

表2 AGV搬运时间

最终编码的实现结构如图2所示，机器选择编码中的数字对应工件加工顺序的可加工设备集合中第几台机器，工序顺序的编码中的整数代表所有工件相应的每道工序，基因序列中的每一位整数代表加工的工件号，其相对出现的位置对应表示第几道加工工序，以两台AGV小车搬运情况的编码序列为例，AGV序号中的整数表示AGV车的编号。

图2 染色体编码示意图

种群初始解的生成对算法求解问题的速度和质量有较大的影响，当前大多数研究以随机、启发式、主动调度等方式进行初始解的编码生成，本文在以上文献研究基础上，将机器利用率纳入初始考虑条件，采用机器最大利用率优先、工件工序的AGV最大利用率优先、随机生成相结合的初始化方式，三种初始化方式的比例为0.4:0.4:0.2。

2.2 遗传操作

2.2.1 选择操作

选择操作可以使适应度较高的基因有更大的生存概率，保证基因后代继承父代的优秀特性，可以使算法求解效率得到有效提升。采用锦标赛选择(tournament selection)方式对编码个体进行筛选选择出符合适应度要求的目标，每次从父代染色体编码群体中随机地选出d个基因，根据最大加工时间适应度规则计算函数求解出适应度f(j)，将满足条件适应度的个体保存到交叉池中，重复操作直到选择池中基因的数量满足要求。

2.2.2 交叉操作

交叉操作是利用父代个体经过一定策略的组合后产生新的个体，使部分优良的基因序列得以保留到子代中。机器选择编码采用均匀交叉(uniform crossover，UX)操作，在[1,Z0]范围内通过程序生成随机整数r，然后将父代染色体P1和P2对应机器选择编码基因复制到子代中，最后将父代余下的基因复制到子代C2和C1中，机器选择的均匀交叉过程如图3所示。

图3 机器选择均匀交叉示意图

工序顺序染色体编码的交叉操作借鉴了优先操作方法[9]和KACEM等[10]的POX混合交叉的优点，随机将工件集{J1,J2,…Jn}分为两部分，复制P1和P2对应工件集合基因到子代C1和C2中，将不包含在工件集的基因复制到C2和C1中，编码交叉过程如图4所示。

图4 工序编码交叉示意图

2.2.3 变异操作

变异操作是染色体编码产生全新解的重要方式，通过改变染色体的某些基因来生成新个体，可以保证算法的全局搜索能力，防止过早出现收敛的情况。采用动态变异的策略，变异概率求解公式为：

pm=pmax-(pmax-pmin)×gn÷gnmax

(7)

Pm代表当前变异概率，随着程序迭代的次数自适应的改变概率，gn表示程序当前迭代进行的次数，gnmax表示初始设置的程序最大运行次数。机器编码采用单点变异，工序编码采用交换变异策略。

2.3 变邻域结构

变邻域搜索(variable neighborhood search,VNS)算法是求解组合优化问题的有效局部算法。VNS通过不断计算初始解邻域中解集的评价适应度，选择出更优秀的结果则替换当前基因编码，如此反复循环计算直到满足程序设定的约束条件。含有AGV约束的FJSP问题在邻域结构设计生成时需要考虑加工设备选择的条件，本文采用了移动工序和关键工序块交换的邻域结构。在移动工序邻域结构中，通过求解关键路径计算出车间调度中的对应的关键工序集{O1，O2，…,On}，从上述工序集合中随机选择出一道关键工序v，将v插入到上述染色体中得到邻域解；工序块交换邻域求解过程如图5所示，通过交换关键工序子块中非同一工件末尾相连的两道工序，求解出新的邻域编码。

图5 关键工序块邻域求解示意图

2.4 混合算法流程

改进变邻域遗传算法流程如图6所示，首先设置种群规模等基本参数，采用启发式与随机结合方式生成初始种群，并对种群适应度进行计算，然后采用全局最优库和锦标赛策略选择个体，进行交叉、变异后采用移动工序和关键工序块交换方式的变邻域搜索扩大搜索范围，最后当程序循环次数达到预设值时结束算法。

图6 变邻域遗传算法流程图

3 算例测试

为了对本文提出混合算法的有效性进行实例化验证，使用MATLAB编写代码实现变邻域遗传算法，测试了Bilge等提出的40个基准算例，包含4种设备布局方式、4台加工设备以及10个加工集。算法最大迭代次数设为100,初始种群规模200,种群初始化策略比例4:4:2,编码的最小的最大交叉概率为(0.5，0.9)，自适应动态变异概率设计为(0.01，0.1)，算法的优化目标为最大完工时间最短，连续运行100次。

首先将本该改进的变邻域遗传算法(GAVNS)与传统遗传算法(GA)进行测试对比，在两台AGV情况下，对Ex32算例进行计算出，两种算法每代最优均值变化曲线结果如图7所示，从图中可以看出GAVNS算法较GA能更快的收敛，避免了算法过早的陷入局部最优。Ex32算例的AGV搬运和工件调度的甘特图如图8所示，最佳调度时间为83。

图7 两种算法对比曲线图

图8 Ex32最佳调度甘特图

选取文献[7]中所提出的改进启发式遗传算法(HGA)、EROL等[11]采用的MAS算法以及CENK等[12]所提出的FMAS算法与本文的变邻域遗传算法结果进行比较，计算了AGV数量R为2、3两种情况下最大加工时间。从表3可以看出本文算法100%的结果优于MAS算法，在两台AGV的情况下83.3%的结果优于HGA算法，在三台AGV搬运情况下75%的结果优于HGA算法，与FMAS算法相比在两台AGV情况下有66.6%的算例求取了最优结果，验证了变邻域遗传算法解决含有AGV搬运FJSP问题的有效性。

表3 算例结果对比表

4 结束语

本文提出一种改进群初始化和编码策略的遗传算法，通过融合移动和交换工序的两级变邻域搜索策略提高了混合算法的局部搜索能力。最后对算例进行实例测试并与其他算法求解的最优结果进行比较，验证了GAVNS混合算法对解决AGV柔性车间调度问题的稳定性、可靠性。后续将对算法进行改进研究并应用到解决多目标约束的柔性离散制造车间调度问题中。