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

贺长征1 宋豫川1 雷 琦1 吕向飞1 刘软香1 陈 进2

1.重庆大学机械传动国家重点实验室,重庆,400030 2.重庆电子工程职业学院,重庆,401331

摘要针对含有AGV的柔性作业车间调度问题,提出基于时间窗和Dijkstra算法的混合遗传算法。建立了AGV/机器的双资源调度数学模型;采用3种解决策略处理多AGV路径规划冲突和碰撞;为了将机器和AGV调度集成考虑,设计了三链式编码结构及AGV编码链的交叉、变异算子,同时在遗传算法的解码操作中将Dijkstra算法与时间窗原理相结合,以精确地为任务小车规划出一条无碰撞无冲突的最短路径;算例对比验证了该算法的可行性、有效性和优越性。

关键词时间窗;Dijkstra算法;遗传算法;自动导引小车(AGV)/机器集成调度

0 引言

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

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

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

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

1 问题描述及数学模型

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

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

假设条件如下:

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

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

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

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

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

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

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

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

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

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

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

(12)不考虑小车充电、故障等问题。

根据以上假设,在建立模型之前,对引入的符号和变量作如下说明和定义:Ji,i∈{1,2,...,n}为工件i;Mk,k∈{1,2,...,m}为机器k;Rv,v∈{1,2,...,w}为小车v;Ci为Ji的完工时间;Pi为Ji的总工序数;Oij为Ji的第j个工序;Sijk为工序Oij在Mk上的开始加工时间;tijk为工序Oij在Mk上的加工时间;Cijk为工序Oij在Mk上的完成时间;Tijv为小车v运送加工工序Oij的运送任务;tkk为小车在Mk和Mk之间行驶时间,若k′=k,则tkk=0;lRv运送加工工序Oij的运送任务空载开始的机器位置;Rv在运送任务Tijv的空载可开始时间;Rv在运送任务Tijv的空载完成时间;STijvRv在运送任务Tijv的负载可开始时间;CTijvRv在运送任务Tijv的负载完成时间;M为一个足够大的正数;

对于优化目标为最大完工时间Cmax最小的含AGV的柔性作业车间调度问题,建立的数学模型如下。

目标函数:

(1)

约束条件:

(2)

Spqk+M(1-βijpqk)≥Cijk

其中,Spqk为工序Opq在机器k上的开始加工时间。∀i,p∈{1,2,…,n},jq∈{1,2,…,Pi},k∈{1,2,…,m},使得

Cijk=Sijk+tijk

(3)

(4)

(5)

(6)

l,∀k′∈{1,2,…,m} j>1

(7)

(8)

Sijk≥max(CTijν,max(Cpqk|pi,∀p=1,2,…,n),

q=1,2,…,Pp)

(9)

式(1)表示模型以工件的最大完工时间最小;式(2)表示工件的一道工序只能选择一台机器加工;式(3)表示工件一旦开始加工不允许中断;式(4)表示一个任务只能选择一台小车;式(5)、式(6)及式(7)表示小车的时间约束,其中式(5)表示一台小车在某一时刻只能运送一个任务,式(6)和式(7)表示小车的空载和负载完成时间大于等于空载和负载开始时间加上各自的运行时间;式(8)和式(9)表示工序与运送任务之间的约束,其中式(8)表示只有工件的前一个工序加工完成并且小车到达后,才能开始该工件下一工序的运送任务,式(9)表示只有工件的本道工序运送任务完成后,才能开始加工本道工序。

由于假设条件工件缓冲区无限大,因此不存在因工件缓冲区不足引起的系统死锁现象。

本文采用网络图表示该问题中工件和运送任务之间的约束关系及可行的集成调度方案,见图1。方框表示小车的运输任务,圆圈表示工件的加工工序,实线箭头表示约束关系,虚线所连接的表示使用的资源,如工序O11,O22,O33都在机器M1上进行加工,运输任务T11,T22,T14,T23,T31,T32都采用AGV1来运送。

图1 多AGV和机器的双资源集成调度析取图
Fig.1 Dual resource integration scheduling disjunctive graph of multi AGV and machine

2 冲突类型及解决策略

在柔性制造系统中,AGV沿着导引路径在车间进行来回穿梭运送工件、物料或托盘等,因此导引路径的布局对AGV来说即为地图。将其抽象成点与边的形式,点表示路口或者机器以及仓库位置,边表示两个节点的可通路段,箭头表示是小车可行驶方向,边上数字表示实际的物理距离或通行时间,见图2。

