Robust Feedback Control and Analysis of Queueing Systems

Virginia Polytechnic Institute And State University, Blacksburg VA

Investigators

Abstract

This project develops mathematical techniques for the analysis of optimal robust control (service) strategies for queuing systems. Fluid models (deterministic, continuous state and time variables) are considered which describe queuing network configurations motivated by applications in manufacturing, communications and vehicular traffic control. Optimal control problems are formulated using the general approach of nonlinear robust control, resulting in an appropriate Hamilton-Jacobi-Isaacs (HJI) partial differential equation which determines the value function of a dynamic game. Solutions to this HJI are constructed by methods similar to classical techniques involving (bi)characteristics or a field of extremals. While this approach is well understood in general, it has had little development in applications to queuing networks. One reason for this is that the precise mathematical description of queuing systems often involves a Skorokhod problem formulation to account for the changes to systems dynamics when some of the queues become empty. A major goal of the project is to develop this approach for a variety of examples (e.g. different network structures and cost criteria) in order to discern the mathematical structure of solutions to the HJI, the form of the optimal policies themselves, and how the unique features of the Skorokhod problem formulation can be treated in this approach. Using the understanding of solutions to the HJI gained through these case studies, numerical methods are developed to analyze larger and more complex examples. The mathematical tools produced will contribute to the theory of robust control in general, to problems involving Skorokhod dynamics in particular, and will introduce robust control techniques to the area of traffic control. The flow of "traffic" through a network, whether vehicles on a system of intersecting roads, products in a multistage manufacturing process, or "packets" of information in an electronic network, is an increasingly important aspect of our commercial and public services infrastructure. In the familiar example of vehicles on a system of roads the network consists of several intersections connected by roads of various sizes. The different streams of traffic that meet at an intersection must take turns or share the limited capacity of the intersection. The efficiency of the network depends on the strategy which controls the traffic streams that are allowed to use the various intersections at each moment of time. (In the most familiar vehicular setting this simply means the scheme which governs the sequence and timing of traffic lights.) Now that sensors are available to detect the number of vehicles waiting or traveling on each of the roads in a network, the design intelligent signal light control strategies to manage the network with optimal efficiency is a natural goal. The same general issue of service allocation strategy is present in manufacturing or communication systems, although the terminology and specific features of the networks are different in those settings. Traffic and network engineers have developed various ways to study the performance of network service control strategies "experimentally" and to adjust those strategies to current network conditions in an adaptive way. However, with only a few exceptions, past research has not developed systematic tools to identify service control strategies whose performance is optimal in a precise mathematical sense. This project develops mathematical ideas and tools for this purpose. The new understanding and mathematical techniques which result should be a valuable contribution to the management and design of high performance networks.