Name
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. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1016/j.orl.2004.10.006 | Oper. Res. Lett. |
Keywords | Field | DocType |
competitive ratio,m identical parallel machine,max flow time.,maximum flow time minimization,max flow time,preemption,optimal preemptive algorithm,on-line scheduling,scheduling,on-line algorithms,possible competitive ratio,on-line scheduling job,optimal algorithm,first in first out,maximum flow | Minimization problem,Online algorithm,Heuristic,Mathematical optimization,Preemption,Scheduling (computing),Computer science,Algorithm,FIFO and LIFO accounting,Maximum flow problem,Competitive analysis | Journal |
Volume | Issue | ISSN |
33 | 6 | Operations Research Letters |
Citations | PageRank | References |
9 | 0.57 | 9 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Christoph Ambühl | 1 | 357 | 18.50 |
| Monaldo Mastrolilli | 2 | 514 | 39.27 |