基于滚动时域的整体式自动物料搬运系统避碰调度方法

周炳海，周 琪，王 腾

（同济大学 机械与能源工程学院，上海 201804）

0 引言

半导体制造整体式布局中的Interbay与Intrabay轨道直接相连，导致多环耦合效应，从而引起高空穿梭车（Overhead Hoist Transporter，OHT）的运输路径极其迂回，并容易在局部区域高度重叠；另外，实际生产中的制造系统往往存在机器故障、来料延迟、紧急插单等不确定因素。因此，亟需实时动态的派工调度和路径规划策略来保障OHT 在轨道上无冲突运行，维护制造系统运行的稳定和安全。

传统的自动导向小车（Automated Guided Vehicle，AGV）避碰策略主要以区域控制策略为主，将轨道分为若干个不重叠的固定区域，车辆只在所属区域上运行，在避免路径冲突的同时极易造成不同区域间AGV 的工作负荷差异，形成制造瓶颈，对此Ho等［1］设计了动态区域控制策略，以模拟退火算法修正根据工作站间距离和物料流动关系划分的初始区域，但区域规划的分治思想并不适用于多环耦合，且具有多重入和关键工序集中等复杂特性的晶圆加工领域。近年来，时间窗及其相关理论被广泛应用于路径规划领域以避免冲突现象，Smolic-Rocak等［2］提出基于时间窗的动态路径规划方法，该方法简单易行并具有广泛的适用性，但无法有效应对系统不确定因素导致的运行延误问题；Maza等［3］在双向行驶的AGV 系统中结合提前预规划路径和实时避碰的思想，确保任意时刻各节点和路径上最多只有一辆AGV 占用，但其避碰策略过于保守，会大大降低物料搬运系统的运行效率。

除此之外，新兴的人工智能技术和分布式算法在路径规划上的作用也越来越被重视。Srivastava等［4］采用多智能体技术，由智能体分别承担AGV控制运行中的路径生成、时间计算、冲突和死锁检测等功能，以多智能体之间的协商通信机制完成无冲突路径的规划；Erol等［5］采用多智能体系统，使用协商和报价机制在实时环境下产生可行路径；Nishi等［6］在不确定移动延迟情况的条件下提出分布式的路径规划方法，在产生初始路径后进行数据交换，以确定是否有冲突，并在目标函数中考虑由路径冲突约束带来的惩罚。针对特定对象设计的启发式算法也有着优异的避碰表现，Ghasemzadeh等［7］针对网格型布局工厂提出AGV 的无冲突路径规划方法，其开发的启发式算法能有效预测和预防冲突。上述文献都采用了提前规划的静态调度思想，虽然能够有效求得当前时刻的全局无冲突路径，但是忽略了系统实际运行结果与规划的差异，没有对路径冲突进行实时动态的检测和避碰。Nelson等［8］最早提出动态调度的概念，通过将动态调度过程划分为多个连续静态区间，在每个区间内进行相应优化以达到局部最优，从而适应动态生产环境的变化；Sourirajan等［9］使用滚动时域调度策略，在半导体制造系统中根据车间实时状态信息求解了晶圆加工调度子问题。

传统的调度方法往往不考虑多OHT 之间的相互影响以及设备宕机引起的搬运延迟等因素。本文采用滚动时域调度策略，结合基于周期和事件驱动的再调度机制，解决不确定环境下多OHT 在多环耦合下的路径协调问题，同时提出了动态调度算法，由于运算量保持在较低水平，该算法能够快速高效地应用于复杂环境，并使系统规划的安全性和可达性在一定约束下得到保证。

1 问题描述

300mm 半导体制造中的整体式自动物料搬运系统（Automated Material Handling Systems，AMHSs）是指Interbay和Intrabay的轨道直接相连，作为物料搬运设备的OHT 无需经过存储柜进行暂存转运，便可直接实现tool与tool间的直接搬运，如图1所示。

在本文假设的同向、同速的自动物料搬运系统内，路径冲突的发生只有两种形式，如图2所示。

