×

A genetic algorithm for multi-objective optimisation in workflow scheduling with hard constraints. (English) Zbl 1306.90188

Summary: 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.

MSC:

90C59 Approximation methods and heuristics in mathematical programming
90B35 Deterministic scheduling theory in operations research
90C29 Multi-objective and goal programming
PDFBibTeX XMLCite
Full Text: DOI