Article ID Journal Published Year Pages File Type
10523992 Operations Research Letters 2005 6 Pages PDF
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Preview
On-line scheduling to minimize max flow time: an optimal preemptive algorithm
Authors
, ,