图2a表示在OHT 前行路径上有其他OHT驻留，其原因可能有加工设备故障导致搬运任务延迟、OHT 等待装卸载或其他OHT 正在等待自身前方的节点可用等。图2b表示由于实际运行时间与预计不一致，导致两辆OHT 在同一时间通过同一节点。由图2可以看出，路径冲突会导致OHT 碰撞，从而使设备受损、系统停滞，给生产运行带来不利影响。

为有效刻画问题，现对系统做如下基本假设：①自动物料搬运系统采用脊柱型布置，设备、存储柜间的距离由路径表确定，轨道单向单轨设置；②晶圆的加工顺序由工艺表决定（即搬运任务的路径起点与终点确定，但途径节点及其驻留时间需要在调度过程中决定），工序加工时间可变，考虑设备故障等不确定因素；③在轨道上加工机器的装卸载处及轨道的交叉点设置节点，装卸载时间为常量，且每次只能装卸载一辆OHT，OHT 的运行速度为常量且只能在节点处主动驻停；④每个节点同一时刻只允许一辆OHT 运行或驻停，节点间允许多辆OHT 依次通过，但不允许并行或超越；⑤OHT 每次只搬运一批晶圆，不考虑其自身故障，设备及存储柜容量设为无限。

设晶圆J 的加工路线为σ=（σ1，σ2，…，σJ），第r个工序的加工时间为t（σJ，r），它可根据设备自身的情况发生变动。为深入分析问题，对路径上的相关变量做形式化描述如下：假设系统中有M 辆OHT，OHTi装载的任务规划路径Pi=（pi，1，pi，2，…，pi，ni），其中pi，j表示其路径上经过的第j 个节点，定义为OHTi进入节点pi，j的时间，为OHTi离开节点pi，j的时间。将在节点pi，j和pi，j+1之间不包括首尾节点的轨道区域称为路径Li，j，以下证明在本文假设条件下OHT 不会在路径Li，j上发生碰撞的充分条件。

定理1 对任意Li，j∈pi，若OHTi在节点pi，j处不会发生碰撞，则在Li，j=（pi，j+pi，j+1）上OHT均不会发生碰撞。

证明 假设该时域内一移动OHTb追赶停留在轨道上的OHTa，由于OHT 只能在节点处主动驻留，若有碰撞则一定发生在OHTa的停留处，即节点处。而若该时域内两辆OHT 均为移动状态，则假设OHTa行驶在前，由假设可知在节点pa，j处OHTa和OHTb未发生碰撞，由于OHT 运行同向且同速，两车在经过该路径内的每一点时均会保持相同时差，即若发生碰撞则只能在节点pa，j+1处。由定理1可以看到，在本文假设情况下，碰撞只发生在节点处，如果在某段路径的首节点未发生碰撞，则在路径上（不包括尾节点）均为无冲突状态，据此对无冲突路径做出形式化定义。

定义1 在规定时域T 内，任意两条规划路径的时域内子路径p′i和p′i′，若对于pi，j=pi′，j′（其中，均 有∅成立，则称该路径规划方案无冲突，其中P′i⊆Pi，P′i′⊆Pi′。

从以上证明和定义可以看出，OHT 的碰撞发生的充要条件为同时满足时间和空间重合的要求，并且在不考虑OHT 自身故障的假设下，路径冲突必定发生在节点处。因此在侦测路径冲突时，依次对时域内预规划路径采取空间和时间比较的方法，只有在经过节点相同时分别比较相应OHT 的进出节点时间，才能大大提高侦测效率，减少系统开销。

下面建立无冲突路径规划问题的数学模型。设OHT 的装载时间为Tl、卸载时间为Tu、运行速度为v。OHTi候选搬运路径共有Ri条，设其第k 条候选路径Pi（k）上共有ni，k个节点，第j 和j+1个节点间的距离为Li，j（k），其进出第j个节点的时间分别为，由OHT 不允许在路径上驻留得：

令i（p，u）表征经过节点p 的第u 辆OHT 序号，由路径冲突的约束有

令i（l，z）表征经过路径l的第z 辆OHT 序号，由路径上不允许OHT 并行或超越可知，需有：

