ausblenden:
Schlagwörter:
-
Zusammenfassung:
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 $\npc$-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 $\npc$-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.
