Scheduling Tasks to Minimize the Total Computation and Communication Makespan
The authors study the problem of scheduling tasks in a distributed system where the data (and code) for a program may reside on a processor different from the one where it will be executed. The scheduling of the tasks is more complex than classical ones as one must not only take into consideration the processing times but also communication times. They present an off-line polynomial time approximation algorithm for the case when the processors can be partitioned into storage (client) and processing (server) nodes. Their algorithm is the first constant ratio approximation algorithm for this problem.