以上有i=1，2，…，M，j，j′=1，2，…，ni，k，k，k′=1，2，…，Ri。令T（Pi（k））为路径Pi（k）所需要的时间，调度目标为从所有路径中找到满足无冲突约束且用时最短的路径Pi，并得到其在路径上每个节点进入和驶出的时间，使得该任务的搬运时间最少，即

则该问题可以表述为以式（6）为目标函数、以式（1）～式（5）为约束的非线性规划问题。

2 算法构建

为解决整体式布局下自动物料搬运系统中由不确定因素导致的路径冲突问题，结合上述数学模型，构造基于滚动时域的调度算法，同时采用基于周期和事件驱动的混合再调度策略。算法的核心思想如下：

周期再调度策略通过对每个时域末系统的实际运行状态检测，更新下一时域初的初始条件，并进行计划外新到达任务的派工和路径规划，事件驱动的再调度策略则在探测到不确定性事件发生时更新系统相关信息，以此为初始条件进行避碰检测和路径规划。

其中涉及的避碰策略描述如下：首先在规划路径时不考虑冲突因素，以Dijkstra算法求得全局最短路，然后在每个滚动时域中连续进行路径冲突的检测和规避。具体操作为：对时域内空间侦测后重叠的节点集合以OHT 进出节点的时间进行试算，预测到碰撞后调用冲突解决模块，通过回溯冲突点前的节点是否符合相应的特征来检测是否可以改变路径，若不可改变路径则只能在当前节点采取等待操作，否则比较使用等待策略和更改路径策略的时间开销，选择耗时较小的方案执行。

本文的冲突规避方法分为等待和更改路径两种，目前较为常用的N 短路径算法一般采用机械的全局排序遍历方法，在大规模图中运行耗时较大，为满足系统实时动态调度的需要，减少可行路径的搜索域，本文基于文献［10］开发了针对OHT 轨道特点的改进型N 短路径算法，通过只构造无冲突路径直接求得可行次短路径，减少搜索域，避免系统的无效重复开销。为阐述构造无冲突N 短路径的算法，对N 短路径定义如下：

定义2 记图G 上给定的两个顶点vs和ve之间的一条路径为r，其长度为d（r），则由vs和ve之间的所有路径组成的集合为R，其中R=｛r1，r2，…，rn｝，若按照长度排列有d（r1）≤d（r2）≤…≤d（rn），则称r1为点vs和ve之间的第1短路径，r2为点vs和ve之间的第2短路径，rn为点vs和ve之间的第n 短路径。

定义3 设OHT 在两节点vs和ve之间的最短路径r1=（vs，v1，v2，…，ve），deg+（vi）为节点vi的出度，以e（vi，vi′）表示点vi和vi′之间存在直接相连的边，如果deg+（vi）＞1，则表明存在e（vi，vj），且vj∉r1，令相应的vj∈Vad。

定理2 对第2短路径r2，∃vj∈r2，其中vj∈Vad，有

推论1 对第n 短路径rn，∃vj∈rn，其中vj∈Vad，且有

结合以上第n 短路径的构造特点，为表述多环耦合下自动物料搬运系统中无冲突路径的快速构造途径，再补充如下定义：

定义4 若∃e（vb，vi），有vi∈rk且vb∈rk∩r1，则称vb为分支点；若∃e（vj，vu），有vj∈rk且vu∈rk∩r1，则称vu为融合点；将检测到的发生路径冲突的碰撞点记作vc。

定义5 将更改路线以实现冲突规避的情况区分为：当第k路径不再经过冲突点时，称该路径为可完全规避冲突的路径；当第k 短路径通过冲突点的时间大于原路径通过时间时，称该路径为可部分规避冲突的路径；当第k 短路径仍在原时间通过冲突点时，称该路径为完全不可规避冲突的路径。

定理3 当检测到冲突时，设三类定义点在路径r1中的序号分别为ib，iu和ic，注意到由定义必有ib＜iu，则候选的k短路径具有以下特征：

（1）ib＜ic＜iu，此时该路径可完全规避冲突。

（2）iu≤ic，此时该路径可部分规避冲突。

