基于图割的云环境中工作流调度改进算法

doi:10.3969/j.issn.1006-2475.2014.02.012

计算机与现代化 ›› 2014, Vol. 0 ›› Issue (2): 51-54.doi: 10.3969/j.issn.1006-2475.2014.02.012

基于图割的云环境中工作流调度改进算法

（西北工业大学计算机学院，陕西西安 710072）

收稿日期:2013-09-16 出版日期:2014-02-14 发布日期:2014-02-14
作者简介:邓碧林(1990-)，男，湖南邵阳人，西北工业大学计算机学院硕士研究生，研究方向：云计算；王云岚(1970-)，女，副教授，博士，研究方向：云计算，高性能计算。

An Improved Algorithm for Workflow Scheduling in Cloud Environment Based on Graph Cut

(School of Computer Science, Northwestern Polytechnical University, Xi’an 710072, China)

Received:2013-09-16 Online:2014-02-14 Published:2014-02-14

摘要/Abstract

摘要： 为提高云环境中工作流的执行效率，通过调整工作流引擎的调度策略，将MCGP（Multi Constraint Graph Partitioning）算法应用于工作流调度引擎，并对其不足，提出改进的MCGRP(Multi Constraint Graph Ratio Partitioning)算法。模拟实验表明，本文的调度算法有效地提高了系统的资源利用率和云环境中工作流的执行效率。

关键词: 云计算, 工作流, 调度, 图割

Abstract: To improve the efficiency of workflow deployed in cloud environment, we applied multi constraint graph partitioning (MCGP) algorithm in workflow engine. Then ratio cut was introduced to MCGP to improve its efficiency. Simulation indicates that our scheduling policy can significantly improve the efficiency of the workflow.

Key words: cloud computing, workflow, scheduling, graph cut

中图分类号:

TP312

邓碧林，王云岚. 基于图割的云环境中工作流调度改进算法[J]. 计算机与现代化, 2014, 0(2): 51-54.

DENG Bi-lin, WANG Yun-lan.

An Improved Algorithm for Workflow Scheduling in Cloud Environment Based on Graph Cut

[J]. Computer and Modernization, 2014, 0(2): 51-54.

参考文献

[1] Hoffa C, Mehta G, Freeman T, et al. On the use of cloud computing for scientific workflows[C]// Proceedings of the 4th IEEE International Conference on eScience. 2008:640-645.

[2] 刘少伟,孔令梅,任开军,等. 云环境下优化科学工作流执行性能的两阶段数据放置与任务调度策略[J]. 计算机学报, 2011,34(11):2121-2130.

[3] Tanaka M, Tatebe O. Workflow scheduling to minimize data movement using multi-constraint graph partitioning[C]// Proceedings of the 12th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing. 2012:65-72.

[4] Karypis G, Kumar V. Multilevel k-way Partitioning Scheme for Irregular Graphs[R]. University of Minnesota, 1995.

[5] Yuan D, Yang Y, Liu X, et al. A cost-effective strategy for intermediate data storage in scientific cloud workflow systems[C]// Proceedings of the 2010 IEEE International Symposium on Parallel & Distributed Processing. 2010.

[6] Karypis G, Kumar V. Multilevel algorithms for multi-constraint graph partitioning[C]// Proceedings of the 1998 ACM/IEEE Conference on Supercomputing. 1998:64-76.

[7] Deng K, Song J, Ren K, et al. Graph-cut based coscheduling strategy towards efficient execution of scientific workflows in collaborative cloud environments[C]// Proceedings of the 12th IEEE/ACM International Conference on Grid Computing. 2011:34-41.

[8] Foster I, Zhao Y, Raicu I, et al. Cloud computing and grid computing 360-degree compared[C]// Proceedings of the 2008 IEEE Workshop on Grid Computing Environments. 2008:60-69.

[9] Armbrust M, Fox A, Griffith R, et al. A view of cloud computing[J]. Communications of the ACM, 2010,53(4):50-58.

