云中混合工作流构造策略与调度算法

doi:10.19665/j.issn1001-2400.20241006

西安电子科技大学学报 ›› 2025, Vol. 52 ›› Issue (3): 257-270.doi: 10.19665/j.issn1001-2400.20241006

• 第二十七届中国科协年会——AI时代网络技术创新 • 上一篇

云中混合工作流构造策略与调度算法

赵冉¹^,²(), 赵辉¹^,²^,³(), 王嘉良¹(), 王静¹(), 万波¹^,²^,³(), 王泉¹^,²()

1.西安电子科技大学计算机科学与技术学院,陕西西安 710071
2.陕西省智能人机交互与可穿戴技术重点实验室,陕西西安 710071
3.西安电子科技大学杭州研究院,浙江杭州 311231

收稿日期:2024-02-20 出版日期:2025-06-20 发布日期:2024-10-23
通讯作者: 王静(1981—),女,副教授,博士,E-mail:wangjing@mail.xidian.edu.cn
作者简介:赵冉(2000—),女,西安电子科技大学硕士研究生,E-mail:23031212085@stu.xidian.edu.cn
赵辉(1983—),男,副教授,博士,E-mail:hzhao@mail.xidian.edu.cn
王嘉良(1998—),男,西安电子科技大学硕士研究生,E-mail:20181213882@stu.xidian.edu.cn
万波(1976—),男,教授,博士,E-mail:wanbo@xidian.edu.cn
王泉(1970—),男,教授,博士,E-mail:qwang@xidian.edu.cn
基金资助:
陕西省重点研发计划(2024GX-YBXM-010);陕西省重点研发计划(2024GX-YBXM-140);陕西省重点研发计划(2024GX-YBXM-039);陕西省创新能力支撑计划(2023-CX-TD-08);陕西省秦创原“科学家+工程师”团队(2023KXJ-040);中央高校基本科研业务费专项资金(ZYTS24089)

Hybrid workflows construction strategy and scheduling algorithm in cloud

ZHAO Ran¹^,²(), ZHAO Hui¹^,²^,³(), WANG Jialiang¹(), WANG Jing¹(), WAN Bo¹^,²^,³(), WANG Quan¹^,²()

1. School of Computer Science and Technology,Xidian University,Xi’an 710071,China
2. Shaanxi Province Key Laboratory of Smart Human-Computer Interaction and Wearable Technology,Xi’an 710071,China
3. Hangzhou Institute of Technology,Xidian University,Hangzhou 311231,China

Received:2024-02-20 Online:2025-06-20 Published:2024-10-23

摘要/Abstract

摘要：

工作流执行过程中,由于子任务之间的数据依赖产生大量的任务等待时隙,造成云平台计算资源空闲和资源利用率低。现有的工作流调度方法虽然可以通过数据依赖分析提高工作流执行效率,但它们都没有考虑异构混合工作流的调度。针对这一问题,笔者以最小化任务完工时间、提高任务按时交付率、提升批处理任务吞吐量以及资源利用率为目标,提出了云中混合工作流构造策略与调度算法。首先,建立了混合工作流三层调度架构,分别完成混合工作流的分类、构造与调度。其次,为了充分利用任务等待时隙,提出了基于背包的混合工作流构造策略,将批处理任务调度至工作流子任务等待时隙执行,实现混合工作流构造。再次,提出了基于信息熵的工作流调度算法和基于粒子群算法的资源动态伸缩策略,解决工作流调度的多目标优化问题,并实时监测调整计算资源,保障混合工作流的顺利完成。最后,仿真实验结果表明所提出的构造策略与调度算法能够有效缩短任务完工时间,保证任务按时交付率,提升批处理任务吞吐量,提高资源利用率。

关键词: 混合工作流, 任务等待时隙, 调度算法, 多目标优化

Abstract:

During workflow execution,a large number of task waiting time slots are generated due to data dependencies between subtasks,resulting in idle computing resources and low resource utilization of the cloud platform.Although existing workflow scheduling methods can improve the workflow execution efficiency through data dependency analysis,they do not consider the scheduling of heterogeneous hybrid workflows.To solve this problem,a hybrid workflow construction strategy and scheduling algorithm in the cloud is proposed with the goal of minimizing the task completion time,enhancing the on-time task delivery rate,increasing batch task throughput and resource utilization.First,a three-layer scheduling architecture for hybrid workflows is established to complete the classification,construction and scheduling of hybrid workflows.Second,in order to make full use of the task waiting time slot,a backpack-based hybrid workflow construction strategy is proposed,which schedules batch tasks to the waiting time slot of workflow subtasks to realize hybrid workflow construction.Third,a workflow scheduling algorithm based on the information entropy and a resource dynamic scaling algorithm based on the particle swarm algorithm are proposed to solve the multi-objective optimization problem of workflow scheduling.It can monitor and adjust computing resources in real time to ensure the smooth completion of hybrid workflow.Finally,simulation experimental results show that the proposed construction strategy and scheduling algorithm can shorten the task completion time,ensure the on-time task delivery rate,and improve batch task throughput and resource utilization.

Key words: hybrid workflows, task wait time slot, scheduling algorithm, multi-objective optimization

中图分类号:

TP301.6

赵冉, 赵辉, 王嘉良, 王静, 万波, 王泉. 云中混合工作流构造策略与调度算法[J]. 西安电子科技大学学报, 2025, 52(3): 257-270.

ZHAO Ran, ZHAO Hui, WANG Jialiang, WANG Jing, WAN Bo, WANG Quan. Hybrid workflows construction strategy and scheduling algorithm in cloud[J]. Journal of Xidian University, 2025, 52(3): 257-270.

图/表 16

图1

图2

表1

表2

表3

图3

图4

图5

图6

图7

图8

图9

图10

图11

图12

图13

参考文献 22