（3）ic≤ib，此时该路径完全不可规避冲突。

证明

（1）ib＜ic＜iu，由于此时k 短路径不再经过冲突点vc，则时间区间，必有，其中有pi，ic=pi′，j′，原来发生在该节点的冲突可完全规避。

（2）iu≤ic，由 于 d（rk）=（r1）-d（vs，vu）］｝，有d（rk）-［d（r1）-d（vs，vu）］≥d（vs，vb）+d（vb，vu），即k 短路径中到达原冲突点的时间，若Δt＜tw，则该路径可规避冲突，否则原冲突仍会产生，式中

（3）ic≤ib，则k短路径到达冲突点的时间，原冲突依旧发生。

利用定理3的结论可以构造用于搜索无冲突路径的改进型N 短路径算法，而通过权衡等待策略与更改为最短无冲突路径策略所需的搬运时间，可以减少OHT 由于避碰导致的时间开销，在保证系统安全运行的前提下减少搬运时间，提高OHT 的利用率，进而提高整个系统的制造效率。下面介绍滚动时域内总周期调度的具体算法运行步骤。

步骤1 产生初始时刻的搬运任务，生成搬运任务的初始点和终止点，令滚动时域序号T=0。

步骤2 令T=T+1，当前时域开始调度。对该时域内新到达的任务规划最短路径，对已在搬运中的任务记录进出节点的实际时间，根据上一区间的执行结果更新该区间的末位置，令i=0。

步骤3 令i=i+1，对于执行搬运任务的OHTi，获取搬运路径Pi在当前时域内的路径规划子集T|Pi|，求得通过T|Pi|内各节点的预计时间。

步骤4 依次对pi，k∈T|Pi|进行空间检测，令k=0。

（1）k=k+1，k 为当前进行冲突侦测的节点在OHTi的路径Pi上的序号。

（2）检测是否∃pi，k∈T|Pi|，有pj，k′∈T|Pj|，使得pi，k=pj，k′，其中j=1，2，…，i-1，若存在则转步骤5。

（3）若k＞ni，则转步骤3，否则转（1）。

步骤5 对空间重叠的点pi，k∈T|Pi|和pj，k′∈T|Pj|进行时间冲突侦测，分别比较其预计进出该节点的时间。若，则转 步骤4（3），否则转步骤6。

步骤6 对能否采用更换路径的方式解决冲突进行判断，若可行则得出更改后的路径P′i和更改后的新路径所需的时间Tc（P′i）。

（1）如果∃u＜k，pi，u∈T|Pi|有deg+（pi，u）＞1，则转（2），否则转步骤7。

（2）由于deg+（pi，u）＞1，表明存在e（pi，u，v），且v∉r1，令所有符合条件的v∈Vad，w=0。

（3）w=w+1，若Vad≠∅，则从Vad中取出点vw，计算从该OHT 上一区间的末位置vt到vw的最短路径d（vt，vw），否则转（11）。

（4）检测是否∃e（vw，vx），其中vx∈r1，若存在则求得vx在r1中的序号ix，若ix＞k，则转（5），否则转（6），若不存在vx则转（7）。

（5）计算dw=d（vt，vw）+d（vw，vx）+r1-d（vx，ve），放入候选路径集R。

（7）计算从vw到OHT 任务终点ve的最短距离d（vw，ve），若d（vw，ve）∩d（vk，ve）≠∅且d（vw，ve）∩d（vk，ve）≠vt，则转（8），否则计算dw=d（vt，vw）+d（vw，ve），放入候选路径集R。

（8）得到d（vw，ve）和d（vk，ve）中的第一个重叠点vco，求得其在r1中的序号ico，若ico＞k，则转（9），否则转（10）。

（9）计算dw=d（vt，vw）+d（vw，vco）+r1-d（vco，ve），放入候选路径集R。

（11）从候选路径集R 中得出最短路径min dw，该路径即为可完全规避冲突的最短路径，得出该可行路径的完成时间Tc（P′i）=T（min dw）。

步骤8 将两种任务的预计搬运时间乘以权重加以考虑，α为等待策略权重，β为更改路径策略权重，具体可根据调度需求进行设置，选择总耗时较小者并更改调度方案。

