A New Approach for Task Scheduling in Distributed Systems Using Learning Automata

Tasks scheduling problem is a key factor for a distributed system in order to achieve better efficiency. The problem of tasks scheduling in a distributed system can be stated as allocating tasks to processor of each computer. The objective of this problem is minimizing Makespan and communication cost while maximizing CPU utilization. Scheduling problem is known as NP-complete. Hence, many genetic algorithms have been proposed to search optimal solutions from entire solution space. However, the 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 weakness of these methods is to spend much time doing scheduling and hence need to exhaustive time. In this paper we use Learning algorithm to cope with the weakness of GA based method. In fact we use the Learning automata as local search in the memetic algorithm. Experimental results prove that the proposed method outperforms the existent GA based method in terms of communication cost, CPU utilization and Makespan.