The
data migration problem is to compute an efficient plan for moving data stored on devices in a network from one configuration to another.
It is modeled by a transfer graph, where vertices represent the storage devices, and the edges represent the data transfers
required between pairs of devices. Each vertex has a non-negative weight, and each edge has unit processing time. A vertex
completes when all the edges incident on it complete; the constraint is that two edges incident on the same vertex cannot
be processed simultaneously. The objective is to minimize the sum of weighted completion times of all vertices. Kim (
Journal of Algorithms, 55:42-57, 2005) gave an LP-rounding 3-approximation algorithm. We give a more efficient primal-dual algorithm that achieves the same approximation
guarantee, which can be extended to yield a 5.83-approximation for arbitrary processing times. We also study a variant of
the open shop scheduling problem. This is a special case of the data migration problem in which the transfer graph is bipartite
and the objective is to minimize the completion times of edges. We present a simple algorithm that achieves an approximation
ratio of
Ö2{\sqrt{2}} ≈ 1.414, thus improving the 1.796-approximation given by Gandhi
et al. (
ACM Transaction on Algorithms, 2(1):116-129, 2006). We show that the analysis of our algorithm is almost tight.