TY - GEN
T1 - T2FA
T2 - 14th IEEE International Conference on Cloud Computing, CLOUD 2021
AU - Sun, Zaixing
AU - Gu, Chonglin
AU - Huang, Hejiao
AU - Zhang, Honglin
N1 - Publisher Copyright:
© 2021 IEEE.
PY - 2021/9
Y1 - 2021/9
N2 - Workflow scheduling is one of the most challenging problems in cloud computing. This paper proposes a heuristic algorithm task type first algorithm (T2FA) for solving deadline-constrained workflow scheduling in cloud with multicore resource (DWS_CMR). The objectives to be minimized are the maximal completion time (i.e., makespan) and the total costs. Firstly, resource model and workflow application model are introduced. Resource model has the configurations of multicore, processing capacity, bandwidth and leasing price, and workflow application model is described by directed acyclic graph (DAG). Based on above models, the mathematical model of DWS-CMR is established, which allows multiple tasks to run concurrently on multicore resources. Secondly, to exploit the characteristics of the problem, the structures of DAG are decomposed and formulated. Merging tasks conforming to the first structure into task blocks can simplify DAG. Four special types of tasks are extracted from the second and third structures, and are preferentially scheduled in task scheduling stage. Then, a new interrelated calculation method of estimated start time and actual start time of tasks is proposed, which can complete the task-To-resource mapping. Finally, T2FA is devised, which incorporates two important phases, including pre-processing and task scheduling. Experimental results show that T2FA can achieve significantly better schedules in most test cases compared to several existing algorithms.
AB - Workflow scheduling is one of the most challenging problems in cloud computing. This paper proposes a heuristic algorithm task type first algorithm (T2FA) for solving deadline-constrained workflow scheduling in cloud with multicore resource (DWS_CMR). The objectives to be minimized are the maximal completion time (i.e., makespan) and the total costs. Firstly, resource model and workflow application model are introduced. Resource model has the configurations of multicore, processing capacity, bandwidth and leasing price, and workflow application model is described by directed acyclic graph (DAG). Based on above models, the mathematical model of DWS-CMR is established, which allows multiple tasks to run concurrently on multicore resources. Secondly, to exploit the characteristics of the problem, the structures of DAG are decomposed and formulated. Merging tasks conforming to the first structure into task blocks can simplify DAG. Four special types of tasks are extracted from the second and third structures, and are preferentially scheduled in task scheduling stage. Then, a new interrelated calculation method of estimated start time and actual start time of tasks is proposed, which can complete the task-To-resource mapping. Finally, T2FA is devised, which incorporates two important phases, including pre-processing and task scheduling. Experimental results show that T2FA can achieve significantly better schedules in most test cases compared to several existing algorithms.
KW - Cloud Computing
KW - Deadline Constraint
KW - Directed Acyclic Graph
KW - Multicore Resource
KW - Workflow Scheduling
UR - https://www.scopus.com/pages/publications/85119326774
U2 - 10.1109/CLOUD53861.2021.00048
DO - 10.1109/CLOUD53861.2021.00048
M3 - 会议稿件
AN - SCOPUS:85119326774
T3 - IEEE International Conference on Cloud Computing, CLOUD
SP - 345
EP - 354
BT - Proceedings - 2021 IEEE 14th International Conference on Cloud Computing, CLOUD 2021
A2 - Ardagna, Claudio Agostino
A2 - Chang, Carl K.
A2 - Daminai, Ernesto
A2 - Ranjan, Rajiv
A2 - Wang, Zhongjie
A2 - Ward, Robert
A2 - Zhang, Jia
A2 - Zhang, Wensheng
PB - IEEE Computer Society
Y2 - 5 September 2021 through 11 September 2021
ER -