We give an algorithm to minimize the total completion time on-line on a single machine, using restarts, with a competitive ratio of 3/2. The optimal competitive ratio without using restarts is 2 for deterministic algorithms and $e/(e-1) approx 1.582$ for randomized algorithms. This is the first restarting algorithm to minimize the total completion time that is proved to be better than an algorithm that does not restart.

Nonnumerical Algorithms and Problems (acm F.2.2)
Analysis of algorithms and problem complexity (msc 68Q25), Randomized algorithms (msc 68W20), Approximation algorithms (msc 68W25)
Software (theme 1), Logistics (theme 3), Energy (theme 4)
CWI
Software Engineering [SEN]
Intelligent and autonomous systems

van Stee, R, & La Poutré, J.A. (2002). Minimizing the total completion time on-line on a single machine, using restarts. Software Engineering [SEN]. CWI.