Clustering technology is usually used in recent semiconductor industry to prevent several sequential process steps from exposing to air and to achieve better productivity of equipment. The equipment that performs two or more sequential processes in a single unit is called integrated single-wafer processing tools. The typical examples of the integrated single-wafer processing tools are cluster tools and photolithography processing tools. The trend toward the integrated single-wafer processing tools in wafer fabs accelerates the necessity of a sophisticated and dedicated scheduler that can manage them more autonomously and flexibly.
Thus, this dissertation addresses crucial problems for real-time scheduling of the semiconductor integrated single-wafer processing tools. The first part of this dissertation proposes the deadlock-free scheduling approach that can perform real-time scheduling and deadlock management in efficient way for the integrated single-wafer processing tools in spite of dynamic contingencies. First, a novel framework is introduced where deadlock management problem is decomposed into sub-problems for computational efficiency, and then they are integrated with real-time scheduling algorithms. In other words, deadlock-prone modules and deadlock-safe modules are identified in the context of the deadlock management, and then only deadlock-prone modules are focused to guarantee deadlock-freeness when scheduling algorithms are applied to the entire modules. To realize the proposed framework, a Resource Request Matrix is newly introduced to represent operational states. The Resource Request Matrix is a representation useful in identifying deadlock-prone modules and applying deadlock management algorithms, because deadlock conditions are expressed explicitly in this representation. This dissertation also presents algorithms with polynomial complexity to identify deadlock-prone modules, and algorithms to manage deadlock considering machine failures.
The second part of this dissertation considers the real-time scheduling problem of the integrated single-wafer processing tools with temporal constraints. Certain chemical processes require that wafer-flow satisfies temporal constraints, especially, post-processing residency constraints, for the high qualities of the wafers produced. Thus, this dissertation proposes a real-time scheduling algorithm to cope with this problem. First, this scheduling problem with temporal constraints is modeled using temporal constraints sets. This formalism relies on a point-based representation of time, and allows a set of unary and binary temporal constraints. Each temporal constraint specifies a set of time intervals. Then, a real-time scheduling algorithm with polynomial computational complexity is presented. The on-line scheduling algorithm consists of two procedures, i.e., FEASIBLE_SCHED_SPACE and OPTIMAL_SCHED. The FEASIBLE_SCHED_SPACE finds feasible solution space for a newly inserted wafer into the integrated single-wafer processing tool, which guarantees both logical and temporal correctness. The OPTIMAL_SCHED computes the optimal solution among the feasible solution space obtained in the previous phase. The objective of the scheduling is to minimize the completion time of the last operation of the wafer. Each procedure is proved to have computational complexity of O($N^5$) and O($N^4$), respectively, where N denotes the number of process modules in the integrated single-wafer processing tools.
반도체 웨이퍼 생산 산업에서 연속되는 여러 단계의 공정을 하나의 장비에서 수행하도록 통합하는 것은, 생산되는 웨이퍼의 질과 생산성을 높일 수 있기 때문에 그 사용이 점차 증가하는 추세다. 이러한 반도체 통합 장비의 대표적인 예로는 클러스터 툴이나 사진공정을 담당하는 트랙 장비 등을 들 수 있다. 본 논문은 반도체 통합 장비의 실시간 스케쥴링 방법에 대한 연구로서, 특히 교착상태 회피 방법과 가공 후 체류시간 제약이 있는 실시간 스케쥴링 방법을 포함한다.
논문의 전반부에서는 교착상태 회피 알고리즘과 실시간 스케쥴링 알고리즘을 효율적으로 적용할 수 있는 프레임워크 제시하며, 프로세스 모듈의 고장 등 동적으로 변하는 환경에서 효과적으로 교착상태를 회피하는 알고리즘을 제시하는 것을 목적으로 한다. 즉, 반도체 통합 장비 내의 프로세스 모듈들을 교착상태가 일어날 수 있는 프로세스 모듈과 교착상태가 일어나지 않는 프로세스 모듈로 나눈 후, 교착상태 회피 알고리즘은 교착상태가 일어날 수 있는 모듈에만 적용하며 실시간 스케쥴링 알고리즘은 교착상태에 상관 없이 모든 프로세스 모듈에 통합적으로 적용한다. 반도체 통합 장비에서 교착상태를 효과적으로 예측하고 회피하기 위하여, 본 논문에서는 시스템의 상태를 표현하기 위한 방법으로 Resource Request Matrix를 이용한 표현 방법을 제시한다. 제안된 Resource Request Matrix 표현 방법은 교착상태의 명시적 표현이 가능하기 때문에, 교착상태가 일어날 수 있는 모듈을 찾고 교착상태 회피 알고리즘을 설계하는데 효과적으로 이용된다. 본 논문에서는 이러한 Resource Request Matrix의 특성을 이용하여, 교착상태가 일어날 수 있는 프로세스 모듈과 교착상태가 일어나지 않는 프로세스 모듈로 나누는 알고리즘과 교착상태 회피 알고리즘을 제시한다.
양질의 웨이퍼를 생산하기 위해서는, 오버 베이킹 또는 화학 약품에 장기간 노출되는 문제 등으로 인하여, 프로세스 모듈에서 웨이퍼 가공 후 체류시간에 제약이 있는 경우가 있다. 논문의 후반부에서는 이와 같은 시간 제약이 있는 반도체 통합 장비에서 실시간 비주기 스케쥴링 방법을 제시하는 것을 목적으로 한다. 가공 후 체류시간의 제약을 만족시키는 실시간 스케쥴링 문제를 다루기 위하여, 본 논문에서는 temporal constraint sets formalism을 이용하여 시간 제약이 있는 스케쥴링 문제를 정형화 한 후, 시간 제약을 만족시키는 비주기 스케쥴을 실시간으로 생성하는 다항식 알고리즘을 제안한다. 제안된 실시간 스케쥴링 알고리즘은 FEASIBLE_SCHED_SPACE와 OPTIMAL_SCHED의 두 단계로 구성되어 있다. 전자는 유효한 스케쥴의 시간 영역을 구하며, 후자는 구해진 유효한 시간 영역 중에서 웨이퍼의 마지막 가공이 끝나는 시간을 최소화하는 스케쥴을 결정한다.
반도체 통합 장비의 스케쥴링에서 교착상태 회피 문제와 시간 제약이 있는 스케쥴링 문제는 자동화 및 양질의 웨이퍼 생산을 위해 반드시 해결해야 하는 문제다. 본 논문에서는 특히 프로세스 모듈의 고장에 대처가 가능하고 갑자기 투입되는 웨이퍼의 처리 등 예외상황에 유연한 실시간 스케쥴링 문제에 초점을 맞추고 있다. 본 논문에서는 교착상태를 효과적으로 예측하고 회피하기 위하여 Resource Request Matrix 표현 방법을 새롭게 제시하였으며, 이를 이용한 교착상태 회피 알고리즘을 제안하였다. 또한, 시간 제약이 있는 스케쥴링 문제에 대하여 기존의 연구들은 오프라인에서 주기적인 스케쥴을 구하는데 비하여, 본 연구에서는 온라인에서 비주기 스케쥴을 구하는 알고리즘을 제안하였다. 제안된 방법들은 프로세스 모듈의 고장이나 갑자기 투입되는 웨이퍼에 유연하게 대처가 가능하다는 장점이 있다.
