英语原文共 7 页，剩余内容已隐藏，支付完成后下载完整资料

自动物料搬运系统中的拥塞感知和自动选路

高光：

自动物料搬运系统中的车载式运输拥堵降低了效率。

我们提出并模拟拥塞感知的动态车辆选择路径的方法。

拥塞感知并自动选路适当地提高了稳定性能。

拥塞感知并自动选路显著降低严重拥堵。

拥塞感知并自动选路提高了车辆故障恢复速度。

摘要：

在自动化材料处理系统（AMHS）中，例如那些用于在半导体制造设备中传输芯片，车辆运输拥挤导致运输延迟，降低了生产效率。通过一个高仿真模拟应用，我们展示了一个有效地改变车辆拥堵状况的拥塞感知并动态选路策略。稳态路径性能适度提高，拥塞的频率显著降低，系统更有效地从车辆故障中恢复。

关键词：

半导体；物料搬运；实时；动态车辆路径；仿真；拥塞

1 简介

半导体制造是一个高度复杂的，可再进入的过程。这个过程中，晶圆和装在墨盒，通过数百个处理步骤在洁净室设施运输。由于被传输物品的规模，价值，敏感属性，墨盒通过一般包括轨道式提升机运输设备的自动物料搬运系统的设施移动。低效的OHT路径或者OHT设备故障产生的严重拥堵可迅速升级成大规模生产延迟。这引发了有效处理稳态拥塞和意外例如OHT失效路径的路径算法的需求。实施新的车辆控制方法之前，整合生产调度和物料搬运的拟议中的变化需要在专有的模拟软件上测试。证明这样的测试需要表明拟议的变化将导致增加的效率和/或降低成本的证据。

半导体制造设备通常被组织成包含相同类型的机器的海湾。在我们考虑的设施类型中，海湾通过一个中心环和一个外环连接，每个海湾有两个入口和两个出口。当墨盒完成一步处理，一个传输请求就生成了然后集中控制系统分配OHT车辆运输它。如果没有车辆可用，系统将请求添加到等待队列等待分配。分配后，车辆移动到墨盒当前位置，将墨盒从机器上卸载到车辆上，移动到处理序列中的下一个机器或移动到存储位置，并且将墨盒加载到下一个机器或存储位置。车辆运动的控制因为物理因素是复杂的，例如直线上不同的速度和弯道的边缘，需要减速的硬件考虑，和管制闲置车辆的政策。

在实践中，车辆行驶的路线选择基于静态因素，如距离，边缘最大行驶速度，和加载/卸载点的位置。所有特定起源地和目的地之间的运输请求都将使用相同的路径，不管当前的拥塞位置和强度，并遵循这条路线不管系统如何变化。如果拥塞发展在预期的路线上，车辆仍直接进入拥堵，既耽误自己又使拥堵恶化。我们定义这为静态路径。考虑到半导体制造设备的结构，静态路径往往会导致显着的中心环拥塞包括需要人工干预解决的死锁拥塞。为了分配流量，减少死锁的发生，工程师使用了临时拥塞惩罚。这个方法是不够系统的，不能够轻松地适应生产顺序和产品结构的变化，并且不能够快速响应不断变化的拥塞特性。

为了更有效地运输车辆和减少拥堵，车辆必须考虑所有其他车辆的当前和未来的路线。如果预先知道所有的请求，可以使用大规模整数规划的先验路径优化。由于加工时间的不确定性和柔性生产调度，请求时间、来源和目的地事先不知道。因此，这是一个在线，实时车辆路径问题。我们定义动态路径为一种允许车辆改变其路径以响应拥塞通过不断了解系统的状态并适应，基于新的信息的基础上。在文献中，拥塞感知动态路径方法曾经被提到过，但是他们需要密集的计算并且他们的有效性仅表现在不到50辆的小规模模拟。

在本文，我们提出了一种采用一个容易实现的拥塞度量和高效率计算并且能用于实践的拥塞感知的动态路径的方法。我们在一个原型设备中车辆运动的高保真模拟中证明了他的有效性。稳态性能适度提高，严重拥堵的频率明显降低，并且系统能够更好地从诸如车辆故障等异常中恢复。尽管传输请求以每秒1 - 2的速度生成，动态路径算法是足够快的，所以没有延迟发生在他的模拟现实中。

在本文的其余部分，第2节简要讨论了相关文献，第3节介绍了我们的方法，第4节提供了详细的模拟，第5节提出的结果，第6节总结。

1. 文献

有限的工作已经在AMHS车辆路径隔离系统中完成了因为从隔离系统过渡到统一系统是相对较新的。在统一的系统中，车辆在整个网络中移动，而不是被限制在一个特定的区域，正如它在先前的隔离设计中。在统一系统中路径选择更加复杂。在拥塞感知的动态路径， (Yang, Cheng, Chiang, amp; Fu, 2008)，通过从使用当前沿着路线行驶的车辆的数量作为拥塞的量度的候选集中选择一个路径使车辆在每一个分叉的路口分散。它在一个小的模拟中演示了一个温和的改善稳态指标，但是他没有讨论严重拥堵、死锁或车辆故障的发生。专利(Gaskins et al., 2001 ; Huang et al., 2008) 还建议路径选择使用预先确定的候选路径集。这覆盖了车辆在哪里，车辆在过程中不改变路径和不呈现结果的情况。专利(Gaskins et al., 2001)使用当前沿着路线行驶的车辆的数量作为拥塞的量度并且(Huang et al., 2008) 不提出具体的度量。

