Introduction to Discrete Event Systems

We have seen how discrete-event systems (DES) differ from continuous-variable dynamic systems (CVDS) and why DES are not adequately modeled through differential or difference equations. Our first task, therefore, in studying DES is to develop appropriate models, which both adequately describe the behavior of these systems and provide a framework for analytical techniques to meet the goals of design, control, and performance evaluation.

The situation under consideration in this chapter is that of a given DES, modeled at the untimed (or logical) level of abstraction, and whose behavior must be modified by feedback control in order to achieve a given set of specifications. This is reminiscent of the feedback control loop introduced in Chapter 1, in Section 1.2.8. Let us assume that the given DES is modeled by automaton G, where the state space of G need not be finite. Let E be the event set of G. Automaton G models the “uncontrolled behavior” of the DES. The premise is that this behavior is not satisfactory and must be “modified” by control; modifying the behavior is to be understood as restricting the behavior to a subset of £(G). In order to alter the behavior of G we introduce a supervisor, supervisors will be denoted by S. Note that we separate the “plant” G from the “controller” (or supervisor) S, as is customary in control theory. This raises two questions: (a) What do we mean by specifications? and (b) How does S modify the behavior of G?

An alternative to automata for untimed models of DES is provided by Petri nets. These models were first developed by C. A. Petri in the early 1960’s. As we will see, Petri nets are related to automata in the sense that they also explicitly represent the transition function of DES. Like an automaton, a Petri net is a device that manipulates events according to certain rules. One of its features is that it includes explicit conditions under which an event can be enabled; this allows the representation of very general DES whose operation depends on potentially complex control schemes. This representation is conveniently described graphically, at least for small systems, resulting in Petri net graphs; Petri net graphs are intuitive and capture a lot of structural information about the system. We will see that an automaton can always be represented as a Petri net; on the other hand, not all Petri nets can be represented as finite-state automata. Consequently, Petri nets can represent a larger class of languages than the class of regular languages, R. Another motivation for considering Petri net models of DES is the body of analysis techniques that have been developed for studying them. Such techniques cover not only untimed Petri net models but timed Petri net models as well; in this regard, we will see in the next chapter that there is a well-developed theory, called the “max-plus algebra,” for a certain class of timed Petri nets (cf. Section 5.4). Finally, we mention that Grafcet, the widely-used programming language for programmable logic controllers (or PLCs) used in industrial automation, is inspired by Petri nets.

From this point on we will concentrate on timed models of DES. This means that the sample paths we consider can no longer be specified as event sequences {e ₁, e ₂,...} or state sequences {x ₀, x ₁,...}, but they must include some form of timing information. For example, let, t _k , k = 1, 2,..., denote the time instant when the kth state transition occurs (with to given); then a timed sample path of a DES may be described by the sequence {(x ₀, t ₀), (x ₁, t ₁),...}. Creating a framework for timed DES models will enable us to address questions such as “how many events of a particular type can occur in a given time interval?”, or “how long does the system spend in a given state?” These issues are of critical importance in analyzing the behavior of DES such as computer systems and communication networks, since they provide us with particularly useful measures of system performance.

In practice, systems always operate in environments which are constantly plagued by uncertainty. This is especially true in dealing with DES, which, by their nature, often involve unpredictable human actions and machine failures. The process of resource sharing (which provides an important motivation for studying DES) is inherently characterized by such unpredictability: changing user demand, computer breakdowns, inconsistencies in human decision making, etc. While the untimed (or logical) models considered in Chapters 2 to 4 do account for “all possible behaviors” of the system, their use is limited to logical (or qualitative) performance objectives. Deterministic timed models of the type considered in Chapter 5 certainly contribute to our basic understanding of some quantitative properties of the dynamic behavior of a system (for instance, the periodic behavior of systems that can be modeled as marked graphs). But their use is limited since models with deterministic clock structures only capture a single timed string of events (or states), or, in other words, a single sample path of the system. If we are to develop either descriptive or prescriptive techniques for evaluating performance and for “optimally” controlling timed DES with respect to quantitative performance measures and in the presence of uncertainty, more refined models that incorporate stochastic elements are required.

A simple queueing system was first introduced in Chapter 1 as an example of a DES. We have since repeatedly used it to illustrate many of the ideas and techniques discussed thus far. In this chapter, we will take a more in-depth look at queueing systems.

In Chapter 7 we considered Markov chains as a means to model stochastic DES for which explicit closed-form solutions can be obtained. Then, in Chapter 8, we saw how special classes of Markov chains (mostly, birth-death chains) can be used to model queueing systems. We pointed out, however, that queueing theory is largely “descriptive” in nature; that is, its main objective is to evaluate the behavior of queueing systems operating under a particular set of rules. On the other hand, we are often interested in “prescriptive” techniques, based on which we can make decisions regarding the “best” way to operate a system and ultimately control its performance. In this chapter, we describe some such techniques for Markov chains. Our main objective is to introduce the framework known as Markov Decision Theory, and to present some key results and techniques which can be used to control DES modeled as Markov chains. At the heart of these techniques is dynamic programming, which has played a critical role in both deterministic and stochastic control theory since the 1960s. The material in this chapter is more advanced than that of previous ones, it involves some results that were published in the research literature fairly recently, and it demands slightly higher mathematical sophistication. The results, however, should be quite gratifying for the reader, as they lead to the solution of some basic problems from everyday life experience, or related to the

In our study of dynamic systems, our first goal is to obtain a model. For our purposes, a model consists of mathematical equations which describe the behavior of a system. For example, in Chapter 5 we developed the set of equations (5.7)–(5.12) which describe how the state of a DES evolves as a result of event occurrences over time. Our next goal is to use a model in order to obtain explicit mathematical expressions for quantities of interest. For example, in Chapter 7 our model was a Markov chain and the main quantities of interest were the state probabilities π_j(k) = P[X _k = j], j= 0, 1, ... In some cases, we can indeed obtain such expressions, as we did with birth-death chains at steady state in Section 7.4.3. In general, however, “real world” systems either do not conform to some assumptions we make in order to simplify a model, or they are just too complex to yield analytical solutions. Our mathematical model may still be valid; the problem is that we often do not have the tools to solve the equations which make up such a model. Simulation is a process through which a system model is evaluated numerically, and the data from this process are used to estimate various quantities of interest. As we have repeatedly pointed out in previous chapters, analytical solutions for DES are particularly hard to come by, making simulation a very attractive tool for their study.

After going through all the previous chapters, it would be natural for readers to conclude that DES are inherently complex and hard to analyze, regardless of the modeling framework adopted. It would also be natural to wonder whether there are any properties at all in DES that we can exploit in our effort to develop mathematical techniques for analysis, design, and control.