SCHEDULING FILE TRANSFERS UNDER PORT AND CHANNEL CONSTRAINTS
Shin‐ichi Nakano, Takao Nishizeki · International Journal of Foundations of Computer Science · 1993
The file transfer scheduling problem was introduced and studied by Coffman, Garey, Johnson and LaPaugh. The problem is to schedule transfers of a large collection of files between various nodes of a network under port constraint so as to minimize the overall finishing time. This paper extends their model to include communication channel constraint in addition to port constraint. We formulate the problem with both port and channel constraints as a new type of edge-coloring of multigraphs, called an fg-edge-coloring, and give an efficient approximation algorithm with absolute worst-case ratio 3/2.