Lecture Notes #3
(Version 3.1, 2003-8-22)
(Based on the Class Note #11 of ES205 in Harvard University)
(§7.1-7.2, §8.1-8.5 of CL99 also skim chapter 9 of CL99 or Kleinrock 1975)
Mathematical models of DEDS via Generalized Semi-Markov Processes (GSMP)
Prof. Y.C. HoSpring 2001Autumn 2002 ______
1.Model of DEDS:
Untimed version
State:xX— a finite set = all possible states of the world
Event:e—a finite set = all possible happenings
Enabled Events:(x)—a subset of depending on the state x
State Transition:xnew = f(xnow, enow, randomness)
Alternative representation of state transition function is
(i)a Markov Chain Matrix Pij(e) = probability of transition from state i to state j when event e occurs ==> parametrized set of |X|by|X| stochastic matrices — a real burden
a huge literature exist on Markov Chains— a real plus
(ii)A state table — more often used when transition is deterministic, i.e., tabular data of xnew = f(xnow, enow)
MAJOR DRAWBACK OF THIS MODEL:all structural information is not retained, e.g., in a single server queue, the state can only increment and decrement by one==> the state transition probability matrix can only be tri-diagonal.
Another problem which is common with discrete states is the combinatorial explosion of the state space. Example: consider a serial queuing network which has N servers each with M limited queue spaces for waiting tasks. Server can be working, broken down, or blocked if downstream queue- space is full. How many states are there for such a DEDS? What practical application this Q-network can represent?
Note: event string serves as both input and output, finite state model (Input alphabets, Output alphabets, State space, function for state transition, Termination state)
Timed Version:
The Analog of dx/dt = f(x,u,t) for DEDS
(see Appendix B of PADEDS Ho-Cao book or ES202 )
For each enabled events in state x, we endow it with a lifetime or clock reading, c(ei), ei(x). Clock reading says “event i occurs in S,” then gets decreased until event occurs at 0. The clock readings run down at unit rate. An event is said to occur when the clock reading reaches zero. The remaining lifetime of the other events becomes the new life times in the next state if they are not disabled or interrupted.
The informal description below can be formalized using a Generalized Semi-Markov Processes framework (see Appendix B)[5]. The process is "Markov" because the state transitions as a Markov Chain; it is "semi" because the inter-event times are arbitrarily distributed (with exponential inter-event time distribution, we'll simply have a Markov process); and finally it is generalized because we can have several such processes concurrently going on to model a total system.
The TIMING and STRUCTURAL parts of the GSMP model
We define (from here to the end of this section a great deal of notations are used to explain and formalize what basically is a simple notion as illustrated on page 294 or 595 of CL99)
n=the epoch of the nth state transition
an=the nth event
xn=the nth state visited by the process: xn = x(n+)
cn=the vector of clock readings at n+
cn()=at n, the time remaining until occurs, provided(xn), the feasible event list associated with xn
N(,n) = number of instances of among a1, . . ., an[*]
Also let 1={Y(,k), , k=1,2, . .} and 2={U(,k),, k=1,2, . .} be two doubly indexed sequences of independent random variables. For each k, Y(,k) is distributed according to (the lifetime distribution of event ) and represents the kth clock sample for . The routing indicator, U(,k), is uniformly distributed on [0,1] and will be used to determine the state transition at the kth occurrence of . (In other words, 1 gives random variables time clock sample for each event, and 2 gives state transition determination for random transitions.) State transitions are determined by a mapping : X[0,1)X: if occurs in state x with routing indicator u=U(,k), then x(t) jumps to x'=(x,,u). The requirement for is that for all x,,x'
Prob((x,,u)=x') = p(x';x,)(1)
whenever u is uniformly distributed on [0,1). It is straightforward to show that with these definitions, the evolution of the trajectory x(t) of the GSMP is governed by
n+1 = n+ min {cn(): (xn)}(2)
an+1 = Arg{(xn): cn() = min {cn('): '(xn)}}(3)
N(,n+1) = N(,n)+1,=an+1
= N(,n),otherwise(4)
xn+1 = (xn, an+1, U(an+1 , N(an+1,n+1)))(5)
Equation (2) means: time of the next event = time of the last event + remaining time until the next event. Equation (3) means: the next event = the event of the enabled set that has the shortest time to occurrence from here. Equation (4) means: # of occurrences of event among the first n+1 events = old # +1, if the next event is ; old #, otherwise. Equation (5) means: the next state is a function of the last state, the next event, and a random variable determined by the next event and the # of times that event has occurred.
At each state transition the clock readings are adjusted by setting clocks for any new events and reducing the time left on any surviving “old” clocks by the time since the last transition, i.e., the duration of the state xn or the triggering event’s life time. Thus,
cn+1() = cn() - (n+1 -n) if (xn) and ≠ an+1 (6)
cn+1() = Y(, N(,n+1)+1)if (xn+1) and
either (xn) or =an+1 (7)
Equation (6) means: the current remaining time until = old remaining time if – time that has passed between then and the current event, if belongs to the enabled events at the last state xn and is not the current event n+1. Equation (7) means: if belongs to the enabled event set at n+1, and either does not belong to the enabled event set at n, or (this is the counterpart with the previous “either”) is the current event, then (this is the counterpart of the previous “if”) get its next clock value following its lifetime distribution. The reason is: if a is not enabled in the last time but enabled this time, its clock is not still ticking; if happens this time but is still enabled in the new state, we need to give a clock value to it.
The sample path x(t) is finally generated by setting x(t)=xn on [n,n+1)). x(t) is known as a Generalized Semi-Markocv Process (GSMP), the setup without the timing part with the event sequence given is known as a Generalized Semi-Markocv Scheme (GSMS).
2.Example
The M/M/1/K example model
X — the number of parts in the intermediate buffer
— { e1-departure from M1, e2-departure from M2}
(x) — {e1, e2 if x≠0 ; e1 only if x=0 ; e2 only if x=xlimit=K}
f: xnext = xnow+1 if e1
= xnow -1 if e2 and xnow≠0
c(ei) : samples from exponential distribution with rate i , i=1,2 (Note breakdown can be considered as extra long service time)
•The GSMP model of discrete event simulation
Interpretations:
- Assume server 1 and 2 are both busy at time t, with state x(t)=n. The residual service times of sever 1 and 2 are e1 and e2 respectively, and a1 is the residual arrival time to server 1 at time t.
ii.Server 2 finishes2 finishes first ( e(e2 is shorter than e1) and) andinitiates ainitiates a new service(service (e'2) at server 2 for the next customer. . At t+e2 server 1 has a remaining lifetime e'1, and, and the corresponding service completion becomes the next triggering event. . a'1 is the residual arrival time at t+e2.
• State x(t+e2) is n-1.
triggering event under state x = arg. min { c(ei) | ei(x)}
xnext = f(xnow, etriggering)
3.Relationship of DEDS models to Stochastic Processes
•A Stochastic sequences is simply an indexed collection of random variables x1, x2, . . . xi, . . .specified by its joint density function, p(x1, x2, . . . xi, . . .)p(x). However, p(x) is an n -
dimensional function representing a tremendous amount of information. Thus to simplify the burden, we can simplify by using the approximate characterization
(mean) and (correlation)
or we specialize to
Purely random sequences which requires
p(x)=ip(xi)
as product of one-dimensional functions.
Gaussian sequence which can be summarized by
.
•Markov sequence is when joint density function has the additional property
p(x(t+1)/x(t)) = p(x(t+1)/x(t), x(t-1), x(t-2), . . . .) which implies that we only need the initial density function, p(x(0)) and the transition density function, p(x(t+1)/x(t)) to specify completely the stochastic sequence
•If in addition the state of the mMarkov sequence is discrete than we have a Markov Chain and the Komogorv-Chapman equation
becomes
,
where and .
•For above discussion we implicitly assumed that time marches on uniformly in discrete time, . . .-2, -1, 0, 1, 2, . . .If on the other hand the indexing variable t is continuous, then we need to specify the event times at which the state transition take place. In other words the sequence of random variables carries two dimensions, one for the usual x, the other specifies the durations of time increment or time to the next event, and we enter the realm of the class of stochastic processes (sequences) that are special to DEDS. In other words, for each state xiwe must specify both P(x=xi) and the time to complete xi.
•If we concentrate on the distribution of the time interval between state transition, p() and simply treat the instants of transition as an “event”, then we have a renewal process if the time interval between events are independently but otherwise arbitrarily distributed. A discrete state continuous time renewal Markov process is called a Semi-Markov process, i.e. the state transitions x are Markov (imbedded Markov Chain) but the time interval between events are not (generally rather than exponentially distributed).
•Renewal Process – counts state transitions. Only restriction is state transition times are i.i.d. – only interested in “Semi” part of SMP -> only interested in time randomness / distribution.
•SMP vs. Markov: SMP allows for any general distribution of event times..
•If the events of the imbedded Markov chain are simply births and deaths with rates and , then we have the process characterized by an M/M/1 queue with
Pij=0 for |j-i|>1
If in addition pij=0 for ji then we have a pure birth process also know as a Poisson process.
•More generally, we can have state transition taking place continuously (e.g., via a stochastic differential equation), thenand then we are in the realm of ES 203.
A process or sequence is said to be stationary if the joint desnitydensity function p(x) is invariant with respect to translation of its indexing variable time. It is said to be wide sense stationary if R(t,)=R(t-).
Fr: distribution of time between transitions.
fr: is memoryless = fr geometric (if discrete time)
fr exponential (if continuous time)
Stationary –P(any set of state occurring) = P for all time (i.e. independent of time).
Wide sense stationary: correlation between two points is simply related to time interval between them.
4.Other Models of DEDS
(chsChapters 2 and 4 of CL 99. We skip this section for now and will return later when we have time. )
The example system we adopted is a simple production line consisting of two machines in tandem with one buffer storage in between and an infinite supply of raw material (parts) at the input of the first machine (Fig. 1). The output of the first machine is the input to the intermediate buffer storage and ultimately becomes the input to the second machine. Each part (job) requires a certain amount of service from the two machines in succession. The service time characteristics will be specified for each model discussed below. For example, the service time for the part on each machine can be deterministic or stochastic. The service time can also incorporate breakdown and repair durations (viewed as an extra long service time).
Fig. 1 The Two Machine System
1. The Markov Process (Chain) Model
2. The Equivalent M/M/1 Queue
3. The Generalized Semi-Markov Process (GSMP) and Discrete Event Simulation Model
4 . The Automata and Finite-State Machine Approach
The fourth approach to the same example, let us illustrate the workings of the finite-state machine model of DEDS taken from [Wonham and Ramage 1987]. We shall consider an extremely simple manufacturing system whichsystem, which is a slightly more restricted but more detailed version of the M/M/1 queue system. Consider the first server with service rate as machine M1, andthe second server with service ratemachine M2. A part (customer) is first processed by M1. Upon completion of the service at M1, it is passed onto the buffer (queue), B, where it will be picked up by M2 for further processing. The completed part leaves M2 and the system. For simplicity of the model, let us assume that the size of the buffer is one. Thus, it can be in either one of the two states, empty or full (E or F). The machines can be in any one of three possible states, “Idle - and holding no part,” “Working - and holding one part,” and “Down (broken) - and having discarded any part it was holding.” The state transition diagrams for the machines and the buffer are shown in Fig. 7. Note that from the viewpoint of queueing theory, we can regard the machines as a black box server with service times, which are a combination of working times and repair times. In this case, we can view the system as a G/G/1/1 system.
Fig. 7 State Diagrams for Machines and Buffer. Use s:u to represent the event “state work is enabled. So event “start” cannot happen from state w.
The transition between states is represented by an event, which we assume to be observable. There are four types of events in this system: “start work,” “finish work,” “machine repair,” and “broke while working.” Note that the events “start work” and “machine repair” are enabled or disabled by the control variables “u” and “v ,” respectively. Furthermore, aside from being enabled or disabled by control variables, the mechanism for determining transition from one state to another and the actual transition are assumed to be specified. While working, a machine can legally go to the idle or the down state, but it is not of primary concern in which state it actually ends up. We are required only to observe the following set of operating rules:
(i)M1 is allowed to start work only when B is empty. (This rule reflects the phenomenon of “blocking” in production lines.)
(ii)M2 can start work only when B is full.
(iii)M1 cannot start work when M2 is down.
(iv)If both M1 and M2 are down, then M2 gets repaired first.
Of the 18 (233) possible states, (i - iv) rule out the six states where M1 is either working or down and B is full. The transition diagram for the remaining 12 states is shown in Fig. 8. The primary goal of the finite-state machine approach [Wonham and Ramadge 1987] is to design controllers in such a way that the control variables “u” and “v” are enabled and disabled based on the observed information, to insure that only the legally admissible state transitions in Fig. 8 will result. Now, if the complete state of the system is observable, it is easy to implement a feedback controller. Table 1 gives the function defining the feedback controller. However, if we make the further assumption that only the events are observable (a debatable assumption if we are modeling a manufacturing system as opposed to a communication network), then we can raise the question of whether or not it is possible to implement the legal behavior of Fig. 8 based on observing the events of the system alone. One obvious solution is simply to create a copy of the system of Fig. 8 to run in parallel and in synchronism with the system. (In other words, the question is to implement the legal behavior of Fig. 8 based on observing the events of the original system. One solution is to create a copy of the original system, and set the initial states of the original and copy of the system to be the same. Then we observe the state of the copy (since we create the copy, for example, it may be a mathematical model, or simulation model, w assume that the state of the copy is observable.) and implement the appropriate control action to both the copy and the original system. This way, the two systems run in parallel and are in synchronism with each other.) This way, we can certainly implement the appropriate control action by measuring the state of the copy. The function of Table 1 and the copy of the system together are then called the “supervisor.” One last point, note that the outputs of the function in Table 1 are identical for certain states. Consequently, it is possible to reduce the state of the supervisor from 12 to 6, resulting in a state diagram for the supervisor as shown in Fig. 9. The reduced supervisor is obtained by projection from the complete supervisor and is called the “quotient supervisor.”
For those readers familiar with the control theory approach, the example of the quotient supervisor design has an immediate parallel with the Linear-Quadratic-Gaussian optimal stochastic control problem. We show the conceptual similarity in the self-explanatory suggestive diagram below in Fig. 10 (the DEDS counterparts to that of the usual CVDS are indicated in the outline font).
Fig. 8 Legally Admissible State Transitions
State / 0 / 1 / 2 / 3 / 4 / 5 / 6 / 7 / 8 / 9 / 10 / 11u1 / 1 / 1 / 0 / 1 / 0 / 1 / 0 / 0 / 0 / 0 / - / -
v1 / - / - / - / - / - / - / - / - / - / 0 / 1 / 1
u2 / 0 / 0 / 1 / 0 / 0 / 0 / 1 / - / 0 / 0 / 0 / 0
v2 / - / - / - / - / 1 / - / - / 1 / 1 / 1 / - / -
reduced
state / 0 / 0 / 1 / 0 / 3 / 0 / 1 / 2 / 3 / 4 / 5 / 5
Legend: 1 = enable, 0 = disable, - = immaterial.
Table 1 State Feedback Controller
Fig. 9 The Quotient Supervisor
Given the above description of our simple problem, we can now infor-mally state the approach of the finite state machine model. Consider a set of states Q and a set of events .Transitions between states are triggered by events and enabled/disabled by control variables. The sequence of events describes the output behavior of a system. A collection of event sequences is a language. The so-called Supervisor Control Problem is to determine whether or not a given legally admissible language can be implemented by proper manipulation of the control variables based on the observed event sequence of the system, and if so, how? The major results in this area concern the characterization of such languages and structural insight into the required controllers. A more complete description of the formalism in connection with some ideas of perturbation analysis can be found in Section 7.2. Further results dealing with analogous concepts of controllability, observability, stability, etc. from CVDS control theory in the finite state machine model setting can be found in [Wonham 1988,1989] and [Ozveren and Willsky 1991].
Fig. 10 The LQG Problem Analogy to the DEDS Supervisor Problem Obtained by Collapsing the Copy of the DEDS and the State of Feedback Controller
*Linear Quadratic Gaussian (LQG): refers to week 9&10 module.
5.Min-Max Algebra Models
The min-max algebra model [Cohen et al.1985] mainly deals with systems with deterministic events. (A recent work [Olsder et al. 1990] contains certain stochastic extensions of this model.) To illustrate this approach, we assume that the service times of machines M1 and M2 are exactly a and b, respectively. Thus, the M/M/1 queue in Fig.3 becomes a D/D/1 queue. To ensure that the queue is stable, we assume ab. The min-max algebra approach studies the transient as well as the steady-state behavior of a system. Let xn, and yn, n>0, be the n th service completion times of machines M1 and M2. Let x0 and y0 be the earliest available times of these two machines. For convenience we assume that x0=0 and that the queue length at time 0 is 0. It is easy to see that