Summary: We consider a model of computation consisting of a sequence of n tasks. In the absence of failures, each task i has a known completion time \(t_ i\). Checkpoints can be placed between any two consecutive tasks. At a checkpoint, the state of the computation is saved on a reliable storage medium. Establishing a checkpoint immediately before task i is known to cost \(s_ i\). This is the time spent in saving the state of the computation. When a failure is detected, the computation is restarted at the most recent checkpoint. Restarting the computation at checkpoint i requires restoring the state to the previously saved value. The time necessary for this action is given by \(r_ i\). We derive an \(O(n^ 3)\) algorithm to select out of the n-1 potential checkpoint locations those that result in the smallest expected time to complete all the tasks. An \(O(n^ 2)\) algorithm is described for the reasonable case where \(s_ i>s_ j\) implies \(r_ i\geq r_ j\). These algorithms are applied to two models of failure. In the first one, each task i has a given probability \(p_ i\) of completing without a failure, i.e., in time \(t_ i\). Furthermore, failures occur independently and are detected at the end of the task during which they occur. The second model admits a continuous time failure mode where the failure intervals are independent and identically distributed random variables drawn from any given distribution. In this model, failures are detected immediately. In both models, the algorithm also gives the expected value of the overall completion time and we show how to derive all the other moments.