Data transfers in networks

The scheduling of the transfer of backlogged data in a network to minimize the finishing time is studied. The most complete treatment (of a version) of the problem is due to Gopal, Bongiovanni, Bonucelli, Tang, and Wong, who attacked the problem using the Birkhoff-von Neumann theorem. However, these authors do not provide a complexity analysis of their algorithm.In this paper we solve the version of these authors as well as a more difficult version of this scheduling problem by formulating them as a continuous form of the Hakimi-Kariv-de Werra generalization of the edge-coloring problem in bipartite graphs. This leads to polynomial time algorithms for these problems. Furthermore, our solution of the previously solved version has the desirable feature of having a tighter bound for the number of communication modes than the solution of the above authors.In the above scheduling problem, there may be a time associated with changing from one set of simultaneous data transfers (i.e., a communication mode) to another. It is shown that if the overall finishing time of our schedule includes these times, then even very simple instances of our problem become NP-hard. However, approximation algorithms are presented which produce solutions whose finishing times are at most twice the optimal.Finally, in the above scheduling problem the interruption (or pre-emption) of the performance of each task is permitted. Essentially, the same problem when pre-emption is not permitted was studied by Coffman, Garey, Johnson, and LaPaugh. The relation between the two problems are explored.This work is supported by the National Science Foundation, Division of Electrical, Computer, and Systems Engineering, Computer Engineering Program, Grant ECS-84-06854.