# MPI-I-2003-1-002

## Scheduling and traffic allocation for tasks with bounded splittability

### Krysta, Piotr and Sanders, Peter and Vöcking, Berthold

**MPI-I-2003-1-002**. February** **2003, 15 pages. | Status:** **available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:

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.

Acknowledgement:** **

References to related material:

To download this research report, please select the type of document that fits best your needs. | Attachement Size(s): |

| 164 KBytes |

Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView |

**URL to this document: **http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/2003-1-002

**BibTeX**
`@TECHREPORT{``KrystaSandersVöcking2003``,`

` AUTHOR = {Krysta, Piotr and Sanders, Peter and V{\"o}cking, Berthold},`

` TITLE = {Scheduling and traffic allocation for tasks with bounded splittability},`

` TYPE = {Research Report},`

` INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},`

` ADDRESS = {Stuhlsatzenhausweg 85, 66123 Saarbr{\"u}cken, Germany},`

` NUMBER = {MPI-I-2003-1-002},`

` MONTH = {February},`

` YEAR = {2003},`

` ISSN = {0946-011X},`

`}`