电子学报
電子學報
전자학보
ACTA ELECTRONICA SINICA
2009年
7期
1457-1464
,共8页
苑迎春%李小平%王茜%张晓东
苑迎春%李小平%王茜%張曉東
원영춘%리소평%왕천%장효동
网格计算%工作流%有向无环图%优先级规则%时间耦合强度
網格計算%工作流%有嚮無環圖%優先級規則%時間耦閤彊度
망격계산%공작류%유향무배도%우선급규칙%시간우합강도
网格资源需求的不断增长使价格成为资源进行竞争的有效手段,有向无环图功DAG(Directed Acyclic Graph)表示的工作流时间费用优化问题是网格环境下一个重要问题.通常情况下,DAG应用调度属于NP-Hard问题.通过分析活动间的时序特征,给出时间耦合强度TCS(Time-dependent Coupling Strength)的定义,用于标识一个活动最大的时间耦合活动个数;将其作为优先级规则的一个重要信息和BF规则(Best Fit)结合,设计出时间耦合强度最适规则BFTCS(Best Fit with Time-dependent Coupling Strength),用于启发式算法的改进阶段,逐步提高初始可行解的性能.模拟实验结果表明,相对现有的启发式算法,基于BFTCS规则的启发算法能获得最好的性能和较快的运行效率;最后讨论了问题参数对算法性能和效率的影响.
網格資源需求的不斷增長使價格成為資源進行競爭的有效手段,有嚮無環圖功DAG(Directed Acyclic Graph)錶示的工作流時間費用優化問題是網格環境下一箇重要問題.通常情況下,DAG應用調度屬于NP-Hard問題.通過分析活動間的時序特徵,給齣時間耦閤彊度TCS(Time-dependent Coupling Strength)的定義,用于標識一箇活動最大的時間耦閤活動箇數;將其作為優先級規則的一箇重要信息和BF規則(Best Fit)結閤,設計齣時間耦閤彊度最適規則BFTCS(Best Fit with Time-dependent Coupling Strength),用于啟髮式算法的改進階段,逐步提高初始可行解的性能.模擬實驗結果錶明,相對現有的啟髮式算法,基于BFTCS規則的啟髮算法能穫得最好的性能和較快的運行效率;最後討論瞭問題參數對算法性能和效率的影響.
망격자원수구적불단증장사개격성위자원진행경쟁적유효수단,유향무배도공DAG(Directed Acyclic Graph)표시적공작류시간비용우화문제시망격배경하일개중요문제.통상정황하,DAG응용조도속우NP-Hard문제.통과분석활동간적시서특정,급출시간우합강도TCS(Time-dependent Coupling Strength)적정의,용우표식일개활동최대적시간우합활동개수;장기작위우선급규칙적일개중요신식화BF규칙(Best Fit)결합,설계출시간우합강도최괄규칙BFTCS(Best Fit with Time-dependent Coupling Strength),용우계발식산법적개진계단,축보제고초시가행해적성능.모의실험결과표명,상대현유적계발식산법,기우BFTCS규칙적계발산법능획득최호적성능화교쾌적운행효솔;최후토론료문제삼수대산법성능화효솔적영향.