基于时间窗口(Kim and Tanchoco, 1991; Kim and Tanchoco, 1993; Huang et al., 1993; Smolic-Rocak et al., 2010 ; Chen et al., 2013)，增加路径规划 (Tanchoco amp; Taghaboni-Dutta, 1995)，分级模拟 (Seifert, Kay, amp; Wilson, 1998)，Petri网 (Nishi and Maeno, 2010 ; Nishi and Tanaka, 2012)，区域控制(Ho amp; Liao, 2009)，和基于代理的(Lau amp; Woo, 2008)方法已经被提出作为各种类型的拥塞感知动态路径的方法在在各种类型的车辆数较少的通用自动引导车辆（AGV）网络中。AGV是用来描述任何自动化车辆的总称。一般AGV的方法并不总是适用于客人，因为他们通常认为较小的网络系统具有一个更一般的结构。海湾的OHT系统结构限制了备用路径的存在。

1. 方法

我们模拟一个设施作为一个有向网络。节点对应加载/卸载端口和轨道相交点和边缘的铁路段连接节点。所有轨道都是单向的。每一边被分配一个权重以表示这边的预计的穿越时间。为了某些目的，我们考虑到节点仅代表铁路交叉点，而不是端口的交点网络。我们使用“发散节点”来表示一个具有多个传出边的节点。注意在OHT网络中，与每个节点相关联的传入加输出边的总数通常不超过三。

我们提出了一个通过平滑地使用不断更新的边缘权重计算通过指数的拥塞感知的动态路径方法。对于每一个边，我们存储了一个表示穿越时间的边缘权重。当车辆度过了节点，该系统记录了那辆车穿过边缘所使用的时间并使用指数平滑法更新估计的边缘穿越时间， ，是边(i,j)的权重，第n次遍历之后， 是n遍历时间，和lambda;是参数指示估计边缘遍历时间的新的信息的敏感性。

在任何车辆遍历边缘之前，我们令lambda;等于该边的长度除以该边上的最大行驶速度。用一个小的值的lambda;，估计边缘遍历次数接近长期平均水平。好的lambda;值可能随影响严重拥堵或死锁的可能性的布局和运行特性而变化。我们是用一个lambda;的值贯穿整个系统，但是可以使用lambda;边缘的具体值。例如，网络拥塞越频繁的区域使用较大的值lambda;更好而网络拥塞越少的区域使用较小的值lambda;。

以前研究拥塞的措施，例如目前正在行驶的车辆的数量，表示系统拥塞的瞬时视图。通过除去目前的信息的最近的信息，可以实现更强大的表示。我们的方法还集成了由于布局特点如车辆进入曲边后可能减速造成的预期的延迟。

在我们的方法中，车辆路径和路径节点采用基于查找表。传统上，一个车辆的路径作为车辆属性存储。在每个发散节点的车辆从存储的路径中选择下一个节点。对于动态路径，在每个不同的节点车辆重新计算路线以确保其首选的路线没有变。如果在第二次模拟时间内有R请求并且每条路径平均有d个发散节点，路线计算总数将为R*（D 1），这可能不是随时间均匀分布的。

我们所提出的方法在每个发散节点存储了一个查找表包括路径中的下一个节点到每个对应的目的地。查找表以固定的时间间隔周期性的更新。随着车辆接近发散节点，它在查找表中寻找其下一个节点。例如，在图1中一个车辆在接近节点I并且在节点Z处有个一目的地。车辆在表中与目的地Z中的节点I关联。该表指示车辆应根据当前的拥塞状态转到节点A。注意每个有一个特定接近在两个后续表更新之间接近给定节点的目的地的车辆将遵循相同的路线。

为了更新一个表，我们用Dijkstrarsquo;s算法在交点网络中运行一个一对所有的最短路径计算。表的更新可以很容易地并行着随着这个一对所有的每个不同的节点估算是独立进行的。与一个I秒更新间隔在一个T秒的模拟时间，我们更新表I/T。因此，估算的数量不随一个更高数量的申请或者更多的发散的节点而增加，允许在大型网络中有效使用。

图1 路径查找表

图2 设备布局图

4.模拟

为了在一个现实的模拟网络中测试我们的方法，我们使用AutoMod仿真软件开发了一个模拟车辆运动的原型设施。我们的网络有大约400个三路交叉口，600个边，和额外的1400个装卸点。在我们的模拟中，150 - 250车辆被分配在实时的由一个起源和一个目的地组成的传输请求。基于原型生产序列通过概率分布生成请求。

