AN EFFICIENT TASKS SCHEDULING ALGORITHM FOR DISTRIBUTED MEMORY MACHINES WITH COMMUNICATION DELAYS

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 mam drawback of this algorithm The research in this study concerns to develop an efficient iterative algorithm for scheduling problem based on the hill-climbing. The developed 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.