Scheduling tasks in master-slave parabllel processing systems

摘要

The problem of deterministic scheduling of tasks in the master-slave environment is analyzed in this paper. It is assumed that the slave reads data from the master, processes it, and sends the results to the master. This paradigm can also model a wider class of distributed applications. The goal is to find the shortest schedule. The general problem is computationally hard. However, any greedy heuristic delivers solutions not worse than twice the optimum when tasks are preallocated, and three times the optimum when tasks are not preallocated. Polynomially solvable cases are considered. Copyright direct C 1998 IFAC