[1]	ZHOU Z, SHOJAFAR M, ALAZAB M, et al. IECL:An Intelligent Energy Consumption Model for Cloud Manufacturing[J]. IEEE Transactions on Industrial Informatics, 2022, 18(12):8967-8976.
[2]	SUN Z, ZHANG B, GU C, et al. ET2FA:AHybrid Heuristic Algorithm for Deadline-Constrained Workflow Scheduling in Cloud[J]. IEEE Transactions on Services Computing, 2022, 16(3):1807-1821.
[3]	ALLAHVERDYAN A, ZHADAN A, KONDRATOV I, et al. MonteCarlo Tree Search with Adaptive Estimation for DAG Scheduling[C]// International Conference on Swarm Intelligence. Berlin:Springer,2023:335-349.
[4]	GUAN F, PENG L, QIAO J, et al. A New Federated Scheduling Algorithm for Arbitrary-Deadline DAG Tasks[J]. IEEE Transactions on Computers, 2023, 72(8):2264-2277.
[5]	SUN B, THEILE M, QIN Z, et al. Edge Generation Scheduling for DAG Tasks Using Deep Reinforcement Learning[J]. IEEE Transactions on Computers, 2024, 73(4):1034-1047.
[6]	MURAD S, BADEEL R, SALIH N, et al. Optimized Min-MinTask Scheduling Algorithm for Scientific Workflows in a Cloud Environment[J]. Journal of Theoretical and Applied Information Technology, 2022, 100(2):480-506.
[7]	KAMALAM G, SENTAMILSELVAN K. SLA-Based Group Tasks Max-Min (Gtmax-Min) Algorithm for Task Scheduling in Multi-Cloud Environments[J]. Operationalizing Multi-Cloud Environments:Technologies,Tools and Use Cases,2022:105-127.
[8]	ALIYEV I, MACK J, KUMBHARE N, et al. FPGA-Based Minimal Latency HEFT Scheduler for Heterogeneous Computing[C]//2021 6th International Conference on Computer Science and Engineering (UBMK). Piscataway:IEEE,2021:1-5.
[9]	MONIK A, SINGH S, WASON A. Performance Evaluation of Bandwidth Allocating Algorithms in Generalized Multi-Protocol Label Switched Optical Networks to Enhance Quality of Service[J]. IEEE Access, 2022,10:40731-40742.
[10]	CHEN Z, WEI P, LI Y. Combining Neural Network-Based Method with Heuristic Policy for Optimal Task Scheduling in Hierarchical Edge Cloud[J]. Digital Communications and Networks, 2023, 9(3):688-697.
[11]	TANG X, CAO W, TANG H, et al. Cost-Efficient Workflow Scheduling Algorithm for Applications with Deadline Constraint on Heterogeneous Clouds[J]. IEEE Transactions on Parallel and Distributed Systems, 2021, 33(9):2079-2092.
[12]	SAHNI Y, CAO J, YANG L. Data-Aware Task Allocation for Achieving Low Latency in Collaborative Edge Computing[J]. IEEE Internet of Things Journal, 2018, 6(2):3512-3524.
[13]	ZOU Y, LI C, CHEN S. Particle Swarm Optimization Algorithm for Workflow Scheduling Based on Spot Instances[C]// 2024 IEEE 6th Advanced Information Management,Communicates,Electronic and Automation Control Conference (IMCEC). Piscataway:IEEE,2024:649-654.
[14]	ALSAIDY S, ABBOOD A, SAHIB M. Heuristic Initialization of PSO Task Scheduling Algorithm in Cloud Computing[J]. Journal of King Saud University-Computer and Information Sciences, 2022, 34(6):2370-2382.
[15]	WANG Y, ZUO X, WU Z, et al. Variable Neighborhood Search Based Multi-Objective ACO-List Scheduling for Cloud Workflows[J]. The Journal of Supercomputing, 2022, 78(17):18856-18886.
[16]	BELGACEM A, BEGHDAD-BEY K. Multi-Objective Workflow Scheduling in Cloud Computing:Trade-off Between Makespan and Cost[J]. Cluster Computing, 2022, 25(1):579-595.
[17]	SHAMAA S, SHI W, ANKENMANN G.Probability-Based Crossover Genetic Algorithm for Task Scheduling in Cloud Computing[C]// 2023 6th Conference on Cloud and Internet of Things (CIoT). Piscataway:IEEE,2023:231-238.
[18]	王燕. 改进多目标进化算法的云工作流调度[J]. 西安电子科技大学学报, 2019, 46(1):130-136.
	WANG Yan. EnhancedMulti-Objective Evolutionary Algorithm for Workflow Scheduling on the Cloud Platform[J]. Journal of Xidian University, 2019, 46(1):130-136.
[19]	朱思峰, 宋兆威, 陈昊, 等. 智慧交通场景下云边端协同的多目标优化卸载决策[J]. 西安电子科技大学学报, 2024, 51(3):63-75.
	ZHU Sifeng, SONG Zhaowei, CHEN Hao, et al. Multi-Objective Optimization Offloading Decision with Cloud-Side-End Collaboration in Smart Transportation Scenarios[J]. Journal of Xidian University, 2024, 51(3):63-75.
[20]	REDDY P, REDDY K. An Energy Efficient RL Based Workflow Scheduling in Cloud Computing[J]. Expert Systems with Applications, 2023,234:121038.
[21]	JAYANETTI A, AMANDA S, BUYYA R. Multi-Agent Deep Reinforcement Learning Framework for Renewable Energy-Aware Workflow Scheduling on Distributed Cloud Data Centers[J]. IEEE Transactions on Parallel and Distributed Systems, 2024,35:604-615.
[22]	YADAV S, KUMAR R. ASME-SKYR Framework:A Comprehensive Task Scheduling Framework for Mobile Cloud Computing[J]. Wireless Networks, 2024, 30(3):1221-1244.

