Please use this identifier to cite or link to this item:
Author(s): Hamid Arabnejad
Jorge G. Barbosa
Radu Prodan
Title: Low-time complexity budget-deadline constrained workflow scheduling on heterogeneous resources
Issue Date: 2016
Abstract: 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.
Subject: Ciência de computadores, Engenharia electrotécnica, electrónica e informática
Computer science, Electrical engineering, Electronic engineering, Information engineering
Scientific areas: Ciências da engenharia e tecnologias::Engenharia electrotécnica, electrónica e informática
Engineering and technology::Electrical engineering, Electronic engineering, Information engineering
Document Type: Artigo em Revista Científica Internacional
Rights: restrictedAccess
Appears in Collections:FEUP - Artigo em Revista Científica Internacional

Files in This Item:
File Description SizeFormat 
  Restricted Access
pdf1.02 MBAdobe PDF    Request a copy from the Author(s)

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.