Optimal control of Stochastic Fluid Programs

Abstract

In manufacturing and telecommunication systems we often encounter the situation that there are different timescales for the occurrence of events. Thus, to obtain appropriate models we replace quantities that vary faster with their averages, whereas we keep the slower process stochastic. Formulations of this type are commonly used and important in stochastic modeling. In this paper we give a unified approach towards the optimal control of such systems which we will call Stochastic Fluid Programs. We investigate the discounted cost criterion as well as the average cost criterion. Stochastic Fluid Programs are a special class of piecewise deterministic Markov processes with one exception: in our model we allow for constraints on the actions and the process can move along the boundary of the state space. First we will prove that an optimal stationary policy exists for the discounted problem. The optimal stationary policy is the solution of a deterministic control problem. The average cost problem is solved via the vanishing discount approach. Moreover, we show that the value functions in both cases are constrained viscosity solutions of a Hamilton-Jacobi-Bellman equation and derive verification theorems. We apply our results to several examples, e.g. the stochastic single-server scheduling problem and the problem of routing to parallel queues. In a second part we approximate control problems in stochastic queueing networks (which are known to be very hard) by fluid problems which are special (purely deterministic) Stochastic Fluid Programs. The fluid problems are rather easy to solve. We show that the fluid value function provides an asymptotic lower bound on the value function of the stochastic network under fluid scaling. Moreover, we construct a so-called Tracking-Policy for the stochastic queueing network which achieves the lower bound as the fluid scaling parameter tends to infinity. In this case the Tracking-Policy is called asymptotically optimal. This statement is true for multiclass queueing networks and admission and routing problems. The convergence is monotone under some convexity assumptions. The Tracking-Policy approach also shows that a given fluid model solution can be attained as a fluid limit of the original discrete model.