基于贪心策略的网格工作流费用优化算法  

Grid workflow scheduling based on greedy algorithm

作　　者：邓定兰[1] 于炯[1] 刘俊祥[1] 汪明军[1] 

机构地区：[1]新疆大学信息科学与工程学院,乌鲁木齐830046

出　　处：《计算机应用研究》2010年第5期1714-1716,1719,共4页Application Research of Computers

基　　金：国家自然科学基金资助项目(60563002;60863003);国家教育部"春晖计划"资助项目(Z2005-1-65009)

摘　　要：针对有向无环图描述的截止期约束下的网格工作流费用优化问题,提出了基于贪心策略的网格工作流费用优化算法GSA-GW(greedyschedulingalgorithmforgrid workflow)和IGSA-GW(improved GSA-GW)。算法首先在当前分配下将截止期转换为各任务的全局时间浮差,各任务再在全局时间浮差的限制下按照两种贪心策略选择备选资源替换原有分配。实验结果证明,两算法能较好地优化工作流费用,提高工作流调度效率。The efficient scheduling of workflow applications represented by DAG（directed acrylic graph） with the objective of time-cost optimization is fundamental and intractable in computational grid.To solve this problem,this paper put forward two new algorithms GSA-GW and IGSA-GW.Under the current distribution,this paper converted deadline into slot time SLOT for every task,then greedily replaced the distribution in the limitation of SLOT. The results show that the algorithms can optimize workflow costs better,and improve scheduling efficiency.

关 键 词：网格工作流 任务调度 贪心策略 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]