We consider the problem of running a job on a selected machine of a collection of machines. Each of these machines may become temporarily unavailable (busy) without warning, in which case the scheduler is allowed to restart the job on a different machine. The behaviour of machines is characterized by a Markov chain, and objective is to minimize completion time of the job. For several types of Markov chains, we present optimal policies.

Nonnumerical Algorithms and Problems (acm F.2.2), PROBABILITY AND STATISTICS (acm G.3)
Performance evaluation; queueing; scheduling (msc 68M20), Scheduling theory, deterministic (msc 90B35), Markov and semi-Markov decision processes (msc 90C40)
Software (theme 1), Logistics (theme 3), Energy (theme 4)
Software Engineering [SEN]
Intelligent and autonomous systems

van Stee, R, & La Poutré, J.A. (1998). Running a job on a collection of dynamic machines, with on-lin restarts. Software Engineering [SEN]. CWI.