Many discrete event systems are subject to time constraints. For instance, in a cluster tool for semiconductor manufacturing, a wafer processed at a processing chamber should leave the chamber within a time limit. Otherwise, the wafer undergoes a severe quality problem due to residual gases or heat in the processing chamber. Hoist-based processing systems for printed circuit board manufacturing, microcircuits like digital signal processing, and real-time software systems also have similar time constraints. Such time constraints make scheduling decisions complicated. The critical scheduling issues include how the system with time constraints is modeled, whether there exists a feasible schedule that satisfies all time constraints, how a feasible schedule is identified or computed, and how the timings of the activities are controlled. There have been attempts for addressing some of the scheduling issues, including p-time Petri nets, PERT-like graph models, and linear programming models. Petri nets are known to be useful for modeling and analyzing discrete event dynamic systems. An interesting question is whether or how the Petri nets can be extended for addressing the time constraints. While p-time Petri nets or PERT-like graphs propose some extension, we still need a more unified Petri net theory that can model and analyze time constrained systems more systematically. To do this, places and tokens that are essential for representing the conditions and states of discrete event systems should be extended.
In this thesis, we propose an extended event graph that can model and analyze decision-free discrete event systems with general time window constraints. To do this, we introduce places with negative holding times and tokens with negative token counts into a timed event graph. Such an extended graph is called a negative event graph(NEG). We define enabling and firing rules for NEGs and develop the theory for analyzing NEGs. We first examine the liveness of an NEG, that is, whether there exists a feasible firing schedule that satisfies all time constraints. We develop a necessary and sufficient condition based on the circuits of the NEG. We prove that the minimum cycle time is the same as the maximum circuit ratio of the circuits with positive token counts. We also show that when there exists circuits with negative token counts, the maximum cycle time is bounded and the same as the minimum circuit ratio of such circuits. We also discuss how a linear programming model and an NEG can be related. We present an application of the theory for scheduling a cluster tool with wafer delay constraints.
Second, we discuss the steady state analysis of the earliest firing schedule that satisfies the time constraints. In fact, the earliest firing schedule delays the firing epoch appropriately after each transition is enabled. We develop a recurrence equation for the earliest feasible firing epochs by using the minimax algebra. We then show how the steady states or steady earliest firing schedules can be identified and computed. We also show that the latest feasible firing schedule can be computed by a similar method. All these schedules have the minimum cycle time. Finally, it is shown that the earliest and latest firing schedules can be computed for the maximum cycle time.
Finally, we develop an event-based timing control method that fires each transition as soon as possible but satisfies the time constraints. To do this, we modify the NEG by adding some places. By token play of such a modified NEG, the system is controlled to satisfy the time constraints. We present a way of systematically adding such places.
최근 많은 이산사건 시스템에서 시간제약(time window constraint) 조건이 존재한다. 예를 들어, 반도체 제조장비인 클러스터 장비의 경우, 공정이 끝난 웨이퍼는 일정한 시간 범위 내에 공정모듈을 떠나야 한다는 제약을 가진다. 이 제약을 만족시키지 못할 경우 공정모듈의 잔존 가스와 열로 인해 웨이퍼에 심각한 품질 문제가 발생된다. 인쇄 회로 기판의 제조 공정장비인 호이스트 장비나 디지털 신호 처리에서의 마이크로서킷, 실시간 소프트 웨어에서도 유사한 시간제약의 예를 찾을 수 있다. 이러한 시간 제약들은 시스템의 스케줄링 문제를 복잡하게 만드는데, 이때 중요한 이슈는 어떻게 시간제약 조건을 모델링 할 것인가, 시스템의 모든 시간제약을 만족하는 가능 스케줄(feasible schedule)이 존재하는가, 어떻게 가능 스케줄을 얻어낼 수 있는가, 얻어낸 스케줄이 있다면 그에 맞추어 어떻게 제어할 수 있는가 하는 문제들이다. 시간제약이 있는 시스템의 스케줄링 문제를 다루는 경우로 p-time Petri net이나 PERT-like 그래프, 선형 계획법 등이 연구되어왔다. 한편, 시간제약이 없는 경우의 이산사건 시스템의 모델링과 분석에는 이미 많은 이론이 분석된 Petri net이 많이 사용되어 왔었다. 이러한 측면에서 Petri net에 시간제약을 모델링하는 방안이 이슈가 되어왔다. p-time Petri net에서 일부 진전이 있었지만, 시간제약이 있는 시스템을 좀더 체계적으로 Petri net으로 모델링 하여, 기존의 Petri net이론들을 통합적으로 확장 할 수 있는 확장된 Petri net이론이 요구되어왔다. 특히, 시스템의 동적 행태를 잘 표현하는 Petri net의 요소인 플레이스(place)와 토큰(token)의 확장이 필요하였다.
본 논문에서는 일반적인 시간제약(generalized time window constraint)을 가진 decision-free인 이산 사건 시스템의 모델링을 위한 확장된 이벤트 그래프를 제안한다. 제안한 그래프는 네거티브 홀딩 타임을 가지는 네거티브 플레이스와 네거티브 토큰을 도입하였고, 이 그래프를 네거티브 이벤트 그래프(Negative event graph;NEG)라고 명명하였다. 첫째로, enabling rule과 firing rule을 정의하고, NEG의 라이브(가능 스케줄의 존재여부)에 대한 필요충분조건을 NEG 내에 존재하는 회선(circuit)에 대한 조건으로 구하였다. 최소 사이클 타임은 포지티브 토큰 수를 갖는 회선 중에 최대비(maximum circuit ratio)와 같게됨을 증명하였다. 이러한 방법으로 시간제약이 있는 시스템의 병목구간이 어디인지를 파악하는 것이 가능하다. 네거티브 토큰 수를 갖는 회선이 있을 경우는 최대 사이클 타임이 제한됨을 보이고 이때의 최대 사이클 타임은 네거티프 토큰 수를 갖는 회선 중에서 최소비(minimum circuit ratio)와 같음을 보였다. 주기가 1인 스케줄인 경우, NEG와 선형계획모델과의 관계도 분석하였다. 시간제약 시스템 분석의 예로 클러스터 장비를 설명하였다.
둘째로, 라이브한 NEG에 대한 안정상태 분석을 하였다. 기존의 이벤트 그래프에서는 earliest firing 전략에서 안정상태가 존재하는 것이 알려져 있었으나, 이 earliest firing 전략이 NEG에서는 경우에 따라 시간제약을 만족하지 못함을 설명하고, NEG에 맞는 새로운 전략인 earliest feasible firing 전략을 제시하였다. 이 전략은 시간제약을 만족하는 시점 중에서 가장 이른 시점에 firing을 하는 것을 의미한다. 이러한 전략하에서 max-plus 대수를 이용하여 안정상태가 존재함을 보이고, 그 스케줄을 구하는 방법을 제시하였다. 이벤트 그래프와는 달리 최소 사이클 타임 뿐만아니라 최대 사이클 타임에서도 안정상태가 존재함을 보였다. latest firing 전략은 기존의 이벤트 그래프에서는 의미가 없었으나, NEG에서는 시간제약이라는 조건에 의해 의미가 있음을 설명하고, latest feasible firing전략을 제시하였다. earliest feasible firing 전략과 유사한 방안으로 latest feasible firing에서도 안정상태의 존재성을 보이고 그때의 스케줄을 min-plus 대수를 이용하여 구하였다.
마지막으로, 라이브한 NEG에 대해 earliest firing을 하더라도 시작제약을 만족할 수 있도록 하는 이벤트 기반의 제어 방안을 제시하였다. 즉, earliest firing을 하더라도 earliest feasible firing이 가능하도록 하는 제어 방안을 제시하였다. 이를 위해 원래의 NEG에 플레이스들을 추가하는 방안을 제안하였고, 어떻게 그러한 플레이스들을 체계적으로 추가할 수 있는지를 논하였다. 수정된 NEG에서 earliest firing 전략하에서 시간제약을 만족하는 이벤트 기반의 토큰 플레이가 가능하게 되었다. 이 방법을 이용하면 수정된 NEG가 시간제약이 있는 이산 사건 시스템의 제어 모듈로 사용될 수 있고, 동적인 행태 또한 분석이 가능하다.
