An Efficient Tasks Scheduling Algorithm for Distributed Memory Machines With Communication Delays

Abstract

The scheduling of multiple interacting tasks of a single parallel program is considered the most important issue to exploit the true performance of the multiprocessor system. The problem is to find a schedule that will minimize the execution time (Make_Span) of a program. On the other hand, task scheduling on a multiprocessor system with and without communication delays is known to be NP-complete problem. Consequently, many heuristic algorithms have been developed, each of which may find optimal scheduling under different circumstances. One of the well known iterative algorithms is the hill-climbing. This algorithm starts with a complete solution and searches to improve this solution by choosing a better neighbor based on a cost function. This will lead to a local optimum which is considered the main drawback of this algorithm. The research in this study concerns to develop an efficient iterative algorithm for scheduling problem based on the hill-climbing. Present algorithm satisfies a local optimum that is very close to the global one in a reasonable amount of time. In most experiments, it satisfies the actual global optimum.