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

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

0.00 Avg rating—0 Votes
Article ID: iaor2006968
Country: Netherlands
Volume: 33
Issue: 6
Start Page Number: 597
End Page Number: 602
Publication Date: Nov 2005
Journal: Operations Research Letters
Authors: ,
Keywords: scheduling
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.

Reviews

Required fields are marked *. Your email address will not be published.