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.

, ,
, ,
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.