Optimal and Approximately Optimal Control Policies for Queues in Heavy Traffic

Abstract

The “approximately” optimal control problem for tandem queueing or production networks (with local feedback allowed) under heavy traffic is treated. The buffers (scaled with traffic) are finite. The controls allow various inputs, connecting links, and the processors to be shut down or opened to manage the system. The service and arrival rates, as well as the routing probabilities, can also be controlled, and the system statistics can depend on the system state (scaled buffer occupancies). The associated costs involve holding costs, costs for shutting off/turning on the links or processors and the opportunity cost for lost production. It is shown that the (scaled) controlled system converges weakly (in an appropriate sense) to a controlled limit “reflected” diffusion. In the resealed time, the actions of the controllers lead to multiple “simultaneous” impulses in the limit problem. Thus a nonstandard limit control problem is obtained, and the usual methods of weak convergence for systems under heavy traffic must be modified. Since it is usually not possible to obtain the optimal or nearly optimal controls for the physical process, it is of considerable interest to know whether an optimal or nearly optimal control for the limit process is also nearly optimal for the physical system with heavy traffic. This is shown to be true under reasonable conditions. Although the limit control problem is nonstandard and there is little available theory concerning it, acceptable numerical procedures are available.