Many automated manufacturing systems such as robotized cluster tools for semiconductor manufacturing often repeat identical work cycles and hence have cyclic behavior. There have been many works on cyclic scheduling of specific manufacturing systems. Timed Petri nets (TPN) have been used for modeling and analyzing a wide class of such manufacturing systems or discrete event dynamic systems. A manufacturing system such as a cluster tool that is operated by cyclic scheduling can be modeled by a TPN that has a cyclic token routing rule at the conflict places. Most existing works on Petri nets and TPNs have focused on structural analysis, deadlock analysis, and performance analysis. However, we wish to develop a cyclic scheduling theory and solution methods for general TPNs, which can be used for a wide class of cyclic scheduling systems and problems. In this thesis, we examine dynamic behavior of TPNs with cyclic token routing, optimization models and solution methods for scheduling, and application to cluster tool scheduling.
In Chapter 2, we examine cyclic behavior of TPNs. We first propose definitions and classifications of cyclic schedules of TPNs based on the token routing method at the conflict places and firing epochs. We then develop conditions for which cyclic schedules exist and identify marking bounds of the places for a cyclic schedule. We also develop an efficient mixed integer programming (MIP) model for finding a cyclic schedule that minimizes the cycle time. To do this, we use a state equation of the TPN model and an assignment model on ordering the transition firing epochs while most existing MIP models for cyclic scheduling of cluster tools rely on traveling salesman problems for sequencing the robot tasks.
In Chapter 3, we apply the cyclic scheduling theory and methods for TPNs to a few complex cluster tool scheduling problems. We demonstrate computation efficiency of the proposed MIP model for a tool scheduling problem, which is solved by a commercial MIP solver based on a common branch and bound procedure using linear programming relaxation. We also examine properties on initial markings of a TPN and utilize them to improve the solution search procedure for the MIP model.
In Chapter 4, we develop a specialized branch and bound algorithm for cyclic scheduling of TPNs. We branch the token routing order among the output transitions of each conflict place to define a partial relaxed solution, where the arcs from a conflict place to its output transitions that are not sequenced yet in the partial routing solution are removed. To evaluate the cycle time of a TPN with a partial token routing, we develop a systematic procedure of transforming the TPN into an equivalent timed event graph (TEG). By using the algorithm of computing the cycle time of a TEG, we efficiently compute the lower bound for the partial token routing solution. We identify significantly improved computational efficiency of a branch and bound procedure that uses the cycle time of a TPN with a partial routing as a lower bound.
오늘날 FAB에서는 물류 장비와 공정 모듈이 결합된 자동화된 생산 시스템들이 널리 사용되고 있다. 이러한 시스템들은 동일한 작업 패턴을 반복하는 주기적 운용기법을 많이 사용한다. 특히 반도체 제조용 클러스터 장비의 경우 주기적 스케쥴링 기법에 대한 연구가 활발하게 이루어져 왔다. 시간을 갖는 페트리넷 (timed Petri net, TPN)은 이러한 자동화 시스템의 모델링 및 분석에 널리 활용된다. 주기적 스케쥴을 갖는 자동화 시스템은 컨플릭트 플레이스 (conflict place)를 갖는 TPN으로 모델링 할 수 있다. 과거 연구들은 이러한 TPN 모델들로 부터 대상 시스템의 구조적 특징, 교착상태 (deadlock) 및 성능을 분석하는데 촛점을 맞추었다. 그러나, 본 논문은 일반적인 TPN 모델들을 대상으로 주기적 스케쥴 대한 이론 및 최적 스케쥴 도출을 위한 알고리즘 개발에 중점을 두었다. 본 논문에서는 TPN 모델의 주기적인 행태에 대해 분석하였으며 최적의 주기적 스케쥴을 도출하기 위한 최적화 모형 및 알고리즘을 개발하였다. 우리는 이러한 분석 결과와 스케쥴링 기법을 반도체용 클러스터 장비의 스케쥴링 문제에 응용하였다.
2장에서는, TPN의 주기적 행태에 대해 분석하였다. 먼저 TPN에서 트랜지션들의 (transitions) 파이어링 (firing) 순서 및 타이밍을 기준으로 TPN의 주기적 스케쥴에 대한 구체적인 정의와 분류 체계를 제안하였다. 또한 TPN 모델이 주기적 스케쥴을 갖게되는 조건과 주기적 스케쥴에서 각 플레이스들에 할당되는 마킹 (marking)의 변화 범위를 규명하였다. 이러한 분석을 바탕으로 TPN의 주기 (cycle time)를 최소화하는 최적의 주기적 스케쥴을 도출하는 혼합 정수 계획 (mixed integer programming, MIP) 모델을 개발하였다. 이 MIP 모델은 TPN 모델의 상태 방정식 (state equation)과 할당 모델(assignment model)을 기반으로 개발되었으며, 기존 MIP 모델들에 비해 더 빠른 시간내에 최적해를 구할 수 있다는 장점이 있다.
3장에서는, 2장에서 개발한 TPN의 주기성 분석 방법 및 스케쥴링 기법을 반도체 공정에 사용되는 클러스터 장비의 스케쥴링에 응용하였다. 클러스터 장비의 주기적 스케쥴링 문제는 TPN 모델의 주기적 스케쥴링 문제와 달리 초기 마킹을 결정해야하는 어려움이 있다. 본 논문에서는 TPN 모델의 최적 초기 마킹의 특성을 분석하였으며 이를 활용하여 `최대 마킹 전략 (maximum marking strategy)`을 제안하였다. 우리는 실험을 통해, 최대 마킹 전략이 MIP 모델의 해 탐색 효율을 크게 높일 수 있으며, 클러스터 장비의 스케쥴링에 효과적으로 활용할 수 있음을 확인하였다.
4장에서는, TPN 모델의 최적 주기적 스케쥴을 도출하기 위한 브랜치 앤 바운드 알고리즘 (branch and bound algorithm) 을 개발하였다. 우리는 어떤 TPN에 주기적 스케쥴이 주어졌을 때, 해당 TPN을 자신과 동일한 스케쥴을 갖는 시간을 갖는 이벤트 그래프 (timed event graph, TEG)모델로 변형할 수 있음을 보였다. 우리는 주기적 스케쥴을 갖는 일반적인 TPN에 적용할 수 있는 TEG로의 변환 룰을 규명하였다. 이러한 변환 룰은 브랜치 앤 바운드 알고리즘에서 부분 스케쥴 (partial schedule)의 성능을 평가하는데 활용되었다. 우리는 제안한 브랜치 앤 바운드 알고리즘을 클러스터 장비의 스케쥴링에 응용하였으며, 제안한 알고리즘이 기존의 스케쥴링 방법에 비해 매우 빠르게 해를 탐색할 수 있음을 실험을 통해 보였다.