Skip to main content
Kent Academic Repository

A family of heuristics for agent-based elastic Cloud bag-of-tasks concurrent scheduling

Sim, Kwang Mong, Gutierrez-Garcia, J. Octavio (2013) A family of heuristics for agent-based elastic Cloud bag-of-tasks concurrent scheduling. Future Generation Computer Systems, 29 (7). pp. 1682-1699. ISSN 0167-739X. (doi:10.1016/j.future.2012.01.005) (KAR id:32019)


The scheduling and execution of bag-of-tasks applications (BoTs) in Clouds is performed on sets of virtualized Cloud resources that start being exhausted right after their allocation disregarding whether tasks are being executed. In addition, BoTs may be executed in potentially heterogeneous sets of Cloud resources, which may be either previously allocated for a different and fixed number of hours or dynamically reallocated as needed. In this paper, a family of 14 scheduling heuristics for concurrently executing BoTs in Cloud environments is proposed. The Cloud scheduling heuristics are adapted to the resource allocation settings (e.g., 1-hour time slots) of Clouds by focusing on maximizing Cloud resource utilization based on the remaining allocation times of Cloud resources. Cloud scheduling heuristics supported by information about BoT tasks (e.g., task size) and/or Cloud resource performances are proposed. Additionally, scheduling heuristics that require no information of either Cloud resources or tasks are also proposed. The Cloud scheduling heuristics support the dynamic inclusion of new Cloud resources while scheduling and executing a given BoT without rescheduling. Furthermore, an elastic Cloud resource allocation mechanism that autonomously and dynamically reallocates Cloud resources on demand to BoT executions is proposed. Moreover, an agent-based Cloud BoT scheduling approach that supports concurrent and parallel scheduling and execution of BoTs, and concurrent and parallel dynamic selection and composition of Cloud resources (by making use of the well-known contract net protocol) from multiple and distributed Cloud providers is designed and implemented. Empirical results show that BoTs can be (i) efficiently executed by attaining similar (in some cases shorter) makespans to commonly used benchmark heuristics (e.g., Max–min), (ii) effectively executed by achieving a 100% success execution rate even with high BoT execution request rates and executing BoTs in a concurrent and parallel manner, and that (iii) BoTs are economically executed by elastically reallocating Cloud resources on demand.

Item Type: Article
DOI/Identification number: 10.1016/j.future.2012.01.005
Uncontrolled keywords: Scheduling heuristics; Bag-of-tasks applications; Cloud computing; Multi-agent systems; Agent-based Cloud computing; Elastic Cloud resource allocation
Subjects: Q Science > Q Science (General) > Q335 Artificial intelligence
Q Science > QA Mathematics (inc Computing science) > QA 75 Electronic computers. Computer science
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
Depositing User: Kwang Mong Sim
Date Deposited: 29 Oct 2012 14:18 UTC
Last Modified: 16 Nov 2021 10:09 UTC
Resource URI: (The current URI for this page, for reference purposes)

University of Kent Author Information

Sim, Kwang Mong.

Creator's ORCID:
CReDIT Contributor Roles:
  • Depositors only (login required):

Total unique views for this document in KAR since July 2020. For more details click on the image.