A lower bound on the schedule time for scheduling tasks on distributed memory systems

Obtaining an optimal schedule for assigning tasks onto distributed memory machines (DMMs) has been proven to be NP-complete. Several heuristic solutions to the scheduling problem have been proposed which are based on certain assumptions that allow the algorithm to be executed in a polynomial time bound. Even though the heuristics do not guarantee an optimal solution, they have been shown to perform reasonably well for many applications. It is difficult to judge the performance of these heuristics because for a given directed acyclic graph (DAG), it is practically infeasible to obtain the optimal solution. The paper proposes a method to compute the lower bound in a polynomial time bound. The idea of the lower bound is to obtain a solution as close to optimal as possible. Also, the lower bound should be less than or equal to the optimal solution. The lower bound with the inclusion of the interprocessor communication costs has been proposed by Al-Mouhamed (1990). The author has observed that for some cases this algorithm does not give a sharp lower bound. The scheme provides a sharper lower bound than the one proposed by Al-Mouhamed. Another scheme was presented by Jain and Rajaraman (1995) which partitions the graph into certain parts and compute the bound for each part to arrive at a sharper bound. To compute the bound of each partition, they use the same method as proposed by Al-Mouhamed. Thus, the scheme can also be used to improve upon the bound proposed by Jain and Rajaraman