The performance of index-based policies for bandit problems with stochastic machine availability

We consider generalisations of two classical stochastic scheduling models, namely the discounted branching bandit and the discounted multi-armed bandi t, to the case where the collection of machines available for processing is itself a stochastic process. Under rather mild conditions on the machine a vailability process we obtain performance guarantees for a range of control s based on Gittins indices. Various forms of asymptotic optimality are esta blished for index-based limit policies as the discount rate approaches 0.