随着电子计算机和自动化技术的革新,制造业愈加偏向智能化发展.自动导引运输车(AGV)作为柔性制造系统关键设备之一,为系统的智能分配、灵活调度和准确控制提供了快捷、有效的物流输送.
目前,国内外学者对AGV调度问题做了许多研究.Ho等[1]提出了区域分区设计和动态区域控制的路径规划方法,在规避碰撞的同时,实现了AGV在不同区域间的负载平衡.Rezapour等[2]提出了在AGV路径规划过程中,对机床布局以循环的方式重新设计,使得AGV调度路径最短.侯玲娟等[3]针对不确定需求和时间下的车辆路径随机问题,提出了一种带有自适应机制的规划模型.胡彬等[4]针对柔性制造系统多AGV路径规划问题,提出了一种基于时间窗的动态路径规划算法,有效避免了AGV间的冲突问题.贺丽娜等[5]结合预先规划算法和实时规划算法,提出了基于先验决策的路径规划方法,有效避免了锁死及碰撞问题.Guan等[6]提出了一种改进的类电磁机制,对可重构系统下的单向AGV系统调度路径进行了优化设计.Caridá等[7]将分层模糊规则模型和自适应遗传模糊控制2种方法应用于AGV调度过程中,有效提升了调度系统的敏感度.Fauadi等[8]关注于多AGV运输任务的动态分配,提出了一种先进的组合拍卖方法以调解AGV任务分配过程.Zheng等[9]提出了一种基于tabu方法的启发式算法,以完工时间最短为目标,优化柔性制造系统中机床操作的加工顺序与AGV路径.Digani等[10]以双层控制构型和路线定义自动算法为依据,提出了一种整体协调方法,使系统的柔性和全局效率得到了提升.Umar等[11]提出了一种混合遗传算法,采用自适应权重方法有效优化了完工时间、调度时间与物流成本.
上述文献的研究重点多针对固定加工方案下的AGV调度问题,而对于由具备完整加工能力的柔性加工设备组成的加工单元而言,可实现同族不同产品的混流加工.在这种情况下,由于不同产品的加工工时、批量需求的差异以及上下料点与不同柔性加工设备间物理位置的差异,使得各设备间加工任务的合理配置存在较大意义.本文针对多品种混流柔性加工单元中柔性设备的加工任务分配方式和AGV数量对调度的影响,对多AGV调度优化问题进行了研究,建立了多AGV调度的数学模型,基于改进的Memetic算法对模型有效求解,得到不同AGV数量下机床加工任务的最优分配方案和AGV最优调度路径.
1 问题描述在一个多品种混流柔性加工单元(FMC)中有d种工件共i个需在m台柔性机床上进行加工.每种工件所需加工工时不同,加工需求数量亦不同.机床按照一定的布局方式分布在线上,每台机床具备完整加工能力,任务开始前各台机床的加工任务未定,均可选择一种工件进行加工.AGV作为物料输送设备,但数量未定.AGV搬运任务分为上料和下料.上料搬运任务指AGV从当前位置移至上料区取料(如当前位置为上料区,直接取料),按工件类型运至目标机床上料;下料搬运任务指AGV从当前位置移至工件所在机床取料,运至下料区下料,如图 1所示.上、下料点在不同机床间物理位置上存在差异,AGV上下料时脱离主运行轨道停靠,以避免对后续AGV的影响.当AGV和机床处于空载状态时,将上料区的所有搬运任务作为一个任务集进行调度,针对各机床加工任务不同的分配方案和AGV数量,将任务集内所有搬运任务按一定次序分配给各台AGV,AGV按分配结果执行任务.
基于实际问题和研究必要性,作出如下假设:
(1) 上、下料区和机床之间的节点位置关系以及AGV节点间行走所需时间已经确定.
(2) 各类型工件所需加工时间已经确定.
(3) 每台机床只负责一种类型工件的加工,每次只能加工一个工件.
(4) 机床的缓冲区容量不影响AGV调度.
(5) 所有工件初始位置在上料区.
(6) 对机床输入/输出缓存区采用先进先出(FIFO)管理规则.
(7) 每辆AGV初始位置在上料区,AGV完成搬运任务后,直接前往下一任务所在目标机床.
(8) AGV可执行任一搬运任务.
(9) AGV在搬运过程中不会发生干涉和碰撞.
该柔性加工单元的优化目标为任务集内AGV完成搬运任务的时间最短.
2 数学模型为便于问题描述,针对图 1对相关符号进行说明,如表 1所示.
约束模型构建如下:
$ \sum\limits_{i = 1}^{{P_i}} {{\delta _{kis}}} \le 1, \;\;\;\;\forall k, s $ | (1) |
$ \sum\limits_{d = 1}^{{P_d}} {{\beta _{md}}} \le 1, \;\;\;\;\forall m $ | (2) |
$ {T_{{\rm{b}}kis}} + {T_{kis}} \ge {T_{{\rm{e}}im}}, \;\;\;\;\forall m, i, k, s $ | (3) |
$ {K_{k0}} = {m_0}, \;\;\;\;\forall k $ | (4) |
$ {T_{{\rm{b}}im}} \ge {T_{{\rm{b}}kis}} + {T_{\left( {{K_{ks}}, {m_0}} \right)}} + {T_{\left( {{m_0}, {N_{im}}} \right)}}, \;\;\;\;\forall m, i, k, s $ | (5) |
$ {T_{{\rm{e}}kis}} - {T_{{\rm{b}}kis}} = {\delta _{kis}}{T_{ks}}, \;\;\;\;\forall i, k, s $ | (6) |
$ {T_{{\rm{e}}im}} = {T_{{\rm{b}}im}} + {T_{im}}, \;\;\;\;\forall i, m $ | (7) |
其中,
$ {\delta _{kis}} = \left\{ \begin{array}{l} 1, \;\;\;\;\;\;{\rm{工件}}i{\rm{是第}}k{\rm{台}}\;{\rm{AGV}}\\ \;\;\;\;\;\;\;\;{\rm{的第}}s{\rm{个任务}}\\ 0, \;\;\;\;\;\;{\rm{其他}} \end{array} \right. $ |
$ {\beta _{md}} = \left\{ \begin{array}{l} 1, \;\;\;\;\;\;{\rm{工件种类}}d{\rm{在机床}}m{\rm{上加工}}\\ 0, \;\;\;\;\;\;{\rm{其他}} \end{array} \right. $ |
式(1)表示每辆AGV每次只完成一个工件的搬运任务;式(2)表示每台机床只能加工一种工件;式(3)表示下料时,AGV必须在工件加工完成后装载工件;式(4)表示AGV的初始位置是上料区;式(5)表示工件在AGV完成上料搬运任务后开始加工;式(6)表示AGV搬运任务结束时间是开始时间加上搬运时间;式(7)表示工件完工时间等于开始时间加上加工时间.
采用机床约束矩阵RM×N=(rvu)来为每台机床分配加工任务.其中,M=APmPm,表示方案数量;N=Pm,表示机床数量;v=1, 2, …, M,表示方案编号;u=1, 2, …, N,表示机床编号.矩阵每1行表示一种分配方案,如Pm=4, v=3,矩阵R第3行为[r31 r32 r33 r34]=[3 1 4 2],表示第3种分配方案中机床1加工工件类型3,机床2加工工件类型1,机床3加工工件类型4,机床4加工工件类型2.如此,可得到机床约束矩阵
$ \mathit{\boldsymbol{R}} = \left\{ {\begin{array}{*{20}{c}} {{r_{11}}}& \cdots &{{r_{1N}}}\\ \vdots &{}& \vdots \\ {{r_{M1}}}& \cdots &{{r_{MN}}} \end{array}} \right\} $ |
需要注意的是,当Pd=Pm时,即每种工件由且仅由一台机床加工,矩阵R中不会出现相同的行矩阵;当Pd<Pm时,即部分类型工件会由多台机床加工,矩阵R会出现重复.因此,实际生产中,矩阵R应根据工厂实际要求对约束进行调整.
根据以上约束模型,目标函数构建如下:
$ \min \left\{ {\mathop {\max }\limits_{\begin{array}{*{20}{c}} {1 \le k \le {P_k}}\\ {1 \le s \le {P_s}} \end{array}} \left\{ {\sum\limits_{i = 1}^{{P_i}} {{\delta _{kis}}{T_{ks}}} } \right\}} \right\} $ |
最小化AGV完成各自搬运任务时间最大值,即完成任务集内所有搬运任务的总时间最短.根据AGV搬运任务的不同,Tks的计算分为上料与下料2种工况.当AGV的搬运任务为上料时,搬运时间是AGV从当前位置移至上料区取料的时间加上从上料区移至目标机床的时间,如下所示.
$ {\delta _{kis}}{T_{ks}} = {T_{\left( {{K_{ks}}, {m_0}} \right)}} + {T_{\left( {{m_0}, {N_{im}}} \right)}}, \;\;\;\;\forall i, k, s{\rm{且}}{\eta _{ks}} = 1 $ |
当AGV的搬运任务是下料时,如果工件已完工,搬运时间是AGV从当前位置移至目标机床的时间加上从目标机床移至下料区的时间.如果工件未完工,搬运时间是工件的完工时间加上从目标机床运至下料区的时间,如下所示:
$ \begin{array}{l} {\delta _{kis}}{T_{ks}} = {T_{\left( {{K_{ks}}, {I_{kis}}} \right)}} + {T_{\left( {{I_{kis}}, {m_1}} \right)}}, \;\;\;\;\forall i, k, s{\rm{且}}{\eta _{ks}} = 0, \\ \;\;\;\;\;\;{C_{mi}} = 1 \end{array} $ |
$ {\delta _{kis}}{T_{ks}} = {T_{{\rm{e}}im}} + {T_{\left( {{I_{kis}}, {m_1}} \right)}}, \;\forall i, k, s{\rm{且}}{\eta _{ks}} = 0, {C_{mi}} = 0 $ |
$ {\eta _{ks}} = \left\{ \begin{array}{l} 1, {\rm{第}}k{\rm{台AGV第}}s{\rm{个任务为上料任务}}\\ 0, {\rm{第}}k{\rm{台AGV第}}s{\rm{个任务为下料任务}} \end{array} \right. $ |
$ {C_{mi}} = \left\{ \begin{array}{l} 1, {\rm{工件}}i{\rm{已在加工单元}}m{\rm{上加工完成}}\\ 0, {\rm{工件}}i{\rm{未在加工单元}}m{\rm{上加工完成}} \end{array} \right. $ |
Memetic算法[12-14]是一种将遗传算法和局部搜索相结合的新型智能算法,基于遗传算法的全局搜索过程中对单个个体进行局部搜索,保证迭代过程中所有个体均可到达局部最优,提高了算法的求解效率.
3.1 构造个体考虑到机床加工任务分配和AGV数量对调度的影响,个体编码采用多参数编码方式.个体由多个基因片段组成,每个基因片段由3位数组成,第1位代表AGV编号,第2位代表机床编号,第3位代表工件编号,表示第k台AGV本次的搬运任务是将第i个工件送至第m台机床.这种编码方式可清楚表达机床加工任务分配信息和AGV搬运任务信息,便于计算机解码.需要注意的是,因第3位为工件编号,每个工件包含上料任务和下料任务各1次,所以含有相同工件编号的基因片段需出现2次,个体所含基因片段数为2Pi个.个体编码为“123246375”时,含义如图 2所示.
按照上述编码方式以基因片段为单位对个体进行解码,解读出AGV任务分配方案和AGV搬运路径.通过数学模型求解AGV调度过程,记录AGV每个搬运任务的完成时间、每个工件的开工时间节点和完工时间节点,并获得工件集内所有搬运任务的完成时间为个体的目标函数值,即评估值value,代表每个个体的优劣程度.
3.2 遗传算子(1) 选择算子
考虑到本算法在初代种群生成过程中存在一定随机性,如采用传统的轮盘赌方法进行算子选择,会存在2个问题:一是在进化前期,value值高的个体被选中概率过高,导致子代继承过多,子代个体单一,从而使搜索陷入局部搜索;二是在进化后期,个体value值差距较小,无法做到有效选择.因此,在进行轮盘赌之前,将个体的value值由小到大排序,获得个体排序序号l,按式(8)计算个体的适应度值fitness(j).通过式(9)计算出个体的cFitness(j),作为其进行轮盘赌时被选中的概率上限,如下所示:
$ {\rm{fitness}}\left( j \right) = a{\left( {1 - a} \right)^{l - 1}}, \;\;\;a \in \left( {0, 1} \right) $ | (8) |
$ {\rm{cFitness}}\left( j \right) = \frac{{\sum\limits_{j = 1}^l {{\rm{fitness}}\left( j \right)} }}{C} $ | (9) |
式中:
采取此方法,个体被选中的概率只取决于它在种群中的排位l与参数值a的大小,个体与其他个体value值的绝对差值大小并不影响到其遗传到子代的数量,从而在一定程度上避免了上述2种情况.其中,a的取值影响个体被选取的概率,a越趋向于0,排位相近的2个个体被选中的概率越接近,value值低的个体越不易被淘汰,算法越不易陷入局部搜索.反之,a越趋向于1,不同排位的个体被选中的概率差异性越大,value值高的个体易被选中,算法收敛速度加快.在本文案例中取a=0.6.
(2) 交叉算子
考虑到编码方式的特殊性(第3位上工件编号具有唯一性),个体如按传统遗传算法(GA)的交叉方式会生成非法解,需对个体交叉重组后对其进行修正,方法如下:提取个体g1、g2对应位置上的基因片段b1、b2,根据b1、b2的第3位(工件编号)i1、i2选择修正方法.如i1=i2,将g1中工件编号为i1的基因片段的第2位改为b2的第2位,g2的修正方法与g1相同;如i1≠i2,将g1中工件编号为i1的基因片段的第2位改为b2的第2位,将g1中2个工件编号为i2的基因片段的后2位改为b1的后2位,g2的修正方法与g1相同.修正方法如图 3、4所示.经过改进的交叉方式不会产生非法解,有利于提升可行解的搜索效率,增加AGV任务分配方案的多样性.
采用爬山算法实现局部搜索,搜索机制如下:
在算法中对于每一个个体,随机生成2个[1, 2Pi]之间不等的整数,取这2个数位上的基因片段相互交换,产生邻域范围解,如图 5所示.通过多次搜索,计算每次交换前后个体的评估值value,选出值最小的个体作为局部搜索后的最优个体.
步骤1 设置相关参数:种群大小popSize,各类型工件数表patternNum,执行局部搜索的次数searchNum,最大迭代次数MaxIter,交叉概率Pc,最大AGV数量AGVmax,各类型工件生产节拍表MAproctime,AGV各节点间行驶时间表AGVtimtable,机床约束矩阵R.
步骤2 取AGV数量AGVNum=1,机床加工任务分配方案编号S=1,分配方案数ST为矩阵R行数,迭代次数y1=1.
步骤3 令Relation=R(S, :),根据Relation中约束关系对各机床加工任务进行分配.按本文个体编码方式,将patternNum中各类型工件按Relation中约束关系选择对应目标机床,分配给AGVNum台AGV,以此生成初始种群.
步骤4 计算个体的评估值value(j).
步骤5 计算个体的适应度值cFitness(j),采用轮赌法进行算子选择.
步骤6 交叉算子:以概率Pc对随机选取的2个个体进行交叉,按本文修正方法对交叉后的个体进行修正.
步骤7 局部搜索:采用爬山算法对每个个体进行searchNum次局部搜索,选出个体较优解,将适应度最高的个体作为当前个体最优解.
步骤8 选出父代和子代中适应度值最高的个体作为最优个体Best.
步骤9 若y1<MaxIter,则令y1=y1+1,转步骤4,否则转步骤10.
步骤10 若y1=MaxIter且S<ST,则令y1=1, S=S+1,转步骤3,否则令BestAGVNum=Best, 放入最优解集,转步骤11.
步骤11 若AGVNum<AGVmax,则令y1=1, S=1, AGVNum=AGVNum+1,转步骤3,否则终止循环,转步骤12.
步骤12 将最优解集{Best1, Best2, …, BestAGVmax}进行解码.求得各AGV数量下调度时间Tmax、各台AGV调度行走路径及工件搬运次序.
4 实例分析 4.1 实例描述本文以某柴油发动机企业混流柔性精加工岛为例,需对其进行机床加工任务分配、AGV任务分配和路径优化.如图 6所示,该精加工岛有一个上料区、一个下料区和一个工件加工区.工件加工区共有8台加工中心,每台加工中心都可以加工任一类型产品.区域被分为4个子区域,每个子区域有2台机床和1台机械手,机床编号分别为1, 2, …, 8,上料区编号为0,下料区编号为9.工件从上料区0上料,运至子区域由机械手送入机床加工,加工完成后运至下料区9下料.4个子区域分别负责对4种不同型号的工件进行加工,工件类型编号分别为A、B、C、D.纵向相邻的2台机床加工同一型号工件,由一名工人负责这2台机床的操作.每种工件的加工数量已定,所需加工时间各不相同,每台机床的加工任务和AGV数量未定.各型号工件所需加工时间和加工数量如表 2所示,机床和上、下料区任意2个节点之间的AGV行驶时间如表 3所示,且为最小路径.
为验证本文算法的可行性,以及与标准Memetic算法和遗传算法对比,在控制参数的选择上,参考文献[13]中的取值,交叉概率Pc=0.6.由于搜索空间较大,在局部搜索参数searchNum的取值上,取高于文献[13]中的取值,以保证解空间的多样性,避免陷入未成熟收敛,取searchNum=100.种群规模popSize=20,最大迭代次数MaxIter=400.应企业成本控制要求,精加工岛AGV数量控制在4台之内,AGVmax=4.取工件数表patternNum=36,依照企业实际生产计划,将各类型工件数表patternNum、各类型工件生产节拍表MAproctime、AGV各节点间行驶时间表AGVtimtable作为约束条件按表 2和表 3输入参数.
考虑到该精加工岛布局和生产要求,纵向相邻2台机床加工同一型号工件,故机床加工任务分配方案数M=A44=24种,机床数量N=8,矩阵R按式(9)约束关系输入,求解过程中各台机床加工任务按矩阵R进行分配,见式(16).如取矩阵R第2行[r21 r22 r23 r24 r25 r26 r27 r28]=[A A B B D D C C],表示第2种分配方案中机床1、2加工工件类型A,机床3、4加工工件类型B,机床5、6加工工件类型D,机床7、8加工工件类型C.
$ \mathit{\boldsymbol{R}} = \left( {\begin{array}{*{20}{c}} {\rm{A}}&{\rm{A}}&{\rm{B}}&{\rm{B}}&{\rm{C}}&{\rm{C}}&{\rm{D}}&{\rm{D}}\\ {\rm{A}}&{\rm{A}}&{\rm{B}}&{\rm{B}}&{\rm{D}}&{\rm{D}}&{\rm{C}}&{\rm{C}}\\ {\rm{A}}&{\rm{A}}&{\rm{C}}&{\rm{C}}&{\rm{B}}&{\rm{B}}&{\rm{D}}&{\rm{D}}\\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ {\rm{D}}&{\rm{D}}&{\rm{B}}&{\rm{B}}&{\rm{C}}&{\rm{C}}&{\rm{A}}&{\rm{A}}\\ {\rm{D}}&{\rm{D}}&{\rm{C}}&{\rm{C}}&{\rm{A}}&{\rm{A}}&{\rm{B}}&{\rm{B}}\\ {\rm{D}}&{\rm{D}}&{\rm{C}}&{\rm{C}}&{\rm{B}}&{\rm{B}}&{\rm{A}}&{\rm{A}} \end{array}} \right) $ | (16) |
根据此案例中AGV调度机制,针对每种机床加工任务分配方案,将AGV完成任务集内所有搬运任务的调度时间Tmax作为目标函数值,即算法中个体评估值value越小,说明这种AGV调度方式越优越,该个体被选择到下一代的概率也就越大.
本案例中,AGV的调度算法中个体评估值value的求解步骤如下:
步骤1 判断搬运任务为上料还是下料,如为上料任务,执行步骤2,如为下料任务,执行步骤6.
步骤2 如为上料任务,上料任务所需时间的计算公式为Tks=T(Kks, m0)+T(m0, Nim). AGV本次搬运任务完成时间,即下次搬运任务的开始时间Tekis=Tks+Tbkis.
步骤3 判断目标机床是否空闲.如空闲,执行步骤4;如不空闲,执行步骤5.
步骤4 如空闲,目标工件的开始加工时间为AGV搬运该目标工件任务的结束时间,将其加上该目标工件在机床上的加工时间即为目标工件的完工时间,Tbim=Tekis+Tim.
步骤5 如不空闲,目标工件的开始加工时间为目标机床的开始空闲时间,将其加上该目标工件在机床上的加工时间即为目标工件的完工时间,Tbim=Tbm+Tim.
步骤6 如为下料任务,AGV移至目标机床的时间Tks=T(Kks, Ikis).
步骤7 比较Tks与Teim大小,判断目标工件是否加工完成.如Tks≥Teim,则完工,执行步骤8;如Tks<Teim,则未完工,执行步骤9.
步骤8 下料任务所需时间的计算公式为Tks=Tks+T(Ikis, m1).AGV本次搬运任务完成时间,即下次搬运任务的开始时间Tekis=Tks+Tbkis.
步骤9 下料任务所需时间的计算公式为Tks=Teim+T(Ikis, m1).AGV本次搬运任务完成时间,即下次搬运任务的开始时间Tekis=Tks+Tbkis.
步骤10 通过累积,可得出每台AGV最后一次搬运任务(下料任务)的完成时间Tks.此时,Tks即为每台AGV完成各自所有搬运任务需要的时间,取其中的时间最大值作为该个体的AGV调度时间Tmax,即value值.
4.3 结果分析本文选用计算机的硬件参数为Intel i7处理器、4GB内存,通过Matlab R2010b软件进行算法运算,对AGV调度机制进行优化,运算过程耗时近12 h,得到不同AGV数量及不同机床加工任务分配方案下目标函数值及其收敛情况.不同AGV数量下各机床加工任务分配方案的目标函数值波动曲线如图 8所示.因各产品加工时间不同、数量不同,不同分配方案下AGV路径有较大的浮动.
图 7a为在由1台AGV完成任务集内所有搬运任务的情况下,24种不同机床加工任务分配方案对最终所需调度时间Tmax的影响.图 7b~d分别为由2台、3台、4台AGV完成搬运任务时,分配方案对Tmax的影响.由图可知,当同一条波动曲线中目标函数值(即调度时间Tmax)越小时,代表该机床加工任务分配方案越合理,调度效率越高.反之,目标函数值越大时,代表该分配方案下,完成AGVnum所有搬运任务所需花费的时间越长,调度效率越低.
取图 7中4条曲线的峰值和谷值所对应的机床加工任务分配方案编号作为各AGV数量下机床加工任务最优和最劣方案.由图 7a中可以看出,采用1台AGV进行调度时,当采取第4种机床加工任务分配方案时,即取矩阵R第4行[r41 r42 r43 r44 r45 r46 r47 r48]=[A A C C D D B B]时,目函数值最小,AGV调度效率最高;当采取第21种分配方案时,即取矩阵R第21行[r211 r212 r213 r214 r215 r216 r217 r218]=[D D B B A A C C]时,目标函数值最大,AGV调度效率最低.采用2、3、4台AGV进行调度时的最优、最劣方案一样可从其他3条曲线得出.
从图 7中亦可发现,为满足不同任务分配下的调度,AGV并不能每次达到最优完工时间和路径最短的要求.在混流生产中企业需要根据计算在选取一定数量AGV的机床上采用一定的分配任务.
单纯考虑AGV数量时,不同AGV数量下机床最优、最劣分配方案的目标函数值如图 8所示,目标函数值随AGV数量变化的趋势如图 9所示.
由图 8可知,AGV数量相等的情况下,不同的机床加工任务分配方案会对目标函数值造成较大的影响,最优方案相较于最劣方案可提升AGV调度效率近10%.可见,在混流柔性加工单元AGV调度过程中,根据不同类型工件的来料数量和加工时间分配各台机床的加工任务对提升AGV调度效率有着重要意义.
从图 9中可以看出,随着AGV数量的增加,目标函数值的变化幅度越来越小,即AGV数量对同一任务集调度效率的增幅随AGV数量的增加而减小.因此,考虑到AGV的高成本,在满足生产节拍要求的情况下可选择较少AGV数量,最终根据工厂实际情况选择3台AGV进行物料运输.由图 7可知,AGV数量为3台时,当采取机床约束矩阵R中第4种分配方案[r41 r42 r43 r44 r45 r46 r47 r48]=[A A C C D D B B],即机床1、2加工工件类型A,机床3、4加工工件类型C,机床5、6加工工件类型D,机床7、8加工工件类型B时,AGV调度时间最短,其最优解由表 4给出.
图 10给出了3台AGV数量下,改进Memetric算法与标准遗传算法、标准Memetic算法迭代收敛情况的对比,结果表明改进算法收敛速度更快,所得最优解也相对更好.
本文研究了多品种混流生产柔性加工单元多AGV任务分配和调度问题.基于柔性加工单元机床加工任务可分配的特点,提出了在AGV调度优化过程中考虑机床加工任务的不同分配方案和AGV数量的影响,设计了改进Memetic算法,并以8台机床的柔性精加工单元为例进行详细分析和求解,验证了该方法的有效性,这对该类加工单元的调度具有较好的借鉴意义.
[1] |
HO Y C, LIAO T W. Zone design and control for vehicle collision prevention and load balancing in a zone control AGV system[J]. Computer and Industrial Engineering, 2009, 56(1): 417 DOI:10.1016/j.cie.2008.07.007 |
[2] |
REZAPOUR S, FARAHANI R Z, MIANDOABCHI E. A machine-to-loop assignment and layout design methodology for tandem AGV systems with single-load vehicles[J]. International Journal of Production Research, 2011, 49(12): 3605 DOI:10.1080/00207543.2010.489056 |
[3] |
侯玲娟, 周泓, 梁春华. 不确定需求和旅行时间下的车辆路径问题[J]. 计算机集成制造系统, 2011, 17(1): 101 HOU Lingjuan, ZHOU Hong, LIANG Chunhua. Vehicle routing problem with uncertain demand and travel time[J]. Computer Integrated Manufacturing Systems, 2011, 17(1): 101 |
[4] |
胡彬, 王冰, 王春香, 等. 一种基于时间窗的自动导引车动态路径规划方法[J]. 上海交通大学学报, 2012, 46(6): 967 HU Bin, WANG Bing, WANG Chunxiang, et al. Dynamic routing of automated guided vehicles based on time window[J]. Journal of Shanghai Jiaotong University, 2012, 46(6): 967 |
[5] |
贺丽娜, 楼佩煌, 钱晓明, 等. 基于时间窗的自动导引车无碰撞路径规划[J]. 计算机集成制造系统, 2010, 16(12): 2630 HE Lina, LOU Peihuang, QIAN Xiaoming, et al. Conflict-free automated guided vehicles routing based on time window[J]. Computer Integrated Manufacturing Systems, 2010, 16(12): 2630 |
[6] |
GUAN Xianping, DAI Xianzhong, LI Jun. Revised electromagnetism-like mechanism for flow path design of unidirectional AGV systems[J]. International Journal of Production Research, 2011, 49(2): 401 DOI:10.1080/00207540903490155 |
[7] |
CARIDÁ V F, MORANDIN O, Jr., TUMA C C M. Approaches of fuzzy systems applied to an AGV dispatching system in a FMS[J]. International Journal of Advanced Manufacturing Technology, 2015, 79(1): 615 |
[8] |
FAUADI M H F, YAHAYA S H, MURATA T, et al. Intelligent combinatorial auctions of decentralized task assignment for AGV with multiple loading capacity[J]. Ieej Transactions on Electrical & Electronic Engineering, 2013, 8(4): 371 |
[9] |
ZHENG Y, XIAO Y, SEO Y. A tabu search algorithm for simultaneous machine/AGV scheduling problem[J]. International Journal of Production Research, 2014, 52(19): 5748 DOI:10.1080/00207543.2014.910628 |
[10] |
DIGANI V, SABATTINI L, SECCHI C, et al. Ensemble coordination approach in multi-AGV systems applied to industrial warehouses[J]. IEEE Transactions on Automation Science & Engineering, 2015, 12(3): 922 |
[11] |
UMAR U A, ARIFFIN M K A, ISMAIL N, et al. Hybrid multiobjective genetic algorithms for integrated dynamic scheduling and routing of jobs and automated-guided vehicle (AGV) in flexible manufacturing systems (FMS) environment[J]. International Journal of Advanced Manufacturing Technology, 2015, 81(9/10/11/12): 2123 |
[12] |
NERI F, COTTA C. Memetic algorithms and Memetic computing optimization: a literature review[J]. Swarm & Evolutionary Computation, 2012, 2: 1 |
[13] |
杨淑莹, 张桦. 群体智能与仿生计算: Matlab技术实现[M]. 北京: 电子工业出版社, 2012 YANG Shuying, ZHANG Hua. Swarm intelligence and bio-inspired computation: implementation with Matlab[M]. Beijing: Electronic Industry Press, 2012 |
[14] |
朱琳, 范秀敏, 何其昌. 柔性生产系统配料区多自动导航小车调度优化[J]. 计算机集成制造系统, 2012, 18(6): 1168 ZHU Ling, FAN Xiumin, HE Qichang. Scheduling optimization for multi-AGVs in batching area of flexible production system[J]. Computer Integrated Manufacturing Systems, 2012, 18(6): 1168 |