Minimizing weighted flowtime on capacitated machines
Venue
ACM-SIAM Symposium on Discrete Algorithms (SODA) (2013)
Publication Year
2013
Authors
Kyle Fox, Madhukar Korupolu
BibTeX
Abstract
It is well-known that SRPT is optimal for minimizing flow time on machines that run
one job at a time. However, running one job at a time is a big under- utilization
for modern systems where sharing, simultane- ous execution, and
virtualization-enabled consolidation are a common trend to boost utilization. Such
machines, used in modern large data centers and clouds, are powerful enough to run
multiple jobs/VMs at a time subject to overall CPU, memory, network, and disk
capacity constraints. Motivated by this prominent trend and need, in this work, we
give the first scheduling algorithms to minimize weighted flow time on such
capacitated machines. To capture the difficulty of the problem, we show that
without resource augmentation, no online algorithm can achieve a bounded
competitive ratio. We then investigate algorithms with a small resource
augmentation in speed and/or capacity. Our first result is a simple (2 + ε)-
capacity O(1/ε)-competitive greedy algorithm. Using only speed augmentation, we
then obtain a 1.75-speed O(1)-competitive algorithm. Our main technical result is a
near-optimal (1 + ε)-speed, (1 + ε)-capacity O(1/ε3 )- competitive algorithm using
a novel combination of knapsacks, densities, job classification into categories,
and potential function methods. We show that our results also extend to the
multiple unrelated capacitated machines setting.
