单个AGV小车多个搬运请求的调度算法研究-AGV吧

引言

目前在柔性制造系统中的物流控制系统往往由多个 AGV 小车构成，而在中小型柔性制造系统中，由于加工中心数量少，多个 AGV 小车会增加小车的等待时间，易发生因调度路线重叠而出现小车冲撞的情况。因此，可采用单个 AGV 小车处理多个搬运请求的调度模式。
针对 AGV 小车的车间调度方案，目前国内外许多学者主要通过动态调度的优化算法来搜索 AGV 小车的调度路径的最优值。文献［1］中提出通过机床/AGV 小车约束下的遗传算法，搜索小车的最优值，验证了该算法的可行性。文献［2］提出通过混合启发式算法，最小化小车的最大完工时间。文献［8］基于模糊满意度的遗传算法调度规则，计算总体满意度水平以得到最优值。以上算法能保证搜索到最优值，但求解过程久，搜索范围大，计算规模往往呈指数倍上涨。因此，可在优化算法的基础上引入小车搬运优先级策略，将算法的搜索区域分割成几部分，求解出每一部分的最优值并进行比较，从而使搜索结果更接近最优值。
本文通过分析 AGV 小车的车间调度机制，根据AGV 小车搬运优先级的几种设定对工序进行编码，并设计适应度函数，选择、交叉和变异方法，通过对遗传算法的仿真分析，确定哪种托盘搬运优先级下小车的最大完工时间最短，为单个 AGV 小车的调度问题提供一种有效的解决途径。

1 问题描述和数学模型

柔性制造系统根据生产计划制订如下加工任务:有 n 个工件在台机床上加工，每个工件都有 k 道工序，工件的每道工序都可以在任一机床上进行加工。由此可得出:
( 1) 工件集 N = { n1，n2，···，nn } ，ni ( i = 1，2，···，n) 为第 i 个工件;
( 2) 工序集 P = { p1，p2，···，pn } ，pi = { pi1，pi2，···，pik} ，pi j 为第 i ( i = 1，2，···，n) 个工件的第 j ( j = 1，2，···，k) 道工序;
( 3) 机床集 M = { m1，m2，···，mm } ，mq ( q =1，2，···，n) 为第 q 台机床;在小车调度过程中，应满足如下约束条件:
( 1) 每台机床都只能一次加工一个工件;
( 2) 工序的加工时间为常数;
( 3) 每个工件加工工序的顺序不能改变;
( 4) 小车从上料台取件往机床搬运的时刻为所有工件的起始加工时间;
( 5) 当所有工件加工完成后，小车将所有工件搬至下料台后搬运任务才算结束。
( 6) 小车搬运工件的优先级条件为: ①向加工中心上料的工件; ②加工中心已加工完的工件; ③接近最后工序的工件。按照以上三条件随机组合成 6 种优先级策略。
根据以上优化约束条件，小车调度方案的优化目标为所有工件的最大加工时间最小化，其数学模型为:min{ max ( ci ) } ，i = 1，2，···，n。其中，ci 为工件 ni 的完工时间。