该原型装置（图2）是一个统一的有着20个海湾，每个有60个装卸点，240个沿中心循环分布用于存储的额外的装卸点 的AMHS。转移请求的来源和目的地代表两个机械的装卸点和存储位置。在一个海湾中，我们不区分端口和侧轨缓冲存储位置。所有沿中心环分布的位置代表储存器存储位置。该设施有四个中心环路交替的行进方向的旅行车道和两个有相对行驶方向的外环旅行道。每个中心和外部循环有14个快捷路径。在图2中，蓝点代表装卸位置，红色位置代表交叉点。

取代通过其整个生产顺序模拟墨盒的进度，我们生成一个墨盒可从原点移动到目的地转移请求指示。每个海湾被分配到八个进程中的一个并且我们基于400个步骤的每个过程重复几次的原型生产序列生成传输请求。基于此序列和输入参数指示墨盒在生产步骤之间访问存储位置的概率，我们生成一个马尔可夫链中使用的过渡矩阵的形式。转移矩阵指定从与一个过程相关联的位置到与另一个过程相关联的位置的移动的概率。沿中心循环的存储位置被与海湾地区分开考虑。从过渡矩阵中，我们产生用来在预热期间选择请求源的平稳分布。我们定义在海湾的净交付为在该湾的交货数量减去分配到该湾的原产地数目。我们跟踪在每个海湾的净交付数量，并在热身期后，根据跨海湾的分布选择新的请求源。通过这种方式，如果车辆因严重拥堵而无法交付请求，将没有新的请求产生与起源在该湾。这更接近真实系统中的行为。对于每个请求，根据转移矩阵选择一个目的地。请求之间的时间是从指数分布产生的净交货的总数确定的平均值。

当一个请求产生时，该系统通过运行Dijkstra的算法使用目前的边的权重计算最早的预测到达时间的车辆并且分配此车辆的请求。如果没有车辆可用，系统将请求添加到等待队列等待分配。在静态路径的情况下，在请求的同时，该系统还计算从车辆当前位置到请求原点和从请求原点到请求目的地的路径。

一个车辆的在弯曲边的最高速度比在直边的最高速度低。因此，车辆必须减速以进入一个弯曲的边。如果车辆未进入弯曲的边，它可以继续以最大速度通过一个路口。在机器上装载和卸载需要确定的10秒。未分配到请求的车辆保持静止直到一个活动车辆请求它去生产。主动车辆预测未来在减速在静止车辆后方之前为了请求静止车辆去生产。当请求得到满足时，未分配的车辆向前移动到下一个分叉路口，并且沿着被呼叫车辆将会采取边缘的相对边。如果在一个海湾的未分配的车辆数超过阈值，要求生产的车辆将会被重新分配给一个有着较少未分配车辆的海湾。所有装卸都发生在轨道上并且其他车辆不允许经过一辆正在装卸的车辆。在实践中，一些设施无轨装卸但我们关注那些有轨装卸的设施。我们假设车辆只能在一个轨道上向一个方向移动的。因此，位于一个在边缘上停止车辆之后的车辆或许只能改变航线，如果这辆车和停止车辆之间有一个分离节点。

我们建立了1200秒的热身期基于速度指数和车辆利用率在最初的十次重复基于距离的静态路径中。速度指数定义为所有车辆（即不停止加载/卸载，而不是闲置和静止）应以当前速度除以给定车辆在网络中的位置的最大速度移动的平均值。我们以图形方式确定该系统通过1200秒达到稳定状态。为了确保重复的次数足够多，我们跑了二十个初始复制。在静态路径的情况下，其中六个达到严重的拥塞。利用剩余的十四个重复，标准偏差足够低所以我们使用这十四次重复作为稳态分析。

5.结果

我们目前的结果为基础的情况下，一个高工作量的情况下，一个带有中心环路车辆故障的场景。我们展示了一个提升了5%的稳态性能和在基础情况下消除拥挤的发生，在高负荷区重大拥堵频率大幅减少和车辆故障情况，和一个改善的车辆故障恢复机制。

每个场景中，我们通过使用三参数设置为每个lambda;和表更新间隔比较基于距离的静态路径与动态路径。我们还用表示长期平均边遍历时间的边缘权重来报告静态路径的使用和通过指数平滑更新边缘权值的静态路径的使用。我们使用基于距离的术语，长期平均和更新指的是不同类型的边缘权重。在图表中，路径方法表示静态（S）或动态（d）路径，表更新间隔指示的是以秒为单位的动态路径表之间的更新间隔时间，边缘类型表示基于距离的（BD）长期平均（LRA），或更新（U）边的权重，和边的权重参数表明lambda;边权值的更新。

5.1 基本情况

基本情况方案有175辆并且平均稳态车辆利用率为88%。因为重拥塞发生在使用基于距离的静态路径的二十次重复中的六次，我们的稳态指标包括其余的十四个重复的平均值。我们考虑到其他参数设置相同的重复。这些重复也是稳态的因为他们没有达到严重拥塞。一个严重的拥塞被定义为在完成

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[141809]，资料为PDF文档或Word文档，PDF文档可免费转换为Word