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

✍ Scribed by Christoph Ambühl; Monaldo Mastrolilli

• Publisher: Elsevier Science
• Year: 2005
• Tongue: English
• Weight: 170 KB
• Volume: 33
• Category: Article
• ISSN: 0167-6377
• DOI: 10.1016/j.orl.2004.10.006

✦ Synopsis

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.