柔性作业车间多自动导引小车和机器的集成调度-AGV吧

０引言

传统的作业车间调度不考虑工件的转移时间或将其假设成确定的时间值考虑在加工时间内,这不符合作业车间加工的实际情况.实际生产中工件的工序加工完成后,由自动导引小车(AGV)来实现工件在不同机器之间的转移,并且不同小车和不同路径的选择会产生不同的转移时间,进而影响工件的开工时间、整个生产调度周期和产品交货期.因此,考虑含 AGV 的作业车间调度,成为当前研究的热点之一.

目前,国内外学者纷纷对含 AGV 的作业车间调度展开研究,但大多研究割裂了机器调度和AGV 路径规划,分两种情况,一种是假设 AGV路径规划已知,即在调度过程中不考虑路径冲突问题进行 AGV 和机器的同时调度,对此问题大多学者采用的是遗传算法、禁忌搜索等智能优化算法[１Ｇ１０],然而这些学者的研究没有考虑小车碰撞或路径冲突所导致的工件转移时间的不确定性;另一种是先调度好机器加工序列后,再进行AGV 的路径规划[１１],这种情况大多数学者采用的是动态规划的方法[１２Ｇ１８],但这是在已知任务的最优调度序列的情况下进行 AGV 的分配并进行路径规划,可以说上述情况并未实现真正意义上的集成调度,因为该问题中的路径规划对于任务调度结果有一定影响,同时任务的调度也会对AGV 选择及其路径规划产生一定的影响,所以二者是相互影响的.SAIDIＧMEHRABAD 等 [１９]在考虑了二者关系的情况下建立了该问题的数学模型,并提出两阶段蚁群算法来求解,但未考虑零件的可变工艺路径约束.在零件具有可变工艺路径的柔性作业车间中更能体现出工件转移时间的不确定性,因为柔性作业系统中工件的每道工序都有不同的机器选择,导致 AGV 的路线选择也不同,进而有不同的工件转移时间,并且所用机器的加工时间不同,导致这些不同的组合会有不同的结果,这也符合现代多品种小批量的生产方式,因此优化柔性作业车间多 AGV 和机器的集成调度具有重要意义.

小车出现碰撞或冲突的本质是两辆小车在时间和空间上存在完全或部分重叠,所以采用为每个路段设置一个时间窗的方法来解决小车的碰撞或冲突问题.这里时间窗的含义是在该路段的时间窗内不允许存在两辆不同小车同方向完全重叠和相反方向完全或部分重叠的情况,即时间窗具有一定的锁定功能.然而在实际作业车间中关于小车路径规划问题,要求能够准确地为 AGV 规划出一条无碰撞无冲突的最短路径,否则会出现
因多个小车在同一时间段竞争同一路段而产生死锁的现象.在最短路径规划中 Dijkstra算法能够从全局出发,具有较强的稳定性,且算法简单[１３].虽然 Dijkstra算法在地图节点个数和弧数量比较多时求解效率较低,但能够１００％求出最短路径,这符合实际柔性作业车间中多 AGV 路径规划的要求.再者,遗传算法具有以下特点:①不直接表达解空间,采用编码方式表示解空间简化问题的处理难度;②具有快速随机搜索能力和从种群出发进行寻优的隐含并行性;③具有可扩展性,容易与其他算法结合.

综合以上考虑,为了避免割裂机器调度和AGV 路径规划关系并求出在系统中工件转移时间的最优值,实现真正意义上的同步集成调度,将时间窗和 Dijkstra算法相结合进行 AGV 路径规划并嵌入遗传算法的解码操作过程中,提出了基于时间窗和 Dijkstra算法的混合遗传算法求解柔性作业车间多 AGV 和机器的集成调度问题.

１问题描述及数学模型

假设有n 个待加工工件,k 台可用于加工工件的机器,w 台相同的 AGV 在车间运送工件.每个工件有一道或多道工序,每道工序有若干台可选机器对其进行加工,且工序在不同机器上的加工时间不一定相同,取决于机器的加工性能.每台 AGV 可在任意两台机器之间运送工件,小
车的运送路线选择通过实时计算两台机器间的可通路径,运送时间取决于两台机器之间的实际物理距离和路况.

AGV 小车在整个调度系统中存在两种行走状态:一是空载,就是小车从第一台机器 Ml 空载行驶到第二台机器 Mk′ 装载将要在第三台机器Mk 进行加工的工件的过程;二是负载,就是小车从第二台机器 Mk′装载着将要被加工的工件行驶到第三台机器 Mk 的位置的过程.与一般的作业车间调度相比,增加了 AGV 资源的约束条件,即双资源约束的调度问题,使得工件的转移时间值存在不确定性,但每道工序的转移一定会存在最优时间值,因此,调度目标是为每道工序选择最合适的加工机器和搬运小车,尽可能减少小车的空载行程,缩短工件的转移时间,使每道工序尽可能早地开工,最终确定各工件的各道工序的最佳搬运路径、最佳加工顺序和开工、完工时间.

假设条件如下:

(１)任意时刻每台机器只能加工一个工件;

(２)任意时刻每个工件的每道工序只能在一台机器上加工,一旦开始加工不允许中断,装/卸货时间算在加工时间内,加工时间已知;

(３)每台机床的工件缓冲区无限大,但只允许停靠一辆小车;

(４)负载或空载不影响小车的行驶速度;

(５)不同工件之间加工顺序没有约束;

(６)每辆小车每次只能运送一个工件;

(７)所有小车和所有工件都在小车起点和毛坯库;

(８)一道工序被加工完后被空闲 AGV 运送到下一个机器位置进行下一道工序的加工;

(９)小车执行完任务停靠在刚执行完任务的机器旁,并不回到原来的位置;

(１０)路段是双向单通道,同一时刻在每个节点和路段只允许通过一辆小车;

(１１)考虑 AGV 之间的碰撞和冲突等问题;