Chen Yao

January 2011
Perturbation Analysis, Optimization and Resource Contention Games in Stochastic Hybrid Systems
Committee Members: Advisor: Christos Cassandras, SE/ECE; Appointed Chair: Sean Andersson, SE/ME; Ioannis Paschalidis, SE/ECE; Michael Caramanis, SE/ME; Pirooz Vakili, SE/ME

Abstract: Stochastic Hybrid Systems (SHS) are systems that combine event-driven and time-driven dynamics, and include elements to model uncertainties in the system. There have been several different types of stochastic hybrid system models proposed. In this dissertation, we first present a unified framework for carrying out perturbation analysis for general SHS with arbitrary structures, in particular, the Infinitesimal Perturbation Analysis (IPA) methodology originally developed for Discrete Event Systems. We also establish properties that apply to this framework and justify its effectiveness in recovering useful performance sensitivity estimates. Then, we concentrate on Stochastic Flow Models (SFMs), which are one type of SHS and are used to abstract the dynamics of many complex discrete event systems to provide the basis for their control and optimization. SFMs have been used to date to study systems with a single user class or some multiclass settings in which performance metrics are not class-dependent. However, little work has been done for multiclass systems that fully differentiate among classes, where classes contend for single or multiple system resources, and with class-dependent performance metrics. This is partly due to the complexities in modeling SFMs for such systems, and partly due to the difficulties in applying IPA in this context. In this dissertation, we build a general framework based on v multiclass SFMs, to model stochastic resource contention systems, where multiple classes (users) compete for shared resources. The general IPA framework is then applied to such systems to obtain performance gradient estimates for various user-specific objectives, which enables the study of a new “user-centric” optimization perspective, in addition to the usual “system-centric” viewpoint. Following the “user-centric” optimization, each class (user) seeks to optimize its own performance by adjusting its own controls, which leads to resource contention games between classes. A simple instance of such systems is studied to illustrate how the general IPA is applied to specific systems, and the difference between solutions of the two perspectives, which is commonly referred to as the “price of anarchy”.

We focus on two specific resource contention problems in this dissertation. One is the admission control problem for the multiclass queueing system under a First Come First Served (FCFS) policy, where the buffer capacity thresholds of all classes are determined to optimize system performances; the other problem is the multiclass lot-sizing problem arising in the manufacturing production planning setting, where we seek to obtain optimal lot sizes for all classes. For both problems, the general IPA framework is applied to the multiclass SFM abstractions to derive sensitivity estimates of performance metrics with respect to control parameters of interest, which are all proven to be unbiased hence reliable for control and optimization purposes. These estimates are then used to drive the on-line optimization of these parameters, and simulation results are provided to contrast the solutions between “system-centric” and “user-centric” perspective.