Title: A genetic algorithm for multi-objective optimisation in workflow scheduling with hard constraints

Authors: Sonia Yassa; Jérémie Sublime; Rachid Chelouah; Hubert Kadima; Geun-Sik Jo; Bertrand Granado

Addresses: University of Cergy-Pontoise, L@ris Laboratory, EISTI Engineering School, Avenue du Parc, 95000 Cergy, France ' University of Cergy-Pontoise, L@ris Laboratory, EISTI Engineering School, Avenue du Parc, 95000 Cergy, France ' University of Cergy-Pontoise, L@ris Laboratory, EISTI Engineering School, Avenue du Parc, 95000 Cergy, France ' University of Cergy-Pontoise, L@ris Laboratory, EISTI Engineering School, Avenue du Parc, 95000 Cergy, France ' University of Cergy-Pontoise, L@ris Laboratory, EISTI Engineering School, Avenue du Parc, 95000 Cergy, France ' University of Cergy-Pontoise, L@ris Laboratory, EISTI Engineering School, Avenue du Parc, 95000 Cergy, France

Abstract: Cloud computing is a fast growing technology allowing companies to use on-demand computation, and data services for their everyday needs. The main contribution of this work is to propose a new model of genetic algorithm for the workflow scheduling problem. The algorithm must be capable of: 1) dealing with the multi-objective problem of optimising several quality of service (QoS) variables, namely: computation time, cost, reliability or security; 2) handling a large number of workflow scheduling aspects such as adding constraints on QoS variables (deadlines and budgets); 3) handling hard constraints such as restrictions on task scheduling that the previous algorithms have not addressed. Using data from Amazon elastic compute cloud (EC2) and workflows from the London e-Science Centre; we have compared our algorithm with other scheduling algorithms. Simulation results indicate the efficiency of the proposed metaheuristic both in terms of solution quality and computational time.

Keywords: genetic algorithms; cloud computing; workflow scheduling; service level agreements; SLAs; quality of service; QoS; hard constraints; metaheuristics; multi-objective optimisation; simulation.

DOI: 10.1504/IJMHEUR.2013.058475

International Journal of Metaheuristics, 2013 Vol.2 No.4, pp.415 - 433

Received: 21 Feb 2013
Accepted: 28 Jul 2013
Published online: 12 Jul 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article