|
|||||
|
|
| 成本约束的网格工作流时间优化方法 | |
| 引用本文： | 苑迎春,李小平,王茜,王克俭.成本约束的网格工作流时间优化方法[J].计算机研究与发展,2009,46(2). |
| 作者姓名： | 苑迎春 李小平 王茜 王克俭 |
| 作者单位： | 1. 河北农业大学信息科学与技术学院,河北保定,071001;东南大学计算机科学与工程学院,南京,210096 2. 东南大学计算机科学与工程学院,南京,210096;计算机网络和信息集成教育部重点实验室,东南大学,南京,210096 3. 河北农业大学信息科学与技术学院,河北保定,071001 |
| 基金项目： | 国家自然科学基金，国家高技术研究发展计划(863计划)，河北省科学技术研究与发展计划项目 |
| 摘 要： | 针对成本约束有向无环图DAG(directed acyclic graph)表示的网格工作流完工时间最小化问题,提出两个基于优先级规则的迭代启发算法.算法利用并行活动特征定义正向分层和逆向分层两个概念,将其分别引入最大收益规则MP(maximum profit),得到正分层最大收益规则MPTL(maximum profit with top level)和逆分层最大收益规则MPBL(maximum profit with bottom level).两规则每次迭代尽量以完工时间的最小增加换取总费用的最大降低,逐步将分层初始解构造为满足成本约束的可行解.模拟结果表明,两规则在获得较少迭代次数和运行时间的同时,能显著改进MP规则的平均性能,且MPBL优于MPTL. |
| 关 键 词： | 服务网格 工作流 迭代启发算法 正向分层 逆向分层 |
Time Optimization Heuristics for Scheduling Budget-Constrained Grid Workflows |
|
| Yuan Yingchun,Li Xiaoping,Wang Qian,Wang Kejian.Time Optimization Heuristics for Scheduling Budget-Constrained Grid Workflows[J].Journal of Computer Research and Development,2009,46(2). | |
| Authors: | Yuan Yingchun Li Xiaoping Wang Qian Wang Kejian |
| Affiliation: | Faculty of Information Science and Technology;Agricultural University of Hebei;Baoding;Hebei 071001;School of Computer Science and Engineering;Southeast University;Nanjing 210096;Ministry of Education Key Laboratory of Computer Network and Information Integration;Nanjing 210096 |
| Abstract: | Workflow scheduling which guarantees anticipated QoS (quality of service) is a fundamental and complex problem in grids. In this paper,the budget-constrained scheduling of workflows represented by DAG (directed acyclic graph) with the objective of time optimization is considered. In general,the optimization problem is NP-hard. Two new iterative heuristics based on priority rules are proposed. According to the property of parallel activities in DAG,two concepts called TL (top level) and BL (bottom level) are... |
| Keywords: | service grid workflow iterative heuristics top level bottom level |
| 本文献已被 CNKI 万方数据 等数据库收录！ | |