A scheduling algorithm for applications in a cloud computing system with communication changes

作     者：Shao, Xia Xie, Zhiqiang 

作者机构：Harbin Univ Sci & Technol Coll Comp Sci & Technol Harbin Heilongjiang Peoples R China 

出 版 物：《EXPERT SYSTEMS》 (专家系统；国际知识工程杂志)

年 卷 期：2019年第36卷第2期

页      面：e12356-e12356页

核心收录：

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

基　　金：China Postdoctoral Science Foundation [2016M591541] Heilongjiang Province Postdoctoral Science Foundation [LBHQ13092] National Natural Science Foundation of China [61370086/61772160/61602133] Research Fund for the Doctoral Program of Higher Education of China Science and Technology Research Foundation of Heilongjiang Province Education Department Heilongjiang Postdoctoral Science Foundation [LBH-Z15096] 

主　　题：CC-DAG cloud computing DPSS network time series scheduling algorithm 

摘      要：This paper proposes a scheduling algorithm to solve the problem of task scheduling in a cloud computing system with time-varying communication conditions. This algorithm converts the scheduling problem with communication changes into a directed acyclic graph (DAG) scheduling problem for existing fuzzy communication task nodes, that is, the scheduling problem for a communication-change DAG (CC-DAG). The CC-DAG contains both computation task nodes and communication task nodes. First, this paper proposes a weighted time-series network bandwidth model to solve the indefinite processing time (cost) problem for a fuzzy communication task node. This model can accurately predict the processing time of a fuzzy communication task node. Second, to address the scheduling order problem for the computation task nodes, a dynamic pre-scheduling search strategy (DPSS) is proposed. This strategy computes the essential paths for the pre-scheduling of the computation task nodes based on the actual computation costs (times) of the computation task nodes and the predicted processing costs (times) of the fuzzy communication task nodes during the scheduling process. The computation task node with the longest essential path is scheduled first because its completion time directly influences the completion time of the task graph. Finally, we demonstrate the proposed algorithm via simulation experiments. The experimental results show that the proposed DPSS produced remarkable performance improvement rate on the total execution time that ranges between 11.5% and 21.2%. In view of the experimental results, the proposed algorithm provides better quality scheduling solution that is suitable for scientific application task execution in the cloud computing environment than HEFT, PEFT, and CEFT algorithms.