Noncyclic Scheduling of Cluster Tools With a Branch and Bound Algorithm
Noncyclic Scheduling of Cluster Tools With a Branch and Bound Algorithm
复制标题
DOI：
10.1109/tase.2013.2293552
复制
发表时间：
2015-04
影响因子：
5.6
通讯作者：
Hyun-Jung Kim;Jun-Ho Lee;Tae-Eog Lee
中科院分区：
文献类型：
--
作者：
Hyun-Jung Kim;Jun-Ho Lee;Tae-Eog Lee
群集工具，每种工具都由多个处理模块，一个物料处理机器人和负载锁组成，广泛用于晶圆制造过程，例如光刻，蚀刻和沉积。有许多用于循环调度集群工具的方法和算法，其中机器人重复了用于处理相同晶片的指定序列。但是，由于较大的晶圆尺寸和电路宽度的降低，最近的订单尺寸最近正在减小。在现代晶圆厂中，每个晶圆量可以在同一过程步骤中具有不同的流图和过程时间，并且在工具中连续处理异质的批次。即使是工厂中的某些工具，也有空闲时间等待晶圆批次，具体取决于过程中的波动。这种不同的晶圆批次和频繁的工具状态更改无法使用循环调度方法来处理，因此需要针对这种情况的非循环调度方法。因此，我们开发了一个有效的分支和约束（B＆B）程序，以针对群集工具的非周期调度问题，以最大程度地减少makepan。由于定时的培养皿（TPN）以其强大的建模能力和分析能力而闻名，因此该算法是基于TPN开发的。我们通过各种集群工具调度问题来验证B＆B程序的效率。关于调度群集工具的研究已经进行了许多研究，但是其中大多数使用不同的调度方法或开发问题专业属性。将所有不同方法实现到工具调度程序是不切实际的，因为调度要求根据晶圆类型和工具体系结构不断更改。因此，需要有一种有效的解决方案方法来解决工厂中各种群集工具调度问题，尤其是由于较大的晶圆尺寸和较小的订单尺寸，频繁的批次开关和工具状态变化。因此，我们开发了一个有效的分支和界限程序，用于使用MakePAN测量的群集工具进行非周期调度。由于TPN具有强大的建模能力和分析能力，因此该算法是基于TPN开发的。从实验结果中，我们观察到可以在合理的时间内轻松解决25个晶圆的批次。该方法可以通过生成每个相应的TPN模型来用于集群工具的许多不同调度问题。
Cluster tools, each of which consists of multiple processing modules, one material handling robot, and loadlocks, are widely used for wafer fabrication processes, such as lithography, etching, and deposition. There have been many approaches and algorithms for cyclic scheduling of cluster tools in which the robot repeats a specified sequence for processing identical wafers. However, the lot order size has recently been decreasing due to the larger wafer size and circuit width reductions. In modern fabs, each wafer lot can have different flow patterns and process times for the same process step, and heterogeneous lots are processed consecutively in a tool. Even some tools in a fab have idle time waiting for wafer lots depending on the work-in-process fluctuations. Such different wafer lots and frequent tool state changes cannot be handled with cyclic scheduling methods, and accordingly noncyclic scheduling methods for such cases are required. Therefore, we develop an efficient branch and bound (B&B) procedure for noncyclic scheduling problems of cluster tools to minimize the makespan. Since a timed Petri net (TPN) is known for its powerful modeling ability and analysis capability, the algorithm is developed based on a TPN. We verify the efficiency of the B&B procedure with various cluster tool scheduling problems. There have been many studies on scheduling cluster tools, but most of them utilize different scheduling approaches or develop problem specialized properties. It is impractical to implement all the different methods to a tool scheduler because the scheduling requirements continuously change depending on wafer types and tool architectures. Hence, it is required to have an efficient solution method to address diverse cluster tool scheduling problems in fabs especially for frequent lot switchings and tool state changes due to larger wafer size and smaller lot order size. Therefore, we develop an efficient branch and bound procedure for noncyclic scheduling of a cluster tool with the makespan measurement. Since TPNs have the powerful modeling ability and analysis capability, the algorithm is developed based on a TPN. From the experimental results, we observe that one lot with 25 wafers can be easily solved in a reasonable time. The proposed method can be used for many different scheduling problems of a cluster tool by generating each corresponding TPN model.