Dynamic scheduling of a class of stochastic systems: extended polymatroid, side constraints, and optimality

A class of stochastic systems (e.g., Klimov´s model) satisfies generalized conservation laws; and the performance space is an extended polymatroid. This structure is the key to the optimality of index policies. In applications, there are often side constraints that represent service requirements (e.g., upper limits on delay). The objective of this paper is to explore the structural properties of extended polymatroids, with and without side constraints, and their implications in the optimality of index policies