A collection of M machines which deteriorate under usage is maintained by a set of R repairmen who may have other tasks to perform. Maintenance interventions will improve a machine's condition and may preempt costly breakdowns. The problem of scheduling such interventions to minimise the total expected discount cost incurred in operating the machines over an infinite horizon is formulated as a Markov Decision Process which has the form of a restless bandit problem. We outline an approach to the development of maintenance policies based on simple machine indices in the form of a fair charge for a maintenance intervention in the machine's current state. Closed form indices are derived for two particular models. Numerical investigations demonstrate the strong performance of the derived index heuristics.