图2 电子地图
Fig.2 Electronic Map

在进行路径规划时,小车在行进的过程中可能出现的冲突类型,包括以下4种基本冲突类型[15]:路口冲突、相向冲突、节点占用冲突以及赶超冲突。由于前提假设小车是按照固定的行驶速度行驶的,所以不存在赶超冲突。

在多AGV系统中碰撞或冲突的类型是复杂多样的,但大多都是由上述3种基本冲突类型所组成。 要解决多AGV系统冲突问题, 首先要处理好上述3种基本冲突[15]。因此针对以上冲突类型,采用基于速度调节、基于几何路径调节以及基于速度和几何路径相结合调节的3种冲突解决策略[18]。为了能够更优地求解小车行驶的最短的路径,将第三种策略进行量化处理如下:设T1为AGV原冲突路径行驶时间,Δt是采用基于速度调节多花费的时间,T2是通过基于几何路径调节策略新生成路径行驶时间。通过下述公式判断采用何种策略:

T1t>T2

(10)

如果成立则采用新生成路径,否则采用基于速度调节策略。特别地,当采用基于速度调节策略失效时,则采用基于几何路径调节策略。

3 算法描述

这里采用一个实例来描述遗传操作的过程。工件加工信息见表1。

表1 柔性作业车间工件加工及运输信息

Tab.1 The processing and transportation information of flexible job shop

工件1工件2工件3工序123123412机器号1,2,51,32,31,42,41,33,51,21,4,5AGV号1,2,3

3.1 编码

此处采用扩展的基于工序的编码[20],该编码由三部分组成,第一部分为基于工序的编码,第二部分为基于机器的编码,第三部分为AGV小车编码且与工序编码一一对应,基因值表示的是对应工序搬运时所需的AGV号。基于上述实例编码信息见图3,工序编码基因串中的数字表示工件号,出现的次数表示工件的第几道工序,如第一个2表示的工件2的第一道工序,第二个2表示的工件2的第二道工序,以此类推;机器编码基因串中工件1的范围表示的工件1的三道工序依次采用5、1、3号机器进行加工,依此类推;AGV编码基因串中第二位置上数字为3表示工件1的第一道工序采用的AGV小车号为3,依此类推,这种编码方式就可以得到柔性作业车间多AGV和机器双资源调度问题的一个可行解。

图3 三链式染色体编码方式
Fig.3 The coding patterns of three chain chromosomes

3.2 选择操作

选择操作体现了优胜劣汰的思想。选择性过强可能会导致早熟收敛,陷入局部最优;选择性过弱,则会使寻优过程太慢。本文采用因以随机等距方式抽取个体而被认为能相对持久保持多样性的随机遍历选择法。

3.3 交叉操作

交叉操作是模拟生物进化过程中的两个染色体通过交配重组得到新的染色体的过程,在遗传算法中起核心作用。根据所采用的编码的特点,采用两种交叉操作,第一种是IPOX[20]交叉操作,用于基于工序编码;为了保证AGV链交叉后小车的数量不变,AGV链的交叉也采用第一种交叉方式; 设P1和P2表示的调度实例中的两条父代染色体,C1和C2是交叉后产生的两条子代染色体。IPOX交叉过程为:随机将所有工件分为J1和J2两个工件集合,复制P1包含在J1中的工件C1,复制P2包含在J2中的工件到C2,并保留他们的位置,复制P2包含在J2中的工件到C1,复制P1包含子在J1中的工件到C2,并保留他们的顺序,其交叉过程见图4a。第二种是MPX[20]交叉操作,用于基于机器编码部分的交叉。设父代P1和P2交叉产生子代C1和C2。MPX交叉操作的过程为:首先随机产生一个由整数0,1组成与染色体长度相等的集合R,依次在P1和P2中选出与R中的1位置对应的工序,交换它们分配的机器,P1和P2中的其他机器保留到子代,这样产生了子代C1和C2,其过程见图4b。

图4 IPOX与MPX交叉过程示意图
Fig.4 The cross process of IPOX and MPX

3.4 变异操作

变异操作模拟生物进化过程中的变异过程,是为了增加种群的多样性,在一定程度上能避免陷入过早收敛,跳出局部极小。此处采用两种变异操作,第一种是针对基于工序编码的交换变异,即从染色体中随机选择两个位置的基因,然后将它们的位置互换,同时为了保证AGV链变异后小车的数量不变,AGV链的变异也采用交换变异方式。第二种是针对基于机器编码的变异操作,即随机选择一个基于机器编码的基因串上的一个基因,在该工序的加工机器集中随机选取另外一个不同的机器替换掉当前机器。

