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

• A review of multiple QoS parameter workflow scheduling.
• A new multiple QoS algorithm with quadratic complexity for workflow scheduling.
• Similar performances of search-based algorithms in a small fraction of the time.
• Results for randomly generated graphs as well as for real-world applications.

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)O(n2.p) for nn tasks and pp processors.