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

• Type: Article in International Scientific Journal
• Date: 2016

Authors

Hamid Arabnejad (Author) FEUP; Jorge G. Barbosa (Author) FEUP; Radu Prodan (Author) Other

Journal

Title: Future Generation Computer Systems

Vol. 55 No. 2

Pages: 29-40

ISSN: 0167-739X

Publisher: Elsevier

Indexing

ISI Web of Knowledge

ISI Web of Science

Scopus

INSPEC

Scientific classification

FOS: Engineering and technology > Electrical engineering, Electronic engineering, Information engineering

CORDIS: Physical sciences > Computer science

Other information

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.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 12