In this paper, we study the On-Line File Transfer Routing and Scheduling problem. Given a sequence of file transfer requests and a graph that represents a network, the problem is to determine both a route and schedule for each file transfer in the sequence so as to minimize a suitable objective function. We require that an algorithm be on-line in the sense that it must respond to each request in the order given and before future requests are known. We show that there is no on-line algorithm which produces solutions with network congestion smaller than [log k] + 1 times that of the optimal solution or makespan smaller than (|log k|)/2 times that of the optimal solution, where k is the number of file transfer requests. We explain that this bound also holds for randomized on-line algorithms versus an adaptive on-line adversary. We discuss briefly the performance of several greedy on-line algorithms both theoretically and in practice.
展开▼
机译：在本文中，我们研究了在线文件传输路由和调度问题。给定一个文件传输请求序列和一个表示网络的图形，问题在于确定序列中每个文件传输的路径和时间表，以最大程度地减少合适的目标函数。从某种意义上讲，我们要求算法是在线的，因为它必须以给定的顺序并在知道未来的请求之前对每个请求做出响应。我们证明，没有在线算法会生成网络拥塞小于最佳解决方案[log k] + 1倍或makepan小于最佳解决方案（| log k |）/ 2倍的解决方案，其中k是文件传输请求的数量。我们解释说，与自适应在线对手相比，随机在线算法也适用此界限。我们将在理论上和实践上简要讨论几种贪婪在线算法的性能。
展开▼
