A novel method for task scheduling in distributed systems using Max-Min Ant Colony Optimization

Tasks scheduling problem is a key factor for a distributed system in order to achieve better efficiency. That is, how proper allocating the tasks to the processor of each computer. In this problem the reported methods try to minimize MakeSpan while maximizing CPU utilization. Since this problem is NP-complete, many genetic algorithms have been proposed to search optimal solutions from entire solution space. However, these existing approaches are going to scan the entire solution space without consideration 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. Therefore in this paper we use memetic algorithm to cope with this shortcoming. We apply Ant Colony Optimization as local search in proposed memetic algorithm considering load balancing efficiently. Extended simulation results demonstrate that the proposed method outperform the existent GA-based method in term of CPU utilization and MakeSpan.