Sequencing and routing in multiclass queueing networks part II: workload relaxations

摘要

Part II continues the development of policy synthesis techniques for multiclass queueing networks based upon a linear fluid model. The following are shown: (i) A relaxation of the fluid model based on workload leads to an optimization problem of lower dimension. An analogous workload-relaxation is introduced for the stochastic model. These relaxed control problems admit pointwise optimal solutions in many instances. (ii) A translation to the original fluid model is almost optimal, with vanishing relative error as the networkload. approaches one. It is pointwise optimal after a short transient period, provided a pointwise optimal solution exists for the relaxed control problem. (iii) A translation of the optimal policy for the fluid model provides a policy for the stochastic network model that is almost optimal in heavy traffic, over all solutions to the relaxed stochastic model, again with vanishing relative error. The regret is of order log(1-rho). [References: 45]