| 黄飞雪,姜新娜,李志洁,侯铁珊.经济网格中基于剪枝策略的时间-费用优化任务调度[J].,2008,(2):298-303 |
| 经济网格中基于剪枝策略的时间-费用优化任务调度 |
| Task scheduling based on cost-time optimization of pruning strategy in economic grid |
| |
| DOI：10.7511/dllgxb200802026 |
| 中文关键词: 费用约束 任务调度 剪枝 时限 网格计算 |
| 英文关键词: cost constraint task scheduling pruning deadline grid computing |
| 基金项目:辽宁省社会科学规划基金资助项目L07DJY065；大连理工大学人文社会科学研究基金资助项目(DUTHS2007321). |
|
| 摘要点击次数: 936 |
| 全文下载次数: 728 |
| 中文摘要: |
| 由于在经济网格环境下，存在着资源异构和分布的特征，网格任务调度变成了一个复杂的问题．为此，针对独立任务，在考虑用户的服务质量经济需求偏好的基础上，提出了一个优化用户时间和费用的任务调度方案选择算法．该算法首先将网格中兼顾时间和费用的任务调度方案形式化为一个 n层m 叉树，然后将调度方案的选择问题转化为树的遍历问题，最后利用剪枝方法避免无效路径的搜索，降低了时间复杂度，实现了任务的优化调度．结果表明该算法能按照用户的时限和费用需求偏好选择优化的调度方案，且在性能上优于传统的未剪枝算法．所以该算法是一种可行的任务调度算法． |
| 英文摘要: |
| Grid task scheduling is very complex issue due to the heterogeneity and distributed nature of economic grid environment. To solve independent tasks scheduling under user quality of service economic demand preference, a scenario selection algorithm for task scheduling is proposed. The task scheduling scenarios are formulated as \%n\%-level and \%m\%-ary tree. Then, the scenario selection for task scheduling is translated into a traversal problem of tree. Next, invalid path searching is avoided using pruning method. Finally, a simulative example is also provided to analyze the characteristics of the algorithm. The results show that this algorithm can allocate tasks to appropriate CPU resources based on the user′s requirement of deadline and budget constraint, and it has a low space complexity and a tolerable time complexity, which outperforms the conventional scheduling algorithm. The conclusions indicate that it is a feasible task scheduling algorithm. |
|
查看全文
查看/发表评论 下载PDF阅读器 |
| 关闭 |
|
|
|