Grid Workflows Schedule Based on Priority Rules

YUAN Ying-chun; LI Xiao-ping; WANG Qian; ZHANG Xiao-dong

您当前的位置：

首页 >

文章列表页 >

Grid Workflows Schedule Based on Priority Rules

更新时间：2025-07-16

- Grid Workflows Schedule Based on Priority Rules
- Acta Electronica Sinica Vol. 37, Issue 7, Pages: 1457-1464(2009)
- 作者机构：
  
  1. 河北农业大学信息科学与技术学院,河北,保定,071001
  2. 东南大学计算机科学与工程学院,江苏,南京,210096
  3. 东南大学计算机网络和信息集成教育部重点实验室,江苏,南京,210096
  4. 河北农业大学信息科学与技术学院河北保定,071001
  5. 东南大学计算机科学与工程学院江苏南京,210096
  6. 东南大学计算机网络和信息集成教育部重点实验室江苏南京,210096
- 作者简介：
- 基金信息：
- DOI：
  CLC： TP393
- Published：2009
- 稿件说明：
移动端阅览
YUAN Ying-chun, LI Xiao-ping, WANG Qian, et al. Grid Workflows Schedule Based on Priority Rules[J]. Acta Electronica Sinica, 2009, 37(7): 1457-1464.
DOI：

YUAN Ying-chun, LI Xiao-ping, WANG Qian, et al. Grid Workflows Schedule Based on Priority Rules[J]. Acta Electronica Sinica, 2009, 37(7): 1457-1464. DOI：

摘要

网格资源需求的不断增长使价格成为资源进行竞争的有效手段

有向无环图DAG(Directed Acyclic Graph)表示的工作流时间费用优化问题是网格环境下一个重要问题.通常情况下

DAG应用调度属于NP-Hard问题.通过分析活动间的时序特征

给出时间耦合强度TCS (Time-dependent Coupling Strength)的定义

用于标识一个活动最大的时间耦合活动个数;将其作为优先级规则的一个重要信息和BF规则(Best Fit)结合

设计出时间耦合强度最适规则BFTCS ( Best Fit with Time-dependent Coupling Strength)

用于启发式算法的改进阶段

逐步提高初始可行解的性能.模拟实验结果表明

相对现有的启发式算法

基于BFTCS规则的启发算法能获得最好的性能和较快的运行效率;最后讨论了问题参数对算法性能和效率的影响.

Abstract

The increasing demand for grid computing resources calls for an incentive-compatible pricing mechanism for differentiated service qualities.The Time-Cost tradeoff problem for grid workflow applications described by Directed Acyclic Graph (DAG) becomes a significant problem.DAG-based optimization problem has been shown to be NP-hard in general cases.In this paper

a new concept called TCS (Time-dependent Coupling Strength) is introduced

which is identified for a given activity the maximum number of time-dependent coupling activities.By incorporating it into priority rule BF (Best Fit) which only takes into account the ratio of the cost improvement to the increase of duration of an activity

a novel priority rule BFTCS (Best Fit with Time-dependent Coupling Strength) is proposed

which is implemented in a heuristic to improve further the feasible initial solutions.Computational experiments indicate that rule BFTCS based heuristic can perform better than other existing heuristics but require a little more computation time.As well

the impact of problem parameters on the heuristics is discussed.

关键词

Keywords

references

Views

1431

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Soundness Analysis of the Multi-cases Workflow Model Based on Home State

Co-Scheduling Model for Independent Tasks with Deadline Constraint in Computational Grid

Resource Allocation Balancing of Workflow Based on Directed Hypergraph

Related Author

JIANG Chang-jun

YAN Chun-gang

PANG Shan-chen

HU Zhi-gang

XIAO Peng

ZOU Li-da

GONG Bin

MA Yan

Related Institution

School of Information Science and EngineeringShandong University of Science and TechnologyQingdaoShandong 266510China

Department of Computer Science and EngineeringTongji UniversityShanghai 200092China

School of Information Science and Engineering,Shandong University of Science and Technology

Department of Computer Science and Engineering,Tongji University

School of SoftwareCentral South UniversityChangshaHunan 410083China

⁰