Discrete event systems, including automated manufacturing systems such as cluster tools for semiconductor manufacturing, microcircuits, and real-time embedded software systems, often have strict time window constraints between pairs of events. Such systems are often operated so that each component or module repeats a predetermined identical work cycle or sequence. Such cyclic operation has advantages of simplicity, predictability, and better optimization. To model and analyze such time constrained decision-free discrete event systems, Lee and Park [1] pro-posed an extended event graph called negative event graph that generalizes notions of places and tokens by introducing negative places and tokens with negative token holding times and negative token counts, respectively, to represent time window constraints. For such negative event graphs, they derived necessary and sufficient conditions based on circuits for which a feasible schedule exists.
In this thesis, we further extend the negative places and tokens to model more general time constraints so that negative places and conventional positive places allow conventional positive tokens and negative tokens, respectively. We call such an extended framework a generalized negative event graph(GNEG). We also propose new improved enabling and firing rules that can explain dynamic state evolution of such extended net model. Under a more general setting than the one for the negative event graph, we prove that the liveness condition similar to that for the negative event graph also holds for the extended model. We also identify the similar feasible cycle time range and present an application to scheduling a cluster tool with intermediate buffers.
Second, a timing control and implementation problem for decision-free discrete event systems with general time constraints is discussed. Even if a system turns out to be schedulable from the liveness condition of a GNEG, the conventional timing control method, which starts each event as soon as it is enabled, may violate the time constraints. Therefore, it is desirable to make each event start as soon as possible while satisfying time window constraints. We call such a schedule feasible earliest-starting schedule. In order to make the system follow such a feasible earliest-starting schedule, it is desirable to control the occurrence timing of each controllable event as soon as the preceding events occur. Such even-based timing control keeps the logical precedence between the events even when there are time variations or disruptions in real-implementation. It also simplifies schedule implementation by using token play of the Petri-net model instead of computing the schedule in advance, deliberately keeping tracking of the timings of the events, and adjusting the timings of the controllable events. In order to identify a feasible earliest-starting schedule and implement it by the event-based timing control, we propose the use of a timed event graph model derived from the GNEG model, of which earliest starting generates a feasible earliest-starting schedule.
Finally, we propose a generalized negative Petri-net (GNPN) which includes negative places, negative tokens, and negative arcs as well as traditional positive places, positive tokens, and positive arcs. We allow a negative place to have multiple input and output transitions and add negative arcs to a GNEG. The net is therefore not decision-free in the sense that a conflict place should have token routing decisions. A negative arc is introduced to generalize conventional roles of arcs in a Petri-net. When a transition fires, such a negative arc works only for changing the tokens at its input positive place or output negative place without transferring enabling effects. Negative arcs further generalize enabling and firing behaviors of Petri-nets so that a transition can be enabled and fired without sufficient number of positive tokens or the system can keep firing after a time constraint is violated. We present modeling and application examples of negative arcs such as credit purchasing, orders and inventory models, and processing wafers with excessive time delays within a chamber.
반도체 제조를 위한 클러스터 툴, 마이크로 서킷, 실시간 소프트웨어 시스템 등과 같은 자동화된 생산 시스템을 포함하는 이산사건 시스템은 아주 엄격한 시간 제약(time window constraint)을 가지는 경우가 많다. 그러한 시스템들은 보통 미리 일의 순서를 정해두고 이를 반복하여 운용하는 경우가 많다. 이러한 주기적 운용방법은 운용이 단순하면서도 좋은 성능을 나타내고 미래의 시스템 상태를 예측하는 것이 용이한 장점이 있다. 주기적으로 운용되는 이산사건 시스템에 시간 제약이 있는 경우 이를 모델링 및 분석하기 위하여 Lee and Park[1]은 기존의 페트리 네트의 요소인 플레이스와 토큰을 확장한 네거티브 플레이스와 네거티브 토큰을 제안하고 모든 시간 제약을 만족하는 지의 여부(liveness)를 판별할 수 있는 조건을 제시한 바 있다.
본 논문에서는, 이를 더욱 확장하여 일반적인 시간제약을 갖는 이산사건 시스템을 모델링 및 분석하기 위한 일반적인 네거티브 이벤트 그래프(generalized negative event graph: GNEG)의 프레임워크를 제안한다. GNEG에서는 파지티브 플레이스가 네거티브 토큰을 갖는 것과 네거티브 플레이스가 파지티브 토큰을 갖는 것을 허용한다. 우리는 확장된 GNEG의 동적 상태 변화를 적절히 설명할 수 있는 개선된 이네이블링(enabling) 규칙과 파이어링(firing) 규칙을 개발하였다. 또한 일반화된 시간제약을 허용함에도 불구하고 liveness 조건이 기존의 조건과 유사하다는 사실을 증명하였고 가능한 사이클 타임의 구간을 구하였다.
두번째로, 일반적인 시간제약이 있는 이사사건 시스템의 타이밍 제어와 구현 방법을 연구하였다. 주어진 GNEG가 앞서 구한 liveness 조건에 따라서 라이브 하다고 판명이 되었다 하더라도, 기존의 타이밍 제어 방법인 earliest start(각 사건을 발생가능한 구간 중 가장 빠른 시간에 발생 시키는 방법)를 채택하는 경우 시스템은 라이브하지 않은 상태로 빠질 수 있다. 이는 미래에 어긋날 가능성이 있는 시간 제약을 만족시키기 위해 어떤 사건이 적절히 지연되어야 함에도 불구하고 이를 지키지 않았기 때문이다. 우리는 모든 시간제약을 지키면서도 각 사건들을 가장 빠른 시간에 발생시키는 스케줄을 feasible earliest starting 스케줄이라 명명하였고, feasible earliest starting 스케줄을 타임 테이블 방식이 아닌 이벤트 기반 제어 방식으로 구현할 수 있도록, 주어진 GNEG를 동일한 의미를 갖는 TEG로 변환시키는 방법을 제안하였다.
마지막으로, 기존의 파지티브 플레이스, 토큰, 아크와 더불어 확장된 요소인 네거티브 플레이스, 토큰, 아크를 갖는 일반화된 네거티브 페트리 네트(generalized negative Petri-nets: GNPNs)를 제안하였다. 첫째로, 기존의 GNEG에서는 하나의 네거티브 플레이스가 복수의 인풋, 아웃풋 트랜지션을 갖는 것을 허용하지 않았던 데 반하여, GNPN에서는 이를 허용함으로써 셋 이상의 사건들 간에 걸린 시간 제약을 모델링 할 수 있도록 하였다. 이는 의사결정이 내려지지 않은 이산사건 시스템에 시간제약이 있을 경우도 모델링 할 수 있을을 의미한다. 네거티브 플레이스와 네거티브 토큰의 좀더 엄밀한 의미와 쓰임새도 실제 시스템의 예를 들어 설명하였다. 둘째로, 새로운 페트리 네트의 요소인 네거티브 아크를 제안하였다. 플레이스와 트랜지션이 기존의 파지티브 아크로 연결된 경우, 트랜지션은 플레이스로부터 enabling 또는 disabling 효과를 받고 트랜지션이 발생 후에는 플레이스는 토큰의 변화를 일으키게 된다. 이에 반하여 네거티브 아크로 연결된 경우 플레이스는 enabling 또는 disabling 효과를 전달하지 못하고 오직 트랜지션으로부터 토큰의 변화만을 일으키게 된다. 네거티브 아크를 이용하여 기존에는 모델링이 불가능하였거나 아주 복잡했던 관계들을 아주 효율적으로 모델링할 수 있다. 제안한 GNPN은 기존의 페트리 네트의 각 요소들에 대응하는 네거티브 요소들을 좀더 완전하게 정의하고 그 의미를 해석한 데에 그 가치가 있다.
