Scheduling cluster tools is an important task in semiconductor wafer fabrication. An important issue is to determine when and how to schedule robot actions so that maximum throughput is achieved while maintaining good wafer quality. Since excessive wafer delays in process chambers may deteriorate wafer quality, wafer delays should be controlled within an acceptable range, or more preferably, should be minimized. Previous research focused on minimizing the cycle time, assuming the system is in steady state. However, the recent trend is to produce small amount of customized wafers, and the size of wafers is expected to grow from 300mm to 450mm. As a result, the transient period increases, which makes the steady state analysis less precise. For these reasons, this paper addresses the problem of non-cyclic scheduling with wafer delay constraints. To solve this problem, we first assumed that the robot sequence is given and developed a multistage linear programming (LP) model which consists of two LPs. The first LP model tries to minimize the total makespan while meeting the wafer delay constraints and the second LP tries to minimize the total wafer delay based on the result of the first LP. Then, we developed a branch & bound algorithm to find the optimal robot sequence with minimum wafer delay. First, we applied the dynamic programming approach introduced in the literature to find the lower bound of total makespan, and then we proposed an algorithm to find a tight upper bound. Finally, we modeled a LP model to check the feasibility of each branch. Applying the three mechanisms of lower bound, upper bound and feasibility check, fruitless nodes are eliminated at an early stage. Consequently, the computational efficiency increased substantially, which helped one solve problems that were not solvable otherwise. The simulation result shows that when the number of process modules grows to more than 5, the algorithm may fail to get the optimal solution due to computational complexity. In this case, we suggested a heuristics to find a candidate schedule which gives an error less than 2%.
반도체 제조공정에서 클러스터 툴의 스케줄링은 중요한 문제이다. 그 핵심은 로봇이 움직이는 시간과 순서를 결정하여 웨이퍼의 최대 생산량을 유지하면서 좋은 품질을 보장하는 것이다. 기존의 연구는 안정상태(steady-state)라는 가정하에 생산 주기시간을 줄이는데 초점을 두었지만 요즘에는 고객의 수요에 맞추어 적은 양의 다양한 웨이퍼를 생산하고 웨이퍼 사이즈가 300mm에서 450mm로 늘어남에 따라 불안정상태(transient state)가 길어지고 있다. 이런 상황에서 안정상태만을 연구하는 것은 현실성이 떨어지므로 이 논문은 불안정상태를 포함하여 연구하였다. 또한 웨이퍼의 품질을 보장하기 위하여 웨이퍼 지연 제약을 두었는바, 이는 웨이퍼가 공정모듈에 너무 오래 머물면 장비에 남아있는 가스와 열 때문에 그 품질이 저하되기 때문이다. 그리하여 이 논문에서는 웨이퍼 지연시간을 줄이고, 더 나아가서 그것을 최소화하는 방법을 연구하였다. 이 문제를 풀기 위해 우리는 우선 로봇이 움직이는 순서가 주어졌다고 가정하고 다단계 선형계획 모델을 만들었다. 첫 번째 모델은 웨이퍼 지연조건을 만족시키는 동시에 최소 생산시간을 갖게 하는 로봇 움직임 시간들을 구하고, 두 번째 모델은 첫 번째 모델의 결과를 바탕으로 전체 웨이퍼 지연시간을 최소화한다. 그리고 우리는 분기 한정법(Branch and Bound) 알고리즘을 개발하여 웨이퍼 지연조건을 고려한 최적의 로봇 시퀀스(sequence)를 구하였다. 첫째, 우리는 기존 연구에서 습득한 동적 계획법(dynamic programming)을 이용하여 생산시간의 하한값을 찾고, 자체적으로 개발한 알고리즘으로 근접한 상한값을 구하였다. 다음, 선형계획 모델을 만들어 각 branch들이 웨이퍼 지연제약을 만족하는지 점검하였다. 이와 같이 상한값, 하한값, 실행 가능성 등 세 가지 기준으로 불리한 값을 주는 노드들을 초기에 제거함으로써 계산 효율을 크게 개선하였다. 시뮬레이션 결과로부터 볼 때, 제시한 알고리즘은 다섯 개 이상의 공정모듈 문제를 풀 때 드물게 계산 한계에 닿는 상황이 발생하였다. 이런 경우에 대비하여 우리는 heuristics를 개발하고, 그 결과값이 최적값과 비교했을 때 오류가 2%이내였음을 확인하였다.
