Recently, semiconductor manufacturing fabs tend to reduce the wafer lot size, down to just a few. Consequently, the wafer recipe or wafer flow pattern changes frequently. For such problems it is impossible to apply conventional prevalent cyclic scheduling methods that repeat processing of wafers in an identical cyclic tool operation sequence. We therefore consider the non-cyclic scheduling problem encountered in cluster tool scheduling.
In Chapter 2 we dealt with scheduling of single armed cluster tools. Single armed cluster tools have a simpler architecture than other configurations, but can be difficult to schedule when additional requirements such as re-entrant wafer flow, parallel chambers and multiple recipes are introduced. To solve these problems we proposed a method to transforms the problem into a multi-objective problem by considering the ready times of the resources as objectives to minimize. Only feasible states were generated based on the initial state of the system. These feasible states form a multi-objective shortest path problem and give us O((r+1)mn) as an upper bound for the number of states, where r, n, and m are the number of different wafer recipes, wafers, and processing chambers. We solved this problem with implicit enumeration by making our scheduling decisions based on the Pareto optimal solutions for each state. The experimental results showed that the proposed algorithm can quickly solve large sized problems including ones with arbitrary initial tool states, changing recipes, re-entrant wafer flows, and parallel chambers.
In Chapter 3 we developed a general scheduling algorithm for Petri nets. Petri nets are widely used for modelling and analysis of discrete event dynamic systems and are therefore suitable for scheduling more complex cluster tool architectures such as dual armed cluster tools. We defined a data structure for noncyclic Petri net scheduling problems and then transformed the scheduling problem into an equivalent multi-objective shortest path (MSP) problem in the state transition graph. Solving the MSP problem finds a path which minimizes the completion time for tokens at each subsequence step, and hence when the corresponding resource becomes available or ready for the next task. This will ultimately minimize the firing epoch of the final destination transition, corresponding to the makespan. We extended a label correction algorithm for existing multi-objective shortest path problems to handle the path dependent edge lengths in the graph and dynamic objectives. We then applied the Petri net-based scheduling method to noncyclic cluster tool scheduling problems. We demonstrate the efficiency of the scheduling method as compared to a branch and bound method.
In Chapter 4 we look into how cluster tools with different requirements can be scheduled. When multiple lots are processed concurrently they can have different due dates, chambers may require scheduled maintenance and longer flow times can reduce the quality of wafers. To solve these problems we introduced alternative objective measures. An algorithm was developed which minimizes the total flow time, total weighted tardiness or the number of tardy jobs. New methods were developed which made it computationally feasible to solve. The methods were then used to solve various scheduling problems in semiconductor manufacturing.
최근 반도체 제조 팹은 웨이퍼 로트 크기를 25장에서 7-8장으로 줄이는 추세에 있다. 결과적으로, 반도체 장비가 생산하는 웨이퍼의 레시피 또는 흐름 패턴이 다양해 지고 있는데, 이러한 문제들은 기존에 널리 사용되어 왔던 주기적 스케줄링 문제의 알고리즘 또는 방법론으로는 해결할 수가 없다. 따라서, 본 논문에서는 반도체 장비의 많은 부분을 차지하는 클러스터 장비의 비주기적 스케줄링 문제를 다룬다.
2장에서는 한팔 클러스터 장비의 스케줄링 문제를 다룬다. 한팔 클러스터 장비는 비교적 간단한 구조를 가지고 있지만 웨이퍼의 재방문 흐름, 병렬 챔버 또는 다양한 레시피가 있는 경우 문제가 복잡해 질 수 있다. 이를 해결하기 위해, 해당 문제들은 각 자원의 준비시간(ready time)을 최소화하는 것을 목적식으로 하는 다목적 (multi-objective)문제로 변환된다. 시스템의 초기 상태를 바탕으로 실현 가능한 상태들만 찾게 되며 이러한 상태들은 다목적 최단 경로 문제 (multi-objective shortest path problem)를 형성하게 된다. r, n, m이 각 서로 다른 레시피 수, 웨이퍼 장수, 챔버 수라고 할 때 O((r+1)mn) 이 가능한 상태수의 상한이 된다. 우리는 각 상태마다 Pareto 최적 솔루션을 기반으로 결정을 내리고 implicit enumeration을 통하여 문제를 해결한다. 실험을 통하여 제안한 알고리즘이 레시피가 다양하고 재방문 흐름이 있고, 병렬 챔버가 있는 복잡한 문제도 많은 웨이퍼를 동시에 풀 수 있음을 보인다.
3장에서는 페트리 넷을 기반으로 한 일반적인 스케줄링 알고리즘을 개발한다. 페트리 넷은 이산사건 시스템을 모델링하고 분석하는데 널리 사용되며 따라서 복잡한 클러스터 장비를 스케줄링 하는데 적합하다. 우리는 비주기적 페트리 넷 스케줄링 문제를 위해 데이터 구조를 정의하고 문제를 다목적 최단 경로 문제로 변환시킨다. 다목적 최단 경로 문제는 각 상태에서 토큰이 머무는 시간을 최소화 하며, 따라서 해당 자원이 다음 작업을 위해 최대한 빨리 가용 가능 하도록 하는 경로를 찾는 것이다. 이는 결국 마지막 트랜지션의 파이어링 시점을 최소화 시키고 makespan역시 최소화 할 수 있게 된다. label correction 알고리즘을 확장시켜 각 경로에 따라 다른 edge의 길이와 dynamic objective를 다룬다. 다음으로, 페트리 넷 기반의 스케줄링 방법을 클러스터 장비의 비주기적 스케줄링 문제에 적용한다. 기존의 분기 한정법(branch & bound algorithm)과 비교하여 우리가 개발한 방법의 효율성을 실험을 통하여 보인다.
4장에서는 다양한 요구사항을 가지는 클러스터 장비가 어떻게 스케줄링 될 수 있는 지를 살펴본다. 다양한 로트가 동시에 공정이 진행될 경우 납기일이 서로 다를 수도 있고 챔버의 유지 보수를 위한 시간이 필요하기도 하고 또 공정을 마친 후 웨이퍼가 장비 내에서 머무는 시간이 길수록 웨이퍼의 질에 영향을 줄 수도 있다. 이러한 문제들을 다루기 위해 전체 흐름시간이나 가중납기지연시간 또는 지연된 job의 수를 최소화 시키는 알고리즘을 개발한다. 새롭게 개발된 방법들은 이러한 문제들을 해결하는데 충분하며 다양한 반도체 제조 장비에 적용될 수 있다.
