The Achievable Region Methodology
John C. Gittins, K. D. Glazebrook, Richard Weber · 2011
This chapter begins with a very simple example of scheduling in a two class M/M/1 queue. It develops a linear program whose solution provides an upper bound on the expected return from any SFABP, and the fact that this bound can be shown to be attained leads us to yet one more proof of the index theorem. The ideas are worked out in the chapter, to prove that systems satisfying generalized conservation laws (GCLs) have optimal policies that are index policies. The ideas are applied to branching bandits in the chapter, and to job selection and scheduling problems. The chapter concludes by attempting to analyse the simple families of alternative bandit processes (SFABP) for the parallel server case. Controlled Vocabulary Terms branching process