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

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)22_Publication in policy or professional journal

View graph of relations



Original languageEnglish
Pages (from-to)1191-1196
Journal / PublicationProceedings of the IEEE Conference on Decision and Control
Publication statusPublished - 1997
Externally publishedYes


Title36th IEEE Conference on Decision and Control (1997 IEEE CDC)
LocationHyatt Regency San Diego
PlaceUnited States
CitySan Diego
Period10 - 12 December 1997


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 polymatroid, with and without side constraints, and their implications in the optimality of index policies.