Abstract of Paper

Scheduling and Traffic Allocation for Tasks with Bounded Splittability
by Piotr Krysta and Peter Sanders and Berthold Voecking

Abstract:

We investigate variants of the well studied problem of scheduling tasks on
uniformly related machines to minimize the makespan. In the $k$-splittable
scheduling problem each task can be broken into at most $k \ge 2$ pieces 
each of which has to be assigned to a different machine. In the slightly
more general SAC problem each task $j$ comes with its own splittability
parameter $k_j$, where we assume $k_j \ge 2$. These problems are known to
be NP-hard and, hence, previous research mainly focuses on approximation
algorithms.

Our motivation to study these scheduling problems is traffic allocation
for server farms based on a variant of the Internet Domain Name Service
(DNS) that uses a stochastic splitting of request streams. Optimal 
solutions for the $k$-splittable scheduling problem yield optimal
solutions for this traffic allocation problem. Approximation ratios,
however, do not translate from one problem to the other because of 
non-linear latency functions. In fact, we can prove that the traffic
allocation problem with standard latency functions from Queueing Theory
cannot be approximated in polynomial time within any finite factor because
of the extreme behavior of these functions.

Because of the inapproximability, we turn our attention to fixed-parameter
tractable algorithms. Our main result is a polynomial time algorithm
computing an exact solution for the $k$-splittable scheduling problem as
well as the SAC problem for any fixed number of machines.
The running time of our algorithm increases exponentially with the
number of machines but is only linear in the number of tasks.
This result is the first proof that bounded splittability reduces
the complexity of scheduling as the unsplittable scheduling is known
to be NP-hard already for two machines. Furthermore, since our
algorithm solves the scheduling problem exactly, it also solves the
traffic allocation problem that motivated our study.