Using Simulated Annealing for Task Scheduling in Distributed Systems

Task scheduling is one of the key factors in a distributed system. That is, how proper allocating the tasks to the processor of each computer in order to achieve better performance is important. In this problem the reported methods try to minimize Make span and communication cost while maximizing CPU utilization. Since this problem is NP-complete, many genetic algorithms have been proposed. However, except a method based on Tabu search, the existing methods scan the entire solution space regardless to techniques that can reduce the complexity of the optimization. In other words, the main shortcoming of these approaches is to spend much time doing scheduling and, hence, need to exhaustive time. In order to tackle this weakness, in this paper we use memetic algorithm. We apply simulated annealing as local search in our proposed memetic algorithm. Extended experimental results demonstrate efficiency of the proposed method.