SCHEDULING FILE TRANSFERS FOR TREES AND ODD CYCLES

The scheduling of file transfers in networks to minimize the overall finishing time was studied by E. G. Coffman, et al. where the schedule does not permit interruption and each communications module can be used as a transmitter and as a receiver. They first presented complexity results under various conditions. Then they showed that the general problem is NP-complete and provided approximation algorithms. This paper first presents more efficient approximation algorithms with better performances than the above authors' algorithms for the cases of trees and multitrees. Furthermore, there are simple distributed implementations of our approximation algorithms. Then this paper provides a polynomial time algorithm for finding an optimum schedule for an odd cycle, whose complexity was left as an open question by the above authors.