  We consider a wireless system with a small number of delay constrained users
and a larger number of users without delay constraints. We develop a scheduling
algorithm that reacts to time varying channels and maximizes throughput utility
(to within a desired proximity), stabilizes all queues, and satisfies the delay
constraints. The problem is solved by reducing the constrained optimization to
a set of weighted stochastic shortest path problems, which act as natural
generalizations of max-weight policies to Markov decision networks. We also
present approximation results for the corresponding shortest path problems, and
discuss the additional complexity and delay incurred as compared to systems
without delay constraints. The solution technique is general and applies to
other constrained stochastic decision problems.
