The problem of scheduling jobs that arrive over time on a single machine is well-studied. We study the preemptive model and the model with restarts. We provide lower bounds for deterministic and randomized algorithms for several optimality criteria: weighted and unweighted total completion time, and weighted and unweighted total flow time. By using new techniques, we provide the first lower bounds for several of these problems, and we significantly improve the bounds that were known.

Nonnumerical Algorithms and Problems (acm F.2.2)
Analysis of algorithms and problem complexity (msc 68Q25), Randomized algorithms (msc 68W20), Approximation algorithms (msc 68W25)
CWI
Software Engineering [SEN]

Epstein, L, & van Stee, R. (2001). Lower bounds for on-line single-machine scheduling. Software Engineering [SEN]. CWI.