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

作     者：Gutierrez-Garcia, J. Octavio Sim, Kwang-Mong 

作者机构：Gwangju Inst Sci & Technol Dept Informat & Commun Kwangju 500712 South Korea Univ Kent Sch Comp Chatham ME4 4AG Kent England 

出 版 物：《FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE》 (下代计算机系统)

年 卷 期：2013年第29卷第7期

页      面：1682-1699页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：National Research Foundation of Korea, NRF, (KRF-2009-220-D00092) Korea Science and Engineering Foundation, KOSEF, (MEST 2009-0065329) 

主　　题：Scheduling heuristics Bag-of-tasks applications Cloud computing Multi-agent systems Agent-based Cloud computing Elastic Cloud resource allocation 

摘      要：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 ROT 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 i