In this paper, based on a thorough analysis of different policies for DAG scheduling, an improved algorithm ICPDP (Improved
Critical Path using Descendant Prediction) is introduced. The algorithm performs well with respect to the total scheduling
time, the schedule length and load balancing. In addition, it provides efficient resource utilization, by minimizing the idle
time on the processing elements. The algorithm has a quadratic polynomial time complexity. Experimental results are provided
to support the performance evaluation of the algorithm and compare them with those obtained for other scheduling strategies.
The ICPDP algorithm, as well as other analyzed algorithms, have been integrated in the DIOGENES project, and have been tested
by using MonAlisa farms and ApMon, a MonAlisa extension.
Keywords Grid Scheduling - DAG Scheduling - Tasks Dependencies - Workflow Applications - MonALISA