3.5 解码操作

依据染色体的编码方法可以获得每条染色体中每个基因位的信息,包括工序P、采用的加工机器号Mk,运送工件的AGV号Rv及所在机器位置l以及运送的起始位置节点ST。将获取的信息作为基于时间窗的Dijkstra路径算法的输入条件,由Dijkstra路径算法和时间窗信息结合冲突检测及解决策略,规划出一条无冲突无碰撞的路径,并得到对应的行驶时间。最后由行驶时间和加工时间计算染色体适应度值。具体步骤如下。

(1)将染色体中基于工序编码的基因串转换成对应的工序串。

(2)按照从左到右的顺序,读取工序串中的一个基因,对应的工序为Oij,确定其加工的机器为Mk,加工时间为tijk,得到其紧前工序Oi(j-1)的完工时间Ci(j-1),确定运输小车Rv,所在机器位置l及运送任务空载可开始时间

(3)空载路径规划。依据邻接可达矩阵AdjM,小车号Rv及运送任务空载可开始时间起点l、终点S,由Dijkstra路径算法计算到下一最短路径节点N,执行步骤(6)。

(4)负载路径规划。由基于时间窗的Dijkstra路径算法求出lS的空载可行路径,计算得出小车到达S的空载结束时间比较Ci(j-1)大小关系。若则小车Rv运送任务负载可开始时间STij=Ci(j-1),反之

(5)依据邻接可达矩阵AdjM,小车号Rv及其运送任务负载可开始时间STij,起点S、终点T,由Dijkstra路径算法计算到下一最短路径节点N

(6)路段冲突检测。结合各路段时间窗检测路段是否可行,若可行,执行步骤(7);反之,执行步骤(8)。

(7)更新各路段时间窗,若空载路段判断N是否等于S,则负载路段判断N是否等于T;若等于S,则结束,输出最短路径及各路段时间窗,返回步骤(4);若等于T,则结束,输出最短路径及各路段时间窗,执行步骤(10);否则,继续由Dijkstra路径算法计算到下一最短路径,返回步骤(6)。

(8)路段冲突类型检测。若冲突类型是相向冲突,则采用基于几何路径调节策略。若冲突类型是路口或节点冲突类型,依公式T1t>T2选择冲突解决策略,若成立,选择基于速度调节策略,反之选择基于几何路径调节策略。

(9)判断是否到达终点ST ;若等于S,则结束,输出最短路径及各路段时间窗,返回步骤(4);若等于T,则结束,输出最短路径及各路段时间窗,执行步骤(10);否则,考察次优路段,返回步骤(6)。

(10)由最优路径及加工时间计算得出本道工序的开始运送时间、运送结束时间以及开始加工和完工时间。

(11)重复步骤(2)~步骤(10),直到所有的工序被操作,得到每个工件的每道工序的具体执行的开始加工时间和完成时间的集合,即调度方案。

3.6 算法流程

基于时间窗和Dijkstra算法的混合遗传算法求解柔性作业车间多AGV和机器的集成调度算法的具体流程见图5。

图5 算法流程图
Fig.5 the flow chart of algorithm

4 算法对比分析

由于本文与文献[19]处理的是相同问题,因此采用此文献中的算例在MATLAB 2014a仿真环境平台上对本文算法进行对比验证。算例中的工件、小车以及机器等信息见文献[19],且将文献中的算法及本文算法分别命名为GAMS、ACA和HGA。采用上述所提混合遗传算法,仍以总的完工时间最小为目标对其进行计算,程序运行5次所测结果最优值见表1。本文混合遗传算法的基本参数设置分别为:初始化种群PopSize为30,最大进化代数MaxGen为30,交叉概率Pc为0.7,变异概率Pm为0.05。

表2中算例号0的是文献[19]在算法分析中进行举例验证的算例,空格表示求解用时较长,无法求得结果。特别地,文献中算例3和11的求解结果是不合理的,因为算例3中工件2的总的加工时间是36,工序的总的转移时间17,因此工件2的总的完工时间是53,所以文献中的最大完工时间49和50.2是不合理的;算例11中工件在机器3上的加工时间总和等于95,因此最大完工时间必然大于等于95,所以文献中最大完工时间72.1是不合理的,而本文算法的求解结果更加合理。

