Font Size: a A A

Mathematical programming representations of discrete-event system dynamics

Posted on:2006-07-14Degree:Ph.DType:Dissertation
University:University of California, BerkeleyCandidate:Chan, Wai KinFull Text:PDF
GTID:1458390008451394Subject:Operations Research
Abstract/Summary:
This dissertation presents a methodology for modeling discrete-event system dynamics as mathematical optimization problems and discusses a variety of applications.; Discrete-event systems are dynamic systems in which the state changes in accordance with the occurrence of events. Discrete-event systems are common in many sectors of modern society; examples can be found in areas as diverse as manufacturing, transportation, telecommunication, computing, and finance. These systems are often too complex to yield exact analytical results. Computer simulation---with the power to model system dynamics and randomness---is one of the most popular tools for studying the behavior of discrete-event systems. In mathematical programming, people have developed techniques and algorithms to solve certain optimization problems efficiently. If simulation models can be expressed as mathematical programs, then the techniques and algorithms from mathematical programming can be used to model and analyze simulations. This can result in better views of the behavior of discrete-event systems.; As applications, we derive mathematical programming representations for open and closed tandem queueing networks under various blocking scenarios. We use these formulations to study reversibility and symmetry properties of tandem queues. We also apply the methodology to generate constraint sets for optimal resource scheduling with a specific example of deriving a linear program for optimally scheduling a semiconductor manufacturing cluster tool. The mathematical structure of this linear program leads, in turn, to a more concise simulation model. In addition, optimization representations of discrete-event systems provide a framework for studying stochastic monotonicity and convexity properties. Finally, the methodology is used to derive gradient estimators for system performance measures using dual shadow prices. Explicit dualities between queueing systems and inventory systems are also identified.
Keywords/Search Tags:System, Mathematical, Discrete-event, Representations
Related items