Efficient Scheduling of Task Graphs to Multiprocessors Using a Combination of Modified Simulated Annealing and List Based Scheduling

Abstract

Multiprocessor task scheduling is a well known NP-hard problem and numerous methods have been proposed to optimally solve it. The objective is makespan minimization, i.e. we want the last task to complete as early as possible. Simulated Annealing (SA) has been considered a very good tool for complex nonlinear optimization problem, such as multiprocessor task scheduling. However, a major disadvantage of the technique is that it is extremely slow. List-based scheduling algorithms are regarded as having acceptable results. In this paper we use a list scheduling based algorithm to find an initial solution and in the neighborhood generation phase of simulated annealing. We also parameterize SA and use a modified version of it. Simulation results show that our approach significantly improves the initial solution in considerably low time for different number of tasks; i.e. it efficiently outperforms the used list based scheduling approach.