（1）若αTw（Pi）≤βTc（P′i），则以等待方式避开冲突，更新后续节点进出路径上的各节点的时间。

（2）若αTw（Pi）＞βTc（P′i），则以更改路径的方式避开冲突，更新路径规划方案，并重新计算后续路径上预计进出各节点的时间。

步骤9 若k＞ni，则转步骤10，否则转步骤4（1）。

步骤10 若i＞M，则转步骤11，否则转步骤3。

步骤11 执行该时域内调度，并更新时域末各任务的实际位置，作为下一时域路径规划的初始条件。若T＞Tmax，则调度结束，否则转步骤2。

事件驱动再调度模块的作用为：当系统出现临时急单或者设备故障等事件、导致通过节点的时间与预计不一致时，对新到达的任务规划最短路径，更新系统实际进出节点的情况，令i=0，并转至上述流程的步骤3。

3 仿真实验及分析

晶圆制造往往需要经过几百道工序，生产周期长达几个月。本文聚焦于晶圆制造中的自动物料搬运系统，在相对较短的仿真时间中，根据正态分布在相应时刻随机产生的搬运任务来模拟晶圆搬运任务的生成，并随机确定其起点和终点，搬运完成后即退出系统，系统基本布置如图1所示，各节点间的从至表由具体布局计算得出。假定OHT 的运行速度为1m／s，装卸载时间均为5s／次，随机生成初始时刻的OHT 位置。在仿真时间内，为模拟紧急插单，随机生成新的搬运任务到达系统；为模拟设备故障和来料延迟，随机延后某几个任务的到达时间。

为有效评价本文提出的基于滚动时域调度方法，引入以下变量衡量调度结果：AFT 表示任务平均完成时间，其定义为从晶圆运输任务产生到晶圆被卸载至目的地设备所需的平均时间，该值越小，制造系统的运行效率越高；AWT 表示任务平均等待时间，其定义为从任务到达系统至任务在源设备被OHT 装载的平均时间，该值越小，搬运工具的利用率越高；ATT 表示任务平均搬运时间，其定义为从OHT 装载任务后运至目的地卸载的平均时间，该值越小，物料搬运系统的运行效率越高，其中有AFT=AWT+ATT。将本文提出的基于滚动时域结合事件驱动再调度的方法用C++编程实现，并在主频2.00GHz、内存2GB的便捷式计算机上运行，实验结果和分析如下：

3.1 运算时间分析

分别令系统内的intrabay 数目为12，14，16，18，20，22 和24，每个intrabay内设置8台tool，OHT数量M=40，任务数量N=60，每次实验运行5次，取整个仿真程序运行时间的平均值，调度运行时间如图3所示。

可以看出，整个程序的运行时间随intrabay数目的增加呈线性增加趋势，即其与所设节点个数正相关，但总体求得调度结果的时间仍很小。由于该调度算法为实时运行，其计算调度方案所需的运行时间与系统实时执行方案时间相比几乎可以忽略不计，本文所提算法适用于实际生产中的动态实时调度。

3.2 搬运工具数目对搬运效率的影响

令intrabay数目为24，每个intrabay内设置8台tool，任务数量N=60，分别令OHT 数量M=20，30，40，50，60，任务的搬运效率相关指标如图4所示。

从图4可以看出，在相同任务负荷情况下，随着OHT 数量的增加，算法得到的任务平均运行时间和平均等待时间明显下降，且逐步趋向平稳，说明在负载不平衡时，OHT 数量对系统性能的影响较大，而当系统负载趋于合理时，OHT 数量的变化对系统性能的波动影响不大，因此可以通过该算法寻找合理的OHT 配置数量来提高运行效能。

3.3 布局规模对搬运效率的影响

分别令系统内的intrabay数目为8，12，16，20和24，每个intrabay内设置8台tool，OHT 数量M=40，任务数量N=60，任务的搬运效率表现如图5所示。

