#Number
TR-PDS-1995-010
#Title
Control and Analysis of Real-Time Discrete Event Systems
#Author
Darren D. Cofer
#Abstract
Many man--made systems such as automated factories, traffic control systems,
communication networks, and computer programs are described in terms of
discrete--valued variables that may change in highly discontinuous ways.
These systems are called discrete event systems (DES) and are characterized by
a discrete state set and a collection of events, such as the completion of a
job or the arrival of a message. The system state changes only at time
instants corresponding to the occurrence of one of these events.
The class of DES which can be modelled by automata known as timed event graphs
are structurally related to finite state machines. Both are governed by
linear equations over a particular idempotent algebraic structure. Since
there exists a well--developed theoretical framework for studying the control
of untimed DES modelled by finite state machines, we use the structural
similarity to develop a corresponding control methodology for certain
real--time DES.
We define events in a system to be controllable if their execution may be
delayed. A behavior specification consisting of a range of acceptable
schedules for all events is controllable if the occurrence of uncontrollable
events does not cause the system to leave the specification. If a
specification is not controllable we consider the existence and computation
of a supremal (infimal) controllable subset (superset) of the specification.
We also consider behaviors specified by minimum acceptable separation times
between events. Control can be exercised by defining automata representing
the system and the specification and operating them in synchrony. In this
case we examine conditions under which the desired behavior is controllable
and, if it is not, provide conditions for the existence of an optimal
controllable behavior.
#Bib
@phdthesis{,
author = "Darren D. Cofer",
title = "Control and Analysis of Real-Time Discrete Event Systems",
school = "The University of Texas at Austin",
month = "May",
year = 1995,
note = "available via ftp or WWW at maple.ece.utexas.edu
as technical report TR-PDS-1995-010"
}