Multi-Criteria Job Scheduling in Grid Using an Accelerated Genetic Algorithm

被引:27
作者
Gkoutioudi, Kyriaki Z. [1 ]
Karatza, Helen D. [1 ]
机构
[1] Aristotle Univ Thessaloniki, Dept Informat, Thessaloniki 54124, Greece
关键词
Multi-criteria; Security; Job scheduling; Genetic algorithm; Performance; INDEPENDENT TASKS; PERFORMANCE; HEURISTICS;
D O I
10.1007/s10723-012-9210-y
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
The continuous growth of computation power requirement has provoked computational Grids, in order to resolve large scale problems. Job scheduling is a very important mechanism and a better scheduling scheme can greatly improve the efficiency of Grid computing. A lot of algorithms have been proposed to address the job scheduling problem. Unfortunately, most of them largely ignore the security risks involved in executing jobs in such an unreliable environment as Grid. This is known as security problem and it is a main hurdle to make the job scheduling secure, reliable and fault-tolerant. In this paper, we present a Genetic Algorithm with multi-criteria approach, in terms of job completion time and security risks. Although Genetic Algorithms are suitable for large search space problems such as job scheduling, they are too slow to be executed online. Hence, we changed the implementation of a traditional genetic algorithm, proposing the Accelerated Genetic Algorithm. We also present the Accelerated Genetic Algorithm with Overhead which concerns the extra overhead caused by the application of Accelerated Genetic Algorithm. Accelerated Genetic Algorithm and Accelerated Genetic Algorithm with Overhead are compared with three well-known heuristic algorithms. Simulation results indicate a substantial performance advantage of both Accelerated Genetic Algorithm and Accelerated Genetic Algorithm with Overhead.
引用
收藏
页码:311 / 323
页数:13
相关论文
共 46 条
[1]   An efficient adaptive scheduling policy for high-performance computing [J].
Abawajy, J. H. .
FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE, 2009, 25 (03) :364-370
[2]  
[Anonymous], 1987, Genetic Algorithms and Simulated Annealing
[3]  
[Anonymous], 1998, GRID BLUEPRINT NEW C
[4]  
[Anonymous], 1991, SIMULATION MODELING
[5]  
[Anonymous], J GRID COMPUT
[6]   A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems [J].
Braun, TD ;
Siegel, HJ ;
Beck, N ;
Bölöni, LL ;
Maheswaran, M ;
Reuther, AI ;
Robertson, JP ;
Theys, MD ;
Yao, B ;
Hensgen, D ;
Freund, RF .
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 2001, 61 (06) :810-837
[7]   A comparison study of static mapping heuristics for a class of meta-tasks on heterogeneous computing systems [J].
Braun, TD ;
Siegel, HJ ;
Beck, N ;
Bölöni, LL ;
Maheswaran, M ;
Reuther, AI ;
Robertson, JP ;
Theys, MD ;
Yao, B ;
Hensgen, D ;
Freund, RF .
(HCW '99) - EIGHTH HETEROGENEOUS COMPUTING WORKSHOP, PROCEEDINGS, 1999, :15-29
[8]   Enabling scientific collaboration on the Grid [J].
Brooke, John M. ;
Parkin, Michael S. .
FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE, 2010, 26 (03) :521-530
[9]   A TAXONOMY OF SCHEDULING IN GENERAL-PURPOSE DISTRIBUTED COMPUTING SYSTEMS [J].
CASAVANT, TL ;
KUHL, JG .
IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, 1988, 14 (02) :141-154
[10]   A Weighted Mean Time Min-Min Max-Min Selective Scheduling Strategy for Independent Tasks on Grid [J].
Chauhan, Sameer Singh ;
Joshi, R. C. .
2010 IEEE 2ND INTERNATIONAL ADVANCE COMPUTING CONFERENCE, 2010, :4-9