表2 不同算法求解算例对比结果

Tab.2 The comparison results of different algorithms

算例号AGV数量/工件数量/机器数量/最大坐标点最大完工时间CmaxGAMSACAPGA02/2/3/(3,3)63636311/2/2/(2,2)7677.25521/3/3/(3,3)9799.45432/2/3/(3,3)4950.25342/3/3/(3,3)7072.75152/4/3/(3,3)6971.35663/4/4/(4,4)8284.66773/5/5/(4,4)115.58783/5/5/(5,5)102.59094/6/4/(4,4)87.585104/7/5/(5,5)115101115/8/3/(3,3)72.197126/10/6/(9,9)164.9151137/15/10/(15,15)292.9267

从表2对比结果中可以看出,当小规模作业车间调度时(如算例1),PGA法得到的结果是和GAMS、ACA两种方法一致的;随着规模的增大,采用本文方法的最大完工时间平均减少15%左右,最大改善是算例2,减少了45%的时间。当规模足够大时,由于可行解的空间太大,所求目标的优劣取决于算法的求解效率。由于文献的算例是中等规模的,所以从对比分析来看,本文算法在求解中等规模的作业车间多AGV和机器的集成调度中相比文献中的算法要优越。因此,可以证明本文算法的可行性、有效性和优越性。

上述算例都是基于非柔性作业车间的,若采用柔性作业车间的算例更能体现出所提算法的优势。因为在柔性作业系统中工件的每道工序都有不同的机器选择,导致小车的路线选择也不同,进而有不同的运送时间,并且各个机器的加工时间不同,结果就是这些不同的组合会有不同的结果,因此,更能从中选择出较优的个体。以下是通过对离散制造企业进行调研处理后的数据:系统中待加工工件有4件,机床设备的数量为8台,其中工件的工序数依次分别为5、4、5、6,每道工序在不同机器上的加工时间不一定相同,具体的加工时间和可选机器见表3,AGV的数量为3台,且任何一辆小车都可为任何一台机床服务。依据电子地图构建出节点间邻接可达矩阵,见表4。表4数据代表了AGV在任意两节点间的行驶时间,其中不在矩阵对角上位置为零值的表示两点不可通行。

表3 工件加工时间表

Tab.3 The processing schedule of workpieces min

零件工序机床1机床2机床3机床4机床5机床6机床7机床8工件116710—————2———57—5—36————7—44——5—7—7—5———4—8—12工件218—5—6———2—5————6—3———6—9—549—10—11———工件315—6—————2—7——7———310————9—74—12—9————5——7———9—工件41———5—7—82—8————6—3——10—11———413————9——5———12———96—13————10—

注:“—”表示不可加工。

表4 小车运输时间表

Tab.4 The transport schedule of AGV min

节点123456789101112131415161718192021222324102000010000000000000000022010000200000000000000003010200003000000000000000400201000010000000000000050001020000100000000000006000020000001000000000000710000002000020000000000080200002010000100000000009003000010200000000000000100001000020100002000000001100001000010200001000000012000001000020000002000000130000002000000000001000001400000001000000100002000015000000000000010300000000160000000002000030000001001700000000001000000300002018000000000002000030000001190000000000001000000100002000000000000002000010100021000000000000000000010200220000000000000001000020102300000000000000002000010124000000000000000001000010

遗传算法的基本参数设置和上文一致,由于柔性作业车间调度的可行解空间范围相对较大,所以增加了初始种群的规模,将初始种群设置为60,进行5次计算,实验获得的最优调度方案甘特图见图6,该生产调度最佳调度周期为89。图7为每辆小车行走路段的时间窗,从图中可以看出在同一路段不存在有多辆小车的时间窗是重叠的,可见算法在多AGV的路径规划方面是有效的。

图6 调度方案的甘特图
Fig.6 The Gantt chart of scheduling scheme

图7 各路段时间窗
Fig.7 The time window of each path section

整个算法的搜索过程见图8,从中可以看出工件的最大完工时间是逐渐减小并收敛的。从求解过程可以看出算法在17代时开始收敛,说明了算法能够有效、快速地获得最优解。可见本文所提算法是可行的,收敛速度较快,并且能够反映出所提出的智能优化算法在求解柔性作业车间多AGV和机器双资源集成调度的优越性。

