Low-time complexity budget–deadline constrained workflow scheduling on heterogeneous resources

• Tipo: Artigo em Revista Científica Internacional
• Data: 2016

Autores

Hamid Arabnejad (Autor) FEUP; Jorge G. Barbosa (Autor) FEUP; Radu Prodan (Autor) Outra

Revista

Título: Future Generation Computer Systems

Vol. 55 Nº 2

Páginas: 29-40

ISSN: 0167-739X

Editora: Elsevier

Indexação

ISI Web of Knowledge

ISI Web of Science

Scopus

INSPEC

Classificação Científica

FOS: Ciências da engenharia e tecnologias > Engenharia electrotécnica, electrónica e informática

CORDIS: Ciências Físicas > Ciência de computadores

Outras Informações

DOI: 10.1016/j.future.2015.07.021

Abstract (EN): The execution of scientific applications, under the utility computing model, is constrained to Quality of Service (QoS) parameters. Commonly, applications have time and cost constraints such that all tasks of an application need to be finished within a user-specified Deadline and Budget. Several algorithms have been proposed for multiple QoS workflow scheduling, but most of them use search-based strategies that generally have a high time complexity, making them less useful in realistic scenarios. In this paper, we present a heuristic scheduling algorithm with quadratic time complexity that considers two important constraints for QoS-based workflow scheduling, time and cost, named Deadline–Budget Constrained Scheduling (DBCS). From the deadline and budget defined by the user, the DBCS algorithm finds a feasible solution that accomplishes both constraints with a success rate similar to other state-of-the-art search- based algorithms in terms of the successful rate of feasible solutions, consuming in the worst case only approximately 4% of the time. The DBCS algorithm has a low-time complexity of O(n2.p) for n tasks and p processors.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 12