Heuristics for multi-round divisible loads scheduling with limited memory

In this paper scheduling divisible loads in systems with limited memory is examined. Divisible loads are parallel computations which can be arbitrarily divided into parts independently processed on remote processors. The scheduling problem consists in distributing the load, taking into account communication and computation time, and limited memory buffers, so that the total processing time is as short as possible. The amount of memory available on the remote processors is too small to hold the whole load at once. Hence, the load must be distributed in many small messages. Since the problem is computationally hard, we propose not one, but several classes of heuristics. In a series of computational experiments we demonstrate advantages and weaknesses of certain heuristic types for wide range of changing system parameters.