图8 算法搜索过程曲线
Fig.8 The algorithm search process curve

5 结论

考虑实际车间中工件在不同机器之间的转移存在不确定性的问题,本文设计了三链式的编码结构和提出基于时间窗和Dijkstra的混合遗传算法求解此问题,最后证明了本文所提算法在解决中小规模的柔性作业车间多AGV和机器双资源的集成调度方面的优越性。但是,随着问题规模的增大,该算法求解效率有所下降,因此改进大规模问题的求解效率是今后算法的研究方向。

参考文献

[1] 李岩, 吴智铭, 甘泉. 柔性加工环境中机器和AGV的集成调度[J]. 中国机械工程, 2001, 12(4):447-450.

LI Yan, WU Zhiming, GAN Quan. Integrated Scheduling of Machines and AGVS in Flexible Manufacturing Environment [J].China Mechanical Engineering, 2001, 12(4):447-450.

[2] 柳赛男, 柯映林. 一种解决有AGV小车约束的车间智能调度问题的算法[J]. 中国机械工程, 2007, 18(15):1810-1813.

LIU Sainan, KE Yinglin. An Algorithm for Job Shop Scheduling in Dual Resource Constrained with AGV [J].China Mechanical Engineering,2007,18(15):1810-1813.

[3] ULUSOY G, BILGE Ü. Simultaneous Scheduling of Machines and Automated Guided Vehicles [J]. International Journal of Production Research, 1993, 31(12):2857-2873.

[4] ÜMIT B, ULUSOY G. Time Window Approach to Simultaneous Scheduling of Machines and Material Handling System in an FMS [J]. Operations Research, 1995, 43(6):1058-1070.

[5] ULUSOY G, SIVRIKAYA-SERIFOGLU F, ÜMIT B. A Genetic Algorithm Approach to the Simultaneous Scheduling of Machines and Automated Guided Vehicles [J]. Computers & Operations Research, 1997, 24(4):335-351.

[6] ABDELMAGUID T F, NASSEF A O, KAMAL B A, et al. A Hybrid GA/Heuristic Approach to the Simultaneous Scheduling of Machines and Automated Guided Vehicles [J]. International Journal of Production Research, 2004, 42(2):267-281.

[7] ZENG C, TANG J. Blocking Job Shop Cell Scheduling with Automated Guided Vehicles[C]//Intelligent Control and Automation. Shenyang,2015:438-442.

[8] REDDY B S P, RAO C S P. A Hybrid Multi-objective GA for Simultaneous Scheduling of Machines and AGVs in FMS [J]. The International Journal of Advanced Manufacturing Technology, 2006, 31(5):602-613.

[9] 肖海宁, 楼佩煌, 严伟国,等.柔性作业车间中机床与自动导引车在线调度方法[J]. 农业机械学报, 2013, 44(4):280-286.

XIAO Haining, LOU Peihuang, YAN Weiguo, et al. On-line Scheduling Method for Simultaneous Scheduling of Machines and Automated Guide Vehicles in Flexible Job Shop [J]. Transactions of the Chinese Society for Agricultural Machinery, 2013, 44(4):280-286.

[10] 刘旭, 楼佩煌, 钱晓明,等. 基于改进遗传算法的物料配送多 AGV 调度优化[J]. 机械设计与制造工程, 2015(3):16-21.

LIU Xu, LOU Peihuang, QIAN Xiaoming, et al. Multi AGV Scheduling Optimization of Material Distribution Based on Improved Genetic Algorithm [J]. Mechanical Design and Manufacturing Engineering, 2015(3):16-21.

[11] 赵倩. 生产物流系统规划分析与生产调度技术的研究现状与趋势[J]. 科技创新导报, 2008(9):63-64.

ZHAO Qian. Research Status and Trends of Production Logistics System Planning Analysis and Production Scheduling Technology [J]. Science and Technology Innovation Herald, 2008(9):63-64.

[12] 刘国栋, 曲道奎, 张雷. 多AGV调度系统中的两阶段动态路径规划[J]. 机器人, 2005, 27(3):210-214.

LIU Guodong, QU Daokui, ZHANG Lei. Two-stage Dynamic Path Planning for Multiple AGV Scheduling Systems [J]. Robot, 2005, 27(3): 210-214.

[13] 贺丽娜, 楼佩煌,钱晓明,等. 基于时间窗的自动导引车无碰撞路径规划[J]. 计算机集成制造系统, 2010, 16(12):2630-2634.

