On-line scheduling to minimize max flow time: an optimal preemptive algorithm |
| |
Authors: | Christoph Ambühl |
| |
Institution: | IDSIA Istituto Dalle Molle di Studi sull’ Intelligenza Artificiale, Galleria 2, CH-6928 Manno, Switzerland |
| |
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: | Scheduling Preemption On-line algorithms Max flow time |
本文献已被 ScienceDirect 等数据库收录! |