Dynamic scheduling of a system with two parallel servers: asymptotic policy in heavy traffic

摘要

Dynamic control of stochastic networks has applications to the control of modern telecommunications, manufacturing and computer systems. Most models of such networks cannot be analyzed exactly and one is naturally led to consider more viable approximations. In particular, Brownian control problems have been proposed as formal heavy traffic approximations to dynamic scheduling problems for queueing networks. Various authors have combined analysis of such Brownian control problems with clever interpretation of their optimal solutions to suggest original and attractive policies for some queueing network control problems. These analytically derived control policies (as opposed to ones derived computationally by discretization of the Brownian control problem) have frequently involved threshold-type control. Although these policies have usually performed well when simulated, there is no systematic way of analysing their performance. We consider a queueing system with two parallel servers and dynamic routing and sequencing capabilities. For this model, we propose a threshold control policy based on continuous review of the system's status, and by means of a systematic method we establish asymptotic optimality of this policy. This work is a first step towards providing a systematic approach to analyzing the asymptotic performance of control policies for queueing networks derived by analytic means using Brownian control problems.