Modeling and analysis of extended petri nets for discrete event systems with general time constraints

Abstract

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...