A Comparison Study on the Performance of Population-based Meta-Heuristics for Independent Batch Scheduling in Grid Systems
A Comparison Study on the Performance of Population-based Meta-Heuristics for Independent Batch Scheduling in Grid Systems
复制标题
DOI：
10.1109/cisis.2011.27
复制
发表时间：
2011-06
期刊：
影响因子：
--
通讯作者：
F. Xhafa;J. Kolodziej;Bernat Duran;Marcin Bogdański;L. Barolli
中科院分区：
文献类型：
--
作者：
F. Xhafa;J. Kolodziej;Bernat Duran;Marcin Bogdański;L. Barolli
最近有很多研究致力于网格系统中的调度和资源分配。特别是在高效网格调度器的设计中，启发式和元启发式方法的使用已经做了大量的研究工作。本文对不同的基于种群的启发式算法，即遗传算法、记忆算法和细胞记忆算法的性能进行了全面的研究。其目的是阐明不同的基于种群的方法的优点和局限性，以及它们与禁忌搜索等局部搜索方法在求解网格调度器执行时间约束下的多目标版本问题时的混合。我们考虑了一组关于条目大小和静态/动态特征的高度变化的场景，旨在判断关于所考虑的方法获得的解的质量的稳健性。这些场景分为静态场景和动态场景，静态场景为每个条目提供一组任务和资源，动态场景使用网格模拟器实时观察网格环境中启发式算法的行为。
There has been a lot of research recently devoted to scheduling and resource allocation in Grid systems. Research efforts have been done in particular to the use of heuristic and meta-heuristic approaches in the design of efficient Grid schedulers. In this paper we present a comprehensive study on the performance of different population-based heuristic methods, namely Genetic Algorithms, Memetic Algorithms and Cellular Memetic Algorithms for the problem. The aim is to shed light on the advantages and limitations of different population based methods as well as their hybridization with local search methods, such as Tabu Search, when solving the multi-objective version of the problem under execution time restrictions of Grid schedulers. We considered a set of scenarios that represent a high variation regarding the size of entries and static/dynamic features aiming to judge on the robustness with regard to the quality of the solutions obtained by the considered methods. These scenarios are divided into static, which provides a single set of tasks and resources for each entry, and dynamic, using a grid simulator used to observe the behavior of heuristics in Grid environments in real time.