Minimizing weighted flowtime on capacitated machines
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.
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.
Research Areas
