Hybrid algorithms for independent batch scheduling in grids
Hybrid algorithms for independent batch scheduling in grids
复制标题
网格中独立批量调度的混合算法
DOI：
10.1504/ijwgs.2012.048402
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
M. Takizawa
中科院分区：
文献类型：
--
作者：
F. Xhafa;J. Kolodziej;L. Barolli;V. Koliçi;Rozeta Miho;M. Takizawa
网格计算已成为解决科学、工程等领域大规模问题的广域分布式范例，并被称为支持 eScience 网格的应用程序系列。利用网格系统中的可用机器有效地计算传入作业的计划是优化系统性能的主要要求。该问题的一种版本是独立批量调度，其中假定作业是独立的，并分批调度，旨在最大限度地减少完工时间和流动时间。考虑到问题的难度，启发式方法用于寻找高质量的解决方案，以实现设计高效网格调度程序的实际目的。最近，人们花费了大量的精力来实现和评估独立启发式和元启发式，以及它们与更高级别算法的混合。在本文中，我们研究了该问题的两种流行算法的性能，即遗传算法（GA）和禁忌搜索（TS），以及涉及它们的两种混合算法，即 GA（TS）和 GA-TS，它们的不同之处在于 GA 和 TS 之间的主要控制和协作实现方式。双目标调度问题考虑了分层和同时优化模式。评估是使用网格模拟器生成的不同网格场景来完成的。计算结果表明，混合算法在完工时间参数方面优于 GA 和 TS，但在流动时间参数方面则优于 GA 和 TS。
Grid computing has emerged as a wide area distributed paradigm for solving large-scale problems in science, engineering, etc. and is known as the family of eScience grid-enabled applications. Computing planning of incoming jobs efficiently with available machines in the grid system is the main requirement for optimised system performance. One version of the problem is that of independent batch scheduling, in which jobs are assumed to be independent and are scheduled in batches aimed at minimising the makespan and flowtime. Given the hardness of the problem, heuristics are used to find high quality solutions for practical purposes of designing efficient grid schedulers. Recently, considerable efforts were spent in implementing and evaluating not only stand-alone heuristics and meta-heuristics, but also their hybridisation into even higher level algorithms. In this paper, we present a study on the performance of two popular algorithms for the problem, namely Genetic Algorithms (GAs) and Tabu Search (TS) and two hybridisations involving them, namely, the GA (TS) and GA-TS, which differ in the way the main control and cooperation among GA and TS are implemented. The hierarchic and simultaneous optimisation modes are considered for the bi-objective scheduling problem. Evaluation is done using different grid scenarios generated by a grid simulator. The computational results showed that the hybrid algorithm outperforms both the GA and TS for the makespan parameter, but not for the flowtime parameter.
DOI：
--
发表时间：
2007
期刊：
Journal of Interconnection Networks(JOIN) 8・2
影响因子：
--
作者：
F.Xhafa;J.Carretero;L.Barolh;A.Durresi
通讯作者：
A.Durresi
使用 Windows PC 的网格性能评估
DOI：
--
发表时间：
2008
期刊：
Inderscience publisher, International Journal of Web and Grid Services Vol.4,No.4
影响因子：
--
作者：
Kenichi Tanaka;Minoru Uehara;Hideki Mori
通讯作者：
Hideki Mori