Scheduling Independent Tasks to Minimize Computation and Communication Makespan in Distributed Systems

T.F. Gonzalez (USA)


Deterministic scheduling, approximation algorithms, client-server model, dual optimization criteria.


We study the problem of scheduling tasks in a distributed system where the data (and code) for a program may re side on a processor different from the one where it will be executed. The scheduling of the tasks is complex as one must balance execution and communications times. We present an off-line polynomial time approximation algo rithm for the case when the processors can be split into storage (client) and processing (server) nodes. Our algo rithm is the first constant ratio approximation algorithm for this problem. Then we discuss generalization of our prob lem as well as the on-line version of our problem.

Important Links:

Go Back