Dynamic Scheduling and Resource Control in Stochastic Processing Networks: Beyond Priority Rules

Columbia University, New York NY

Investigators

Abstract

The goal of this project is to study resource control that extends beyond the classical priority rules, and to do so in the general setting of stochastic processing networks, allowing features such as concurrent occupancy and sharing of resources. Dynamic allocation of resources to serve different kinds of customers or job classes is a central issue in the design and analysis of many complex systems. The research plan is to investigate the asymptotic behavior of the system under a general class of resource control, which optimizes in each system state a utility function (e.g., a "fairness" measure as in the case of the Internet protocol, also prevalent in many service systems). This will be carried out by deriving the limiting regimes of the main performance processes, such as workloads and congestion levels, under fluid and diffusion scalings. These limits are useful in evaluating the system performance. They also establish the connection between the utility function, which the control maximizes locally (or "greedily") in each state, and the performance objective that is optimized by the control globally over any given planning horizon, finite or infinite. Results from the project are expected to help the design of dynamic resource control rules in stochastic processing networks in two ways: given a control scheme, its performance can be evaluated; and conversely, given a performance objective, one or several control schemes can be identifed to optimize the objective. More broadly, the project will add to the mathematical foundation of stochastic networks, enhance the understanding of the implications of utility- maximizing resource allocation schemes on network performance, and lead to new decision tools and computational techniques for systems design and optimization.