Stochastic Scheduling with Priority Classes

We consider controlled stochastic systems in which multiple job types (customers, projects, jobs, etc.) may require processing by one or more servers. The job types are all members of priority classes and admissible controls must respect the constraints imposed by these. For systems which (when unconstrained) satisfy generalised conservation laws, we obtain the performance space and show that linear objectives are optimised by admissible controls which choose job types within each priority class according to a set of Gittins indices. Various degrees of decomposition of the problem are described and illustrated. In the special case of (discounted and undiscounted) branching bandits, the theory is developed further to yield index-based suboptimality bounds for general policies.