Scheduling and traffic allocation for tasks with bounded splittability.

*(English)*Zbl 1124.68329
Rovan, Branislav (ed.) et al., Mathematical foundations of computer science 2003. 28th international symposium, MFCS 2003, Bratislava, Slovakia, August 25–29, 2003. Proceedings. Berlin: Springer (ISBN 3-540-40671-9/pbk). Lect. Notes Comput. Sci. 2747, 500-510 (2003).

Summary: We investigate variants of the 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 \geq 2\) pieces to be assigned to different machines. In a more general SAC problem each task \(j\) has its own splittability parameter \(k_j \geq 2\). These problems are NP-hard and previous research focuses mainly 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. We show 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.

Our main result is a polynomial time, exact algorithm for the \(k\)-splittable scheduling problem as well as the SAC problem with a fixed number of machines. The running time of our algorithm is exponential in 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.

For the entire collection see [Zbl 1025.00004].

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. We show 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.

Our main result is a polynomial time, exact algorithm for the \(k\)-splittable scheduling problem as well as the SAC problem with a fixed number of machines. The running time of our algorithm is exponential in 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.

For the entire collection see [Zbl 1025.00004].