On Constrained Optimization of the Klimov Network and Related Markov Decision Processes

Abstract

We solve a constrained version of the server allocation problem for a Klimov network and establish that the optimal constrained schedule is obtained by randomizing between two fixed priority schemes. This generalizes work of Nain and Ross in the context of the competing queue problem, and also covers the discounted cost case.In order to establish these results we develop a general framework for optimization under a single constraint in the presence of index-like policies. This methodology is in principle of wider applicability.