We analyse and optimise the completion time for a class of jobs whose conditional completion time is not always decreasing with the time invested in the job. For such jobs, restarts may speed up the completion. Examples of such jobs include download of web pages, randomised algorithms, distributed queries and jobs subject to network or other failures. This paper derives computationally attractive expressions for the moments of the completion time of jobs under restarts and provides algorithms that optimise the restart policy. We also identify characteristics of optimal restart times as well as of probability distributions amenable to restarts.