Running a job on a collection of dynamic machines, with on-line restarts

We consider the problem of running a background job on a selected machine of a collection of machines. Each of these machines may become temporarily unavailable (busy) without warning. If the currently selected machine becomes unavailable, the scheduler is allowed to restart the job on a different machine. The behaviour of machines is characterized by a Markov chain, which can be compared to [6]. The objective is to minimize the expected completion time of the job. For several types of Markov chains, we present elegant and optimal policies.