[BOB15] A Hybrid Algorithm for DAG Application Scheduling on Computational Grids

Conférence Internationale avec comité de lecture : International Conference on Mobile, Secure and Programmable Networking (MSPN'2015), June 2015, pp.63-77, Series LNCS 9395, France, (DOI: 10.1007/978-3-319-25744-0_6)

Auteurs: L. Bouali , K. Oukfif , S. Bouzefrane , F. Oulebsir Boumghar

Mots clés: Grid computing, Task scheduling, Directed Acyclic Graph, Heterogeneous Earliest, Finish Time algorithm Particle Swarm Optimization Algorithm, Makespan

Résumé: In the late three decades, grid computing has emerged as a new field providing a high computing performance to solve larger scale computational demands. Because Directed Acyclic Graph (DAG) application scheduling in a distributed environment is a NP-Complete problem, meta-heuristics are introduced to solve this issue. In this paper, we propose to hybridize two well-known heuristics. The first one is the Heterogeneous Earliest Finish Time (HEFT) heuristic which determines a static scheduling for a DAG in a heterogeneous environment. The second one is Particle Swarm Optimization (PSO) which is a stochastic meta-heuristic used to solve optimization problems. This hybridization aims to minimize the makespan (i.e., overall competition time) of all the tasks within the DAG. The experimental results that have been conducted under hybridization show that this approach improves the scheduling in terms of completion time compared to existing algorithms such as HEFT.

Equipe: mim

Collaboration: USTHB

BibTeX

@inproceedings {
	BOB15,
	title	=	"{A Hybrid Algorithm for DAG Application Scheduling on Computational Grids}",
	author	=	" L. Bouali and K. Oukfif and S. Bouzefrane and F. Oulebsir Boumghar ",
	booktitle	=	"{International Conference on Mobile, Secure and Programmable Networking (MSPN'2015)}",
	year	=	2015,
	edition	=	"Springer",
	month	=	"June",
	series	=	"LNCS 9395",
	pages	=	"63-77",
	address	=	" France",
	doi	=	"10.1007/978-3-319-25744-0_6",
}