A natural class of mathematical models for modern automated manufacturing systems such as semiconductor wafer fabricators and service system is queueing network. There have been many studies to analyze such systems, but exact analysis is hard to be applied as the system becomes complicated. While performance bounds, simulation and approximations are employed to provide useful information for the system, but do not completely characterize the steady state behavior.
In this dissertation, two queueing models are analyzed with exact method. We obtain Markov chain models for the systems, thus the equilibrium probabilities can be obtained. First, flow line models, also called tandem queue, are analyzed. Flow line models have been studied for decades, but there have been few exact results on their steady state behavior. For flow lines with at most three server, some exact steady state results have been obtained, however they cannot be extended to allow for more servers. As such, approximations based on aggregation or decomposition methods are generally employed. By focusing on flow lines with deterministic service durations,
we conduct exact analysis for the system. We focus on two performance metrics: equilibrium probability for delay in each servers and maximum production rate. Each will be studied with different assumptions.
For the equilibrium probability for delay in each servers, we start with the investigation of recursions for customer delay based on exact decomposition methods. We demonstrate that the delay a customer faces in each server possesses a Markovian property. For discrete-time flow lines, we obtain a multidimensional discrete-time time-homogeneous Markov chain for the delays; there are an infinite number of balance equations for the equilibrium probabilities. Exploiting a similarity between our system and the GI/D/1 queue allows us to reduce these to a finite number of balance equations that can be solved numerically. To our knowledge, these are the first exact results which can be applied to flow lines consisting of more than three servers.
Considering classes of random state-dependent setups between customers, we next focus on the maximum production rate, or just-in-time (JIT) throughput. We consider various cases, deduce when exact closed form expressions for the production rate are possible and when a numeric solution to the Markov chain balance equations are required. As these systems have shown promise for modeling process bound clustered photolithography tools in semiconductor manufacturing, we study their accuracy versus detailed simulation for predicting the tool throughput. Various practical features such as the capacity of a pre-scan buffer and batch customers (to model wafer lots) are investigated.
Second, we analyze two station closed reentrant queueing networks under the last buffer first served policy. Excepting the well-known product
form networks (e.g. Jackson, Kelly and BCMP networks), there are few multiclass queueing networks that admit explicit solutions for their equilibrium probabilities.
Even though networks possess a finite state space, and thus the equilibrium probabilities can be found directly from the global balance equations, it is practically impossible to obtain the equilibrium probabilities as the number of trapped customers increases. By restrict our focus on a class of two station closed reentrant queueing networks, we obtain closed form expressions for the equilibrium probability
distribution under the last buffer first served policy. We show that the equilib
rium probabilities can be expressed as a linear combination of powers of roots
of the characteristic polynomial of a matrix derived from the global balance
equations. To our knowledge, this is the first class of queueing networks for
which explicit non-product form solutions can be constructed.
제조 공정이 복잡해지고 그 분석의 중요성이 증대됨에 따라, 반도체 웨이퍼 공정과 같은 자동 제조 시스템들을 수학적으로 분석하기 위한 시도들이 늘어나고 있다. 이러한 자동 제조 시스템을 수학적으로 모델링하는데 가장 많이 사용되는 모델 중의 하나가 대기행렬 네트워크이다. 이러한 대기행렬 네트워크들은 오랜 시간동안 연구되어져 왔지만, 일반적으로 네트워크가 복잡한 형태를 띄게 될수록 정확한 분석이 불가능하게 된다. 그렇기 때문에, 일반적으로 이러한 시스템을 분석하는데 성능척도 상,하한이나 근사해법을 통한 근사해가 사용된다. 이러한 정보들은 유용하지만, 모델의 안정상태에서의 행태에 관한 정확한 정보를 제공하지 못한다. 정확한 정보를 통해서, 우리는 모델의 정확한 행태를 이해할 수 있고, 이러한 정보는 정확한 정보 뿐 아니라, 새로운 근사해법을 개발하기 위한 기반이 되기도 한다.
이 논문에서는 정확한 분석을 통하여, 두 대기행렬 모델이 분석된다. 우리는 마코브 체인 모델을 얻고 따라서 안정상태 확률을 계산해낼 수 있음을 보인다. 첫번째로, 일렬 대기행렬 네트워크, 또는 플로우 라인 모델를 분석한다. 일렬 대기행렬 네트워크는 오랜 시간 연구되어 왔지만, 대개의 경우 3개 이상의 서버로 구성될 경우, 정확한 분석을 통해 해를 얻는 것은 불가능하다고 생각되어져 왔다. 우리는 결정적인 서비스 시간을 갖는 서버로 구성된 일렬 네트워크의 성능척도들을 정확한 분석을 통해 구하게 된다. 우리의 두가지 주요 성능척도는 각 서버 안에서 고객이 경험하는 대기시간의 안정상태 확률과 시스템의 단위시간당 최대 처리량이다. 우리는 각각의 성능척도에 대하여, 마코브 체인 모델을 통한 분석을 수행한다. 특별히, 단위시간당 최대 처리량을 다루는 모델에서는 실제 반도체 공정에서 발생하고 있는 다양한 형태의 셋업을 고려한 모델을 분석한다. 먼저 각각의 시스템에 대하여, 우리는 마코브 특성을 발견하고, 이를 통하여 마코브 체인 모델을 통하여 안정상태의 성능척도에 대한 정보를 얻어낸다. 기존의 모델들에서 사용되던 분석법들이 서버가 3개 이하일 때만 사용할 수 있었다면, 우리의 분석법은 서버 세 개 이상의 대기행렬 모델에서도 정확한 해를 얻을 수 있는 첫 번째 분석방법이라는 데에 의의가 있다.
또한 우리는 2개의 서버로 이루어진 닫힌 재진입 대기행렬 네트워크를 분석한다. Jackson, Kelly 그리고 BCMP 네트워크와 같이 product form의 안정상태 확률을 갖는 대기행렬 네트워크를 제외하고는 안정상태 해의 형태를 closed form으로 도출 해 낼 수 있는 네트워크는 이제까지 알려진 바가 없다. 우리는 2개의 서버로 이루어진 닫힌 재진입 대기행렬 네트워크에 대한 분석을 통해, 특정 버퍼 우선 정책 하에서 non-product form 형태의 해를 도출해 낼 수 있음을 보인다. 마지막 버퍼 우선 정책 하에서, 안정상태 확률은 상태 방정식의 행렬형태에서 얻은 행렬식의 해로 이루어진 선형결합의 형태를 띄게 된다. 이는 non-product 형태의 해를 구할 수 있는 첫 번째 대기행렬 네트워크이다.
