柔性制造系统agv调度问题的研究

柔性制造系统agv调度问题的研究

2007年9月12日，agv（自动驾驶指南）采用电池为动力，配备非接触跟踪装置，独立于系统寻找无人驾驶自动交通工具。这是现代物流系统的重要组成部分。AGV可以按照监控系统下达的指令,根据预先设计的程序,依照车载传感器确定的位置信息,沿着规定的行驶路线和停靠位置自动驾驶。它是一种集声、光、电、计算机为一体的简易移动机器人,主要应用于FMS(FlexibleManufacturingSystem)、自动化立体仓库以及其他行业,作为搬运设备使用。在物流设备中,AGV较为贵重,如果AGV使用效率太低,不仅会增加成本,造成资源浪费,而且会降低生产效率,影响企业的服务效率。AGV系统调度合理与否,将直接影响到整个生产系统的成本与效率。AGV系统的调度要考虑AGV的数量、路线、任务紧急程度等诸多方面因素。1agv的执行在柔性制造系统(FMS)中生产机组实现从辅料到成品的加工,AGV完成从立库运送辅料到机组、从机组拾取废料到废料回收站,以及从机组运送空托盘到空托盘回收站。AGV小车的运行路径作为电子地图存放在AGV系统的PLC存储器中,只要给出源位置和目标位置,则会自动生成两点间最短路径。机组发出的每一项请求为需求一台AGV来执行一项任务。每一台AGV执行的任务都是从一个点(源位置)装载货物(如:辅料、废料、空托盘),然后在另一个点(目标位置)卸下(如:辅料送达点、废料回收点、空托盘存放点)。为了降低空载率以提高利用率,一般实现运送辅料—拾取废料—运送辅料的循环,必要时连续执行同一种类任务。在实际生产中,各机组运作各有不同,请求随机产生(如图1所示)。在处理多个请求时,首先应优先紧急请求,其次对于一般请求遵从先进先出的原则(FIFO),即先发出请求的先得到服务。根据一般情形,对此问题作如下约定:(1)各生产机组均设有输入缓冲站(放辅料)、输出缓冲站(放废料和空托盘);(2)AGV执行的任务指令为两种:辅料运送、废料拾取(包括空托盘回送);(3)AGV系统中所有的AGV均以相同的速度行驶;(4)AGV满载和空载时运行速度相同;(5)AGV执行任务时只允许装载一次货物,且所装载的货物将一次性卸完;一个机组发出一项请求时只允许一台AGV来服务,且一台AGV能够满足一项请求。2数学模型2.1源位置至目标位置间的距离i—任务i(请求i需要AGV执行的任务),i=1,2,…,N;N—所涉及的任务总数目;m—AGV的总数目;c—AGV的承载能力;ai—任务i的实际载重量;di—任务i的源位置至目标位置间的距离;dij—任务i的目标位置至任务j的源位置间的距离;xij—任务i后立即执行任务j时值为1,否则为0;xijk—若AGV小车k执行完任务i后立即执行任务j时值为1,否则为0;yik—若任务i由AGV小车k执行时值为1,否则为0;U—不包括任务全集和单一任务子集的任务子集;q—AGV的待命区(一般为充电区);ti1—机组发出请求i的时刻;ti2—若请求i到时刻ti2没得到满足则转化为紧急请求;ti3—若请求i到时刻ti3没得到满足则此机组停产;ui(ti)—任务请求i的满意度。2.2agv不得《提取》第5页,采用ib.当车间只有一台AGV的情形时,我们以总行驶距离最小化为目标建立数学模型。min∑di+∑xijdijs.t.ai<c,i=1‚2‚⋯‚Ν;(1)∑j(≠i)xij=1‚i=1‚2‚⋯‚Ν；(2)∑i(≠j)xij=1‚j=1‚2‚⋯‚Ν；(3)∑i∈Uj∈Uxij≤|U|-1‚(2≤|U|≤Ν-1)‚xij=0或1(i≠j)(4)约束条件(1)式表示AGV不得超载;约束条件(2)式意味着AGV在任务之后立即执行的只有一项任务;约束条件(3)式表明紧接任务j之前仅有一项任务;约束条件式(4)限制一些子路径:若任务j出现在任务i之后,那么禁止任务i在任务j之后。2.3多机多要求的数学模型2.3.1agv的选取①在满足需要的前提下应尽量减少AGV的数量;②请求应及时得到满足,使机组满意度最大化;③应使得整个AGV系统总行驶距离最小化。2.3.2紧急请求的满足机组发出的请求为辅料运送和废料拾取(包括空托盘回送),由于机组生产任务与速度不尽相同,因而机组随机发出任务请求,若请求不能及时得到满足,直到某种程度时则转化为紧急请求;若紧急请求在一定时间内仍然得不到满足,则机组停产,这是由于机组无原料加工或者是废料已填满输出缓冲器而中断生产。满意度函数定义为:ui(ti)={0,ti<ti1ti-ti1ti2-ti1,ti1≤ti≤ti2ti3-titi3-ti2,ti2<ti≤ti30,ti3<ti。2.3.3agv车辆数量的计算minn∑j=1m∑k=1xqjk(5)max1nn∑i=1ui(ti)(6)minm∑k=1n∑i=1n∑j=1dijxijk(7)s.t.ui(ti)>0i=1‚2‚⋯‚Ν(8)ai<ci=1‚2‚⋯‚Ν(9)m∑k=1yik=1i=1‚2‚⋯‚Ν(10)n∑i=1xijk=yjkj=1‚2‚⋯‚Ν;k=1,2,…,m(11)n∑j=1xijk=yjki=1‚2‚⋯‚Ν;k=1,2,…,m(12)∑i,j∈U×Uxijk≤|U|-1k=1‚2‚⋯‚m(13)xijk=0或1,i=1,2,…,N;j=1,2,…,N;k=1,2,…,m;yik=0或1,i=1,2,…,N;k=1,2,…,m;ti≥0;i=1,2,…,N;其中目标(5)式表示最小化AGVS车辆数量;目标(6)式是最大化平均满意度;目标(7)式是最小化总运行距离。约束条件(8)式确保AGV能满足机组的任一请求;约束(9)式确保每台AGV不会超重;约束(10)式确保每个请求只由一台AGV来执行;约束(11)式和约束(12)式对于每一个请求,只有两个请求与之相连,AGV由一个机组直接驶向它,又由它直接驶向另一个机组;约束(13)式描述车辆k直接运行和任务请求数的关系。在此数学模型中存在两个已知的组合优化问题,约束(9)式和(10)式是一般指派问题的约束,若变量满足约束(8)式～(10)式,则对于给定的小车k,(11)式～(13)式定义了一个对请求分配车辆k的旅行商问题。3模型解3.1算法描述这里应用一种混合遗传算法来求解此数学模型。染色体表达方式:机组/服务时间/AGV。3.1.1初始种群聚类由于存在允许服务时间约束,不能直接随机产生初始种群,这里的初始化过程分为三个步骤:ⅰ.随机产生机组排列;ⅱ.用从左向右扫描过程将机组对应于AGV进行聚类;ⅲ.确定每个机组的最优服务时间;3.1.2agv服务时间可行性聚类过程是一个连续地向AGV增加任务请求的过程。当向当前AGV增加新的请求时,必须检查当前AGV执行任务的能力可行性和服务时间可行性。当两者均可行时,新的任务请求即可分给当前AGV,否则,将这个请求分给新的AGV。3.1.3车辆路径计划由聚类过程得到一组染色体,每个染色体代表一个可行的调度。推移过程是使机组的服务时间尽可能靠近它的最满意服务时间,以最大化总满意度。通常,一个可行染色体包括几个AGV路径计划,而一个车辆路径计划则包括一些可推移路径:可通过推移服务时间使之最靠近最满意服务时间。令P表示路径上顺序的机组列表,机组i的可能前推时间Δmin确定如下:Δi={ti2-ti,若ti1<ti<ti2ti3-ti,若ti2<ti<ti3Δmin=mini∈Ρ{Δi}。确定前推时间后进行不可推检查:在已经前推的部分中检查是否违反时间约束或降低满意度,若是则为不可推路径。令u′=∑i∈Ρu′i(ti),当u′>0时,一个可能的前推将带来总满意度的增加;否则,这一前推将导致总满意度下降。3.1.4车辆路径问题上可行的调度ⅰ.用连续插入启发式产生一个能力和服务时间可行的调度,连续插入算法在一系列带时间窗的车辆路径问题上优于其他所有算法。ⅱ.用推移过程确定每个发出请求的机组的最优服务时间。3.1.5染色体适值的计算适值根据原始目标函数计算,一个染色体的目标加权和如下:g(vk)=ρ1uku0max+ρ2(1-1n∑iuki(tki))+ρ3dkd0max‚3∑i=1ρi=1；ρi≥0；i=1,2,3(14)(14)式中,vk是第k个染色体;uk是染色体vk中AGV总数;u0max是初始染色体中AGV最大数;dk是染色体vk的运行总距离;d0max是初始染色体中最大运行距离。于是染色体的适值计算如下:eval(vk)=g(vmax)-g(vk)g(vmax)-g(vmin)。用轮转法作选择机制,并用精选法嵌入其中,以保护下一代中的最好染色体并克服采样的随机误差。其中权系数ρi可由决策者根据各因素的影响程度来定。3.2agv总使用车辆数增加某车间有25个机组,每个机组的请求服务时间随机产生。适值权重的变化(见表2)对最终结果(见表3)产生了不同程度的影响。结果表明,在适值权重设置中,对满意度的强调(情形2,ρ2=0.90)和对总行驶距离的强调(情形3,ρ3=0.90)都将引起AGV总使用车辆数增加。在计算最终输出的染色体中(见表4),确定了请求与AGV的一一对应,并指出了AGV的最优服务时间,如表上位机下达的调派方案为AGV1在时刻执行机组的请求,AGV1在时刻执行机组M2的请求