On-line scheduling to minimize max flow time: an optimal preemptive algorithm

We investigate the maximum flow time minimization problem of on-line scheduling jobs on m identical parallel machines. When preemption is allowed, we derive an optimal algorithm with competitive ratio 2-1/m. When preemption is not allowed and m=2, we show that the First In First Out heuristic achieves the best possible competitive ratio.