由图5可知，当系统布局规模增大时，任务的平均完成时间增大，但结合其平均等待时间趋于平稳来看，完成时间的增加主要由搬运时间即规模增大时平均搬运距离增长引起。在该系统配置条件下，平均等待时间趋于平稳，表明该算法对于较大规模的系统布局具有良好的适应性，可适用于实际生产系统。

3.4 负载率对搬运效率的影响

将任务数量与OHT 数量的比值设置为1，2，3，4和5，令系统内intrabay数目为24，每个intrabay内设置8台tool，任务的搬运效率表现如图6所示。

由图6可知，由于平均完成时间与平均等待时间基本呈相同的变动趋势，可以推论：当负载率增大时，平均完成时间的增大主要由等待时间增长引起。在1～4倍负载率的情况下，任务的平均完成时间和平均等待时间均随系统负载率的增大而增大，说明此时算法性能受负载率的影响较大，该阶段在负载率到达4之后的变化明显放缓，表明在负载极端不平衡时，算法仍具有一定的稳定性。

3.5 平均故障时间对搬运效率的影响

令intrabay数目为24，每个intrabay内设置8台tool，任务数量N=60，令OHT 数量M=40，将平均故障时间分别设为20，40，60，80，100，120，140和160，算法的调度性能指标如图7所示。

由图7可以看出，平均故障时间基本保持平稳状态，对算法性能的影响不大，并且平均完成时间出现的波动主要受平均等待时间影响，表明在故障类型多样、故障时间差异较大的实际生产情况下，算法仍具有稳定性。

3.6 故障率对搬运效率的影响

令intrabay数目为24，每个intrabay内设置8台tool，任务数量N=60，令OHT 数量M=40，系统内加工设备的故障发生率分别为0.01，0.02，0.03，0.04 和0.05，算法的调度性能指标如图8所示。

由图8可见，任务的平均完成时间主要随平均等待时间波动，任务的平均搬运时间首先随故障率的增加略微增加，在故障率达到0.03时达到峰值，随后随故障率的增加缓慢减少，并有趋于平稳的态势。说明算法在故障率较大的情况下可以有效减少系统中任务的搬运时间，适用于实际生产系统。

3.7 滚动时域长度对搬运效率的影响

滚动时域长度即系统对实际运行状态进行探测并更新的周期，本节在相同的系统设置下仅改变时域长度来研究其对算法性能的影响。由图9可见，任务的平均完成时间随时域长度的增加总体呈下降趋势，并在时域长度大于350s时趋向平稳，表明较长的滚动时域可以使调度效果接近全局最优，但同时算法的运行时间也会因计算量的增大而增加。如图9所示的算法运行时间在滚动时域长度为150s附近达到最低值，但此时调度结果仍有改善空间；在时域长度为200s～300s的区间内，算法的运行时间和调度结果都处于相对稳定的平台期，之后随着时域的增长，算法运行时间显著增长，而调度结果的改善效应则趋于平稳。因此在实际使用中，为了求得最佳滚动时域，可以通过计算机仿真技术或者试运行获得运行的相关数据，以较经济的时间获得较优解，使算法既能满足实时调度的要求，又能获得较好的调度结果。

3.8 与其他算法的比较

在AGV 调度领域，文献［3］中同一路径同一时刻只能被一辆OHT 占用的的避碰思想具有一定的代表性并具有普遍的适用性；而在半导体领域近年的相关研究中，以文献［11］为代表的时间窗方法应用较为广泛。为有效评价本文提出的基于滚动时域和事件驱动的混合再调度方法，分别引用文献［3］的区域分治静态调度思想和文献［11］的基于事件静态预调度的算法，与本文算法在同速同向且系统设置相同的条件下运行并进行对比分析。分别令系统内的intrabay数目为8，12，16，20 和24，每个intrabay内设置8台tool，OHT 数量M=40，任务数量N=60，任务的搬运效率（AFT）表现如表1所示。

表1 算法性能对比（AFT）

