查询结果:   蔡艳婧,王强,程实.基于局部关键路径与截止期限分配的云工作流调度算法[J].计算机应用与软件,2019,36(8):220 - 229.
中文标题
基于局部关键路径与截止期限分配的云工作流调度算法
发表栏目
算法
摘要点击数
369
英文标题
CLOUD WORKFLOW SCHEDULING ALGORITHM BASED ON PARTIAL CRITICAL PATH AND DEADLINE DISTRIBUTION
作 者
蔡艳婧 王强 程实 Cai Yanjing Wang Qiang Cheng Shi
作者单位
南通大学电子信息学院 江苏 南通 226019 江苏商贸职业学院电子与信息学院 江苏 南通 226001 南通大学计算机科学与技术学院 江苏 南通 226019   
英文单位
School of Electronic Information,Nantong University, Nantong 226019, Jiangsu, China School of Electronics and Information, Jiangsu Vocational College of Business, Nantong 226001, Jiangsu, China College of Computer Science and Technology, Nantong University, Nantong 226019, Jiangsu, China   
关键词
云计算 工作流调度 期限分配 局部关键路径 期限约束
Keywords
Cloud environment Workflow scheduling Deadline distribution Partial critical path Deadline constraint
基金项目
国家自然科学基金项目(61602267);江苏省高校高端研修资助项目(2018GRFX022);南通市科技计划(指导性)项目(MSZ18080);江苏商贸职业学院课题(SY20171212-07)
作者资料
蔡艳婧,副教授,主研领域:大数据,智能算法,移动计算。王强,副教授。程实,实验师。 。
文章摘要
为了解决云计算中截止期限约束下的工作流调度代价优化问题,提出一种基于局部关键路径和截止期限分配的工作流任务调度算法。为了满足期限约束,并最小化执行代价,算法将工作流任务的调度过程划分为两个阶段:期限分配阶段和调度资源选择阶段。期限分配阶段定义工作流的局部关键路径,并以递归的方式在局部关键路径上的任务间进行子期限分配;调度资源选择阶段在满足任务子期限的同时,为每个任务选择执行代价最低的资源进行任务调度,以实现调度代价优化。分析算法的时间复杂度,并通过一个算例对算法的实现思路进行了详细阐述。通过科学工作流结构的仿真实验,证明了算法不仅可以满足截止期限约束,而且可以降低工作流任务的执行代价。
Abstract
For optimizing workflow schedulimg cost under deadline constraint in cloud, we presented a workflow scheduling algorithm based on partial critical path and deadline distritution. For meeting the deadline constraint and minimizing the execution cost, our algorithm divided the workflow scheduling process into two steps: the deadline distribution stage and the scheduling resource selection. In the deadline distribution stage, we defined the partial critical path of the workflow and recursively assigned sub-deadlines to the tasks on the partial critical path. In the scheduling resource selection, we assigned the cheapest resource to each task to optimize the scheduling cost while meeting its sub-deadline. The time complexity of our algorithm was analyzed and an example was designed to elaborate the implement idea of our algorithm. Through the simulation experiments of scientific workflow, it is proved that our algorithm can better reduce the workflow execution cost under meeting deadline.
下载PDF全文