虚拟机类型	vCPU	Memory/GiB	BW/(Gb·s^-1)	虚拟机类型	vCPU	Memory/GiB	BW/(Gb·s^-1)
M5.large	2	8	10	M5.4xlarge	8	64	10
M5.xlarge	4	16	10	M5.8xlarge	16	128	10
M5.2xlarge	6	32	10	M5.12xlarge	32	192	10

	c₁	c₂	ω
Set 1	1,1.5,2,2.5,3	2	1.5
Set 2	2	1,1.5,2,2.5,3	1.5
Set 3	2	2	0.5,1,1.5,2,2.5

云中混合工作流构造策略与调度算法

Hybrid workflows construction strategy and scheduling algorithm in cloud

RichHTML

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

图/表 16

参考文献 22

相关文章 15

Metrics

本文评价

推荐阅读 0

工作流	任务数量	边数量	工作流	任务数量	边数量
Montage 25	25	45	LIGO 30	30	33
Montage 50	50	100	LIGO 60	60	66
Montage100	100	433	LIGO 100	100	335
CyberShake 30	30	52	SIPHT 30	30	35
CyberShake 50	50	92	SIPHT 50	50	60
CyberShake 100	100	380	SIPHT 100	100	319

[1]	支文韬, 赵辉, 孟繁鑫, 王静, 万波, 王泉. 面向WaaS平台的多工作流容错调度策略[J]. 西安电子科技大学学报, 2025, 52(1): 181-195.
[2]	韩家曦, 赵辉, 冯南之, 王静, 万波, 王泉. 边缘计算平台中面向分簇的半在线调度方法[J]. 西安电子科技大学学报, 2024, 51(6): 104-116.
[3]	余修武, 晋诗琪. 融合VFA和ISSA的多目标优化WSN覆盖算法[J]. 西安电子科技大学学报, 2024, 51(6): 60-72.
[4]	张超, 赵辉, 张智峰, 王静, 万波, 王泉. 边缘协作环境下最小化完工时间任务调度方法[J]. 西安电子科技大学学报, 2024, 51(4): 114-127.
[5]	万梦依, 武燕. 一种新的基于预测的动态多目标进化算法[J]. 西安电子科技大学学报, 2024, 51(3): 124-135.
[6]	朱思峰, 宋兆威, 陈昊, 朱海, 乔蕊. 智慧交通场景下云边端协同的多目标优化卸载决策[J]. 西安电子科技大学学报, 2024, 51(3): 63-75.
[7]	张铂扬, 褚怡, 杨仲平, 周青松. 用于精确干扰波形设计的高效流形算法[J]. 西安电子科技大学学报, 2023, 50(6): 84-92.
[8]	刘景美,闫义博. 人工鱼群特征选择的网络入侵检测系统[J]. 西安电子科技大学学报, 2023, 50(4): 132-138.
[9]	张浩, 覃涛, 徐凌桦, 王霄, 杨靖. 改进多目标蚁狮算法的WSNs节点部署策略[J]. 西安电子科技大学学报, 2022, 49(5): 47-59.
[10]	张宇鹏,吴自力,陈鸣,张璐璐. 面向交叉微服务链的任务调度优化[J]. 西安电子科技大学学报, 2021, 48(6): 32-39.
[11]	杜文占,余志勇,杨剑,姜海滨. 改进NSGA-II算法及监测天线部署优化研究[J]. 西安电子科技大学学报, 2021, 48(5): 239-248.
[12]	刘天宇,王翥. 一种多样性控制的多目标粒子群算法[J]. 西安电子科技大学学报, 2021, 48(3): 106-114.
[13]	杨五四,陈莉,王毅,张茂省. 一种适应度排序的高维多目标粒子群优化算法[J]. 西安电子科技大学学报, 2021, 48(3): 78-84.
[14]	王燕. 改进多目标进化算法的云工作流调度[J]. 西安电子科技大学学报, 2019, 46(1): 130-136.
[15]	韩亚敏;柴争义;李亚伦;朱思峰. 长尾群组推荐的免疫多目标优化实现[J]. 西安电子科技大学学报, 2018, 45(3): 109-116.