HE Lina, LOU Peihuang, QIAN Xiaoming, et al. Conflict-free Automated Guide Vehicles Routing Based on Time Window [J].Computer Integrated Manufacture System,2010,16(12):2630-2634.

[14] 胡彬, 王冰, 王春香,等.一种基于时间窗的自动导引车动态路径规划方法[J]. 上海交通大学学报, 2012, 46(6):967-971.

HU Bin, WANG Bing, WANG Chunxiang, et al. Dynamic Routing of Automated Guided Vehicles Based on Time Window [J].Journal of Shanghai Jiaotong Univesity, 2012, 46(6):967-971.

[15] 孙奇. AGV系统路径规划技术研究[D]. 杭州:浙江大学, 2012.

SUN Qi. Research on Path Planning Technology of AGV System[D].Hangzhou:Zhejiang University,2012.

[16] 冯海双. AGV自动运输系统调度及路径规划的研究[D]. 哈尔滨:哈尔滨工业大学, 2013.

FENG Haishuang. Research on Scheduling and Path Planning of AGV Automatic Transportation System [D]. Harbin : Harbin Institute of Technology, 2013.

[17] 苏霞, 李伟光. FMS中自动导引车路径规划[J]. 机械设计与制造, 2015(1):201-203.

SU Xia, LI Weiguang. Path Planning of AGV in FMS [J]. Machinery Design and Manufacture, 2015(1):201-203.

[18] 刘维民. AGV路径规划与调度系统研究[D]. 广州:华南理工大学, 2016.

LIU Weimin. Research on AGV Path Planning and Scheduling System [D]. Guangzhou:South China University of Technology, 2016.

[19] SAIDI-MEHRABAD M, DEHNAVI-ARANI S, EVAZABADIAN F, et al. An Ant Colony Algorithm (ACA) for Solving the New Integrated Model of Job Shop Scheduling and Conflict-free Routing of AGVS [J]. Computers & Industrial Engineering, 2015, 86(C):2-13.

[20] 张超勇,董星,王晓娟,等.基于改进非支配排序遗传算法的多日标柔性作业车间调度[J].机械工程学报,2010,46(11):156-164.

ZHANG Chaoyong, DONG Xing,WANG Xiaojuan, et al. Improved NSGA Ⅱ for the Multi Objective Flexible Job Shop Scheduling Problem[J].Journal of Mechanical Engineering ,2010,46(11):156-164.

Integrated Scheduling of Multiple AGVs and Machines in Flexible Job Shops

HE Changzheng1 SONG Yuchuan1 LEI Qi1 LYU Xiangfei1 LIU Ruanxiang1 CHEN Jin2

1.State Key Laboratory of Mechanical Transmissions,Chongqing University,Chongqing,400030 2.Chongqing College of Electronic Engineering,Chongqing,401331

Abstract: For the flexible job shop-scheduling problem with AGVs, a hybrid genetic algorithm was proposed based on the time window and Dijkstra algorithm. Firstly, a mathematical model of the dual resource scheduling of AGV/machine was established. Secondly, three solutions were used to deal with conflicts and collisions in multiple AGV path planning. Then in order to take integrated scheduling of machine and AGVs into account, three encoding chain structures and the crossover and mutation operators of AGV coding chain were designed. Meanwhile, the Dijkstra algorithm was combined with the time window principles in the decoding operations of genetic algorithm, which may accurately plan a shortest path without collisions and conflicts for the taskes of AGVs. Finally, the feasibility, effectiveness and superiority of this algorithm were verified by numerical examples.

Key words: time window; Dijkstra algorithm; genetic algorithm;automatic guided vehicle(AGV)/machine integrated scheduling

中图分类号TP273; TH187

DOI:10.3969/j.issn.1004-132X.2019.04.009

开放科学(资源服务)标识码(OSID):

收稿日期2017-12-21

基金项目工信部2016年绿色制造系统集成项目(CCLS-JB-002);国家自然科学基金资助项目(51205429);教育部创新团队发展计划资助项目(IRT_15R64);重庆市教委科学技术研究项目(KJ1503006)

(编辑 王旻玥)

作者简介贺长征,男,1989年生,硕士研究生。研究方向为AGV路径规划、生产调度。E-mail:changzhenghe001@126.com。宋豫川(通信作者),男,1973年生,教授、博士研究生导师。研究方向为智能制造与装备、绿色制造。E-mail:syc@cqu.edu.cn。