Performance evaluation of minimum execution time multiprocessor scheduling algorithms using standard task graph set

This paper evaluates performance of heuristic algorithms such as CP (Critical Path), CP/MISF (Critical Path/Most Immediate Successors First), practical sequential optimization algorithm DF/IHS (Depth First/Implicit Heuristic Search) and practical parallel optimization algorithm PDF/IHS (Parallelized DF/IHS) using a "Standard Task Graph Set" for evaluation of multiprocessor scheduling algorithms. The Standard Task Graph Set has been developed to allow worldwide researchers to evaluate multiprocessor scheduling algorithms fairly under the same evaluation conditions. It includes random task graphs generated by several generation methods that were used in the previous papers published by many research groups. Performance evaluation shows that PDF/IHS gives us optimal solutions for 96.06% of tested 660 task graphs with 50 to 1900 tasks by using 6 parallel processors within 600 seconds in wall-clock, and heuristic algorithms can give us optimal solutions for about 75% of tested graphs.