A Novel Method for Task Scheduling in Distributed Systems Using Memetic
Mohsen Jahanshahi, Majid Gholipour, Mohammad Sadegh Kordafshari, Amir Masoud Rahmani · 2009
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 the processor of each computer. The objective of this problem is minimizing makespan and communication cost, while maximizing CPU utilization. Scheduling problem is known as being NP-complete. Hence, 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, needing exhaustive time. Therefore, in this paper we use memetic algorithm to cope with this shortcoming. We apply Tabu search as local search in our proposed memetic algorithm. Extended simulation results demonstrate that the proposed method outperforms the existent GA-based method in terms of communication cost, CPU utilization and makespan.