A GA+TS Hybrid Algorithm for Independent Batch Scheduling in Computational Grids
A GA+TS Hybrid Algorithm for Independent Batch Scheduling in Computational Grids
复制标题
DOI：
10.1109/nbis.2011.41
复制
发表时间：
2011-09
期刊：
影响因子：
--
通讯作者：
F. Xhafa;J. Kolodziej;L. Barolli;A. Fundo
中科院分区：
文献类型：
--
作者：
F. Xhafa;J. Kolodziej;L. Barolli;A. Fundo
元分析学研究团体提出了元分析学方法的混合，作为克服单一元分析学局限性的一种方法。虽然先验不能保证所得到的混合启发式算法会优于独立的启发式算法，但一般来说，对于所研究的优化问题的实例类，可以找到更好的结果。一个有前途的家庭杂交算法是基于人口的算法与局部搜索算法。在本文中，我们提出了一个高层次的混合遗传算法（GAs）和禁忌搜索（TS），表示GA+TS算法，在计算网格调度。在作业调度问题中，目标是有效地计算进入网格系统中的可用机器的作业的规划，使系统的性能得到优化。我们的GA+TS高级混合算法首先运行GA流程，直到满足一个停止条件，然后将最佳输出解作为TS算法的初始解传递给TS算法进行进一步的改进，然后执行TS流程。因此，我们的目标是序列的调用GA和TS在一个链中，收益率，以有效的网格搜索器，最终会表现得更好，比相同的元搜索器作为简单的搜索器，没有任何额外的支持和改进机制的本地解决方案。我们评估了所提出的混合算法使用不同的网格场景生成的网格模拟器。计算结果表明，混合GA+TS算法优于GA和TS的网格调度问题的某些类别的实例。
The hybridization of heuristics methods has been proposed in the meta-heuristics research community as a way to overcome limitations of single meta-heuristics. Although a priori there is no guarantee that the resulting hybrid heuristic would outperform stand alone heuristics, in general better results can be found for classes of instances of the optimization problem under study. One promising family of hybridization algorithms is that of population based heuristics with local search heuristics. In this paper we present a high level hybridization of Genetic Algorithms (GAs) and Tabu Search (TS), denoted GA+TS algorithm, for scheduling in computational grids. In the job scheduling problem, the objective is to efficiently compute a planning of incoming jobs to available machines in the Grid system so that the system performance is optimized. Our GA+TS high level hybrid algorithm runs first the GA flow, until a stopping condition is met, and then passes the best output solution in input as starting solution to TS algorithm for further improvement, the flow of TS is then executed. The objective is thus to sequence the calls of GA and TS in a chain that yields to efficient Grid schedulers that would eventually perform better than the same meta-heuristics used as simple schedulers without any additional support and improvement mechanism of the local solutions. We evaluated the proposed hybrid algorithm using different grid scenarios generated by a grid simulator. The computational results showed that the hybrid GA+TS algorithm outperforms both the GA and TS for some classes of instances of the Grid scheduling problem.