其中算法1采用的是较为保守的调度策略，当检测到路径重叠时，限制同一路径上同一时刻只能运行一辆OHT；算法2则允许OHT 在同一路径同时被多辆不发生冲突的OHT 占用，但系统实际运行情况与预调度方案不同时，两者均无法有效检测实际冲突并进行避碰。通过对比可以看出：滚动时域调度方法计算的平均搬运时间在小规模条件下均略长于静态调度算法，但因为其中包括了为避免冲突而进行的等待和更换路径操作，所以在合理范围内。在用于较大规模结构时，由于在路径上的运行时间随着布局规模的增大而显著增加，偏差度的增加较为显著。

4 结束语

本文应用滚动时域模型实现了不确定环境下多环耦合的整体式自动物料搬运系统进行实时规划和调度。其中，基于周期和事件驱动的混合再调度策略可以有效保障OHT 的运行路径无冲突碰撞。通过对OHT 碰撞发生的充要条件进行深入分析，结合空间和时间的冲突侦测，可以快速有效地侦测碰撞发生，节省系统开销。根据不同冲突节点的不可用时间，选择合理等待或更改路径的避碰策略，能够有效缩短避碰带来的工期延长，增加搬运设备的利用率。针对OHT 轨道运行特点构造的改进型N短路径算法，能够有效减少搜索可行候选路径时间，增加调度效率。本课题来源于晶圆制造厂商的实际生产问题，考虑了大多数半导体调度研究中忽略的自动物料搬运系统实际运行情况，其中本文主要针对OHT 同速同向运行下的整体式自动物料搬运系统的路径调度问题做了探讨，今后将对该模型在异速双向的多环耦合情况下的适用性做进一步研究。

［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］.Computers &Industrial Engineering，2009，56（1）：417-432.

［2］SMOLIC-ROCAK N，BOGDAN S，KOVACIC Z，et al.Time windows based dynamic routing in multi-AGV systems［J］.IEEE Transactions on Automation Science and Engineering，2010，7（1）：151-155.

［3］MAZA S，CASTAGNA P.A performance-based structural policy for conflict-free routing of bi-directional automated guided vehicles［J］.Computers in Industry，2005，56（7）：719-733.

［4］SRIVASTAVA S，CHOUDHARY A，KUMAR S，et al.Development of an intelligent Agent-based AGV controller for a flexible manufacturing system［J］.International Journal of Advanced Manufacturing Technology，2008，36（7／8）：780-797.

［5］EROL R，SAHIN C，BAYKASOGLU A，et al.A multi-Agent based approach to dynamic scheduling of machines and automated guided vehicles in manufacturing systems［J］.Applied Soft Computing，2012，12（6）：1720-1732.

［6］NISHI T，MORINAKA S，KONISHI M.A distributed routing method for AGVs under motion delay disturbance［J］.Robotics and Computer-Integrated Manufacturing，2007，23（5）：517-532.

［7］GHASEMZADEH H，BEHRANGI E，ABDOLLAHI AZGOMI M.Conflict-free scheduling and routing of automated guided vehicles in mesh topologies［J］.Robotics and Autonomous Systems，2009，57（6／7）：738-748.

［8］NELSON R T，HOLLOWAY C A，MEI-LUN W R.Centralized scheduling and priority implementation heuristics for a dynamic job shop model［J］.AIIE Transactions，1977，9（1）：95-102.

［9］SOURIRAJAN K，UZSOY R.Hybrid decomposition heuristics for solving large-scale scheduling problems in semiconductor wafer fabrication［J］.Journal of Scheduling，2007，10（1）：41-65.

［10］BAI Yiduo，HU Peng，XIA Lanfang，et al.Ath-shortest path algorithm based on k-1shortest paths［J］.Geomatics and Information Science of Wuhan University，2009，34（4）：492-494（in Chinese）.［白轶多，胡 鹏，夏兰芳，等.关于k次短路径问题的分析与求解［J］.武汉大学学报：信息科学版，2009，34（4）：492-494.］

［11］ZHENG Wen，ZHOU Binghai.OHT dispatching and routing scheduling algorithm based on events-driven［J］.Computer Integrated Manufacturing Systems，2013，19（1）：75-81（in Chinese）.［郑 雯，周炳海.基于事件驱动的高架提升传输小车派工与路径调度算法［J］.计算机集成制造系统，2013，19（1）：75-81.］