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.
['Leah Epstein', 'Rob van Stee']
Lower bounds for on-line single-machine scheduling