[10] Ostermann S, Iosup A, Yigitbasi N, et al. A performance analysis of EC2 cloud computing services for scientific computing[M]// Cloud Computing. Springer, Berlin, Heidelberg, 2010,34:115-131.

[11] Nurmi D, Wolski R, Grzegorczyk C, et al. The eucalyptus open-source cloud-computing system[C]// Proceedings of the 9th IEEE/ACM International Symposium on Cluster Computing and the Grid. 2009:124-131.

[12] Youseff L, Butrico M, Da Silva D. Toward a unified ontology of cloud computing[C]// Proceedings of the 2008 IEEE Workshop on Grid Computing Environments. 2008:42-51.

[13] Velte T, Velte A, Elsenpeter R. Cloud Computing: A Practical Approach[M]. McGraw-Hill, 2009.

[14] Marinos A, Briscoe G. Community cloud computing[C]// Proceedings of the 1st International Conference on Cloud Computing. 2009:472-484.

[1]	李桃迎, 李蒙, 武梦乔. 基于异构时空图卷积网络的出租车客流预测[J]. 计算机与现代化, 2024, 0(11): 13-18.
[2]	王佳1, 顾文俊1, 鞠炜刚2, 李玉维1, 张云龙2, 米传民3, 周志鹏3. 基于多元级差优良化遗传算法的环境拓扑结构任务调度[J]. 计算机与现代化, 2024, 0(10): 65-73.
[3]	张永亮1, 2, 王家润2. 嵌入式系统全国路径规划算法[J]. 计算机与现代化, 2024, 0(10): 80-86.
[4]	杨波, 王宏杰, 徐胜超, 毛明扬, 蒋金陵, 蒋大锐. 一种面向生物基因多序列比对算法的任务调度方法[J]. 计算机与现代化, 2024, 0(07): 7-12.
[5]	王佳1, 张云龙1, 鞠炜刚1, 周志鹏2, 米传民2. 一种通用的服务器类环境资源节能降耗平台[J]. 计算机与现代化, 2024, 0(05): 61-68.
[6]	杨柯1, 潘大志1, 2, 池莹1. 改进蜉蝣算法求解工艺规划与调度集成问题[J]. 计算机与现代化, 2024, 0(04): 92-98.
[7]	王宏杰, 徐胜超, 杨波, 毛明扬, 蒋金陵. 基于SRv6技术的云网安全服务链自动编排方法[J]. 计算机与现代化, 2024, 0(01): 1-5.
[8]	何玉鹏, 陶勇, 王必恒, 赵英男. 智能配电网边缘计算研究现状与展望[J]. 计算机与现代化, 2023, 0(08): 87-92.
[9]	杨波, 徐胜超. 基于SRv6服务链的云网专线场景安全防护方法[J]. 计算机与现代化, 2023, 0(08): 107-111.
[10]	韩沐枫. 计及需求响应的微电网多时间尺度调度仿真[J]. 计算机与现代化, 2023, 0(03): 102-106.
[11]	周永福, 徐胜超. 基于双层规划的容器云资源动态配置算法[J]. 计算机与现代化, 2022, 0(12): 1-5.
[12]	毛明扬, 徐胜超. 可信赖云计算的通信终端攻击行为识别算法[J]. 计算机与现代化, 2022, 0(11): 37-42.
[13]	田云娜, 田园, 刘雪, 赵彦霖. 一种改进的求解柔性作业车间调度问题的灰狼算法[J]. 计算机与现代化, 2022, 0(08): 78-85.
[14]	曹禹, 李晓辉, 刘忠麟, 贾贺, 费志伟. 云环境大数据工作流编排管理系统研究综述[J]. 计算机与现代化, 2022, 0(01): 41-53.
[15]	徐明, 张剑铭, 陈松航, 陈豪. 柔性作业车间调度问题的多目标优化算法[J]. 计算机与现代化, 2021, 0(12): 1-6.

基于图割的云环境中工作流调度改进算法

An Improved Algorithm for Workflow Scheduling in Cloud Environment Based on Graph Cut

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价