Physical Sciences and Mathematics Commons^™

Task Scheduling In Networks, Cynthia Phillips, Clifford Stein, Joel Wein

Dartmouth Scholarship

Scheduling a set of tasks on a set of machines so as to yield an efficient schedule is a basic problem in computer science and operations research. Most of the research on this problem incorporates the potentially unrealistic assumption that communication between the different machines is instantaneous. In this paper we remove this assumption and study the problem of network scheduling, where each job originates at some node of a network, and in order to be processed at another node must take the time to travel through the network to that node.

Our main contribution is to give approximation algorithms …