Messages Scheduling for Data Redistribution between Clusters

Colloque avec actes et comité de lecture. internationale.International audienceIn this paper we study the general problem of parallel data redistribution over a network. Given a set of communications between two parallel machines interconnected by a backbone, we wish to minimize the total time required for the completion of all communications assuming that communications can be preempted and that preemption comes with an extra cost. Our problem, called {\em $k$-Preemptive bipartite scheduling (KPBS)} is proven to be \mbox{NP}-Complete. Moreover we prove that approximating KPBS problem within a ratio number smaller that $\frac{4}{3}$ is impossible unless $P=\mbox{NP}$. In spite of this negative result, we study a lower bound on the cost of KPBS problem in terms of its parameters, and we propose an approximation algorithm with ratio $2$ and fast heuristics