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 NPcomplete, 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 GAbased method in term of CPU utilization and MakeSpan.

关键词： Task scheduling Memetic algorithm Ant Colony Optimization

作者: M. H. Kashani R. Sarvizadeh

作者单位: Department of Computer Engineering Islamic Azad University, Shahr-e-Qods Branch Tehran, Iran Department of Electrical Computer Engineering Islamic Azad University, Kashan Branch Kashan, Iran

会议类型: 国际会议

会议名称: 2011 3rd International Conference on Advanced Computer Control(2011年IEEE第三届高端计算机控制国际会议 ICACC2011)

会议地点: 哈尔滨

会议语种:英文

页码: 422-426

在线出版日期: 2011-01-18（万方平台首次上网日期，不代表论文的发表时间）