Foundations for Discrete Event Stochastic Systems

University Of California-Berkeley, Berkeley CA

Investigators

Abstract

In simulating the resource cycles in general queuing networks, the system state can be represented by integer arrays. Running these simulations amounts to increasing and decreasing the values of elements in these arrays at specific event times. The dynamics of many of these simulations can be formulated as linear and mixed-integer programs. The solutions to the mathematical programs are identical to the state trajectories generated by running the simulation. The variables in these mathematical programs are the event times. Relationships between system events constrain these event times. The objective of the mathematical program, like in a system simulation, is to execute events as soon as possible subject to the constraints imposed by the logic and dynamics of the system. The project objective is to produce a methodology for modeling discrete event dynamic systems as combinatorial optimization problems. The approach is derived from a simulation modeling technique that was developed in an ad-hoc manner to solve specific large-scale engineering problems. This research will study the theoretical and practical foundations of this modeling methodology in a generic context. Many complex systems, including health care delivery, transportation, communication and production systems, can be effectively modeled as undergoing discrete changes that take place when particular events occur. These systems can be simulated by scheduling events on a computer that mimic the occurrences of these events in the real system. In this research, discrete event systems will be modeled using the optimization tools and techniques of operations research. This will allow the rich theory and algorithms of mathematical and stochastic programming to be applied to the modeling and analysis of this large and important class of dynamic systems.