We study the problem of scheduling n jobs that arrive over time. We consider a non-preemptive setting on a single machine. The goal is to minimize the total flow time. We use extra resource competitive analysis: an optimal off-line algorithm which schedules jobs on a single machine is compared to a more powerful on-line algorithm that has l machines. We design an algorithm of competitive ratio O(min(Delta^(1/l),n^(1/l))), where Delta is the maximum ratio between two job sizes, and provide a lower bound which shows that the algorithm is optimal up to a constant factor for any constant l.

We also consider scheduling on parallel identical machines. In this case the optimal off-line algorithm has m machines and the on-line algorithm has lm machines. We give a lower bound for this case and consider the resource augmentation required for a constant competitive ratio. For every m, we show a polylogarithmic lower bound (in n or Delta) on l. We also give lower bounds for algorithms using resource augmentation on the speed and for algorithms using restarts. Finally, we consider scheduling with hard deadlines.

This is joint work with Rob van Stee.

Host: Kim Skak Larsen