New results on flow time with resource augmentation

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$. The algorithm works for a hard version of the problem where the sizes of the smallest and the largest jobs are not known in advance, only $Delta$ is known. This gives a trade-off between the resource augmentation and the competitive ratio. 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. Next, we give lower bounds for algorithms using resource augmentation on the speed. Finally, we consider scheduling with hard deadlines.