| 基于相对效费比的网格工作流调度算法 |
| |
| 引用本文： | 龙浩,梁毅,邸瑞华.基于相对效费比的网格工作流调度算法[J].计算机集成制造系统,2010,16(3). |
| |
| 作者姓名： | 龙浩 梁毅 邸瑞华 |
| |
| 作者单位： | 1. 北京工业大学,计算机学院,北京,100124;江西师范大学,软件学院,江西,南昌,330022
2. 北京工业大学,计算机学院,北京,100124 |
| |
| 基金项目： | 国家自然科学基金资助项目(60703020);;北京市教委基金资助项目(JJ007011200901);;北京工业大学211基金资助项目(007000548108)~~ |
| |
| 摘 要： | 为解决计算网格中有向无环图表示的截止期约束下的工作流时间费用优化问题,提出了一个新的启发式优化算法——相对效费比算法。该算法首先根据调度系数得到初步方案,再逐步调整,当方案完工时间小于截止期时,用时间换成本,选择成本消减最快的节点进行调整,中选服务有最大的正相对效费比值;当方案完工时间超过截止期时,用成本换时间,调整成本增加最慢服务的节点,中选服务有最大的负相对效费比值,该方法在保证截止期约束的同时能有效降低总成本。通过大量模拟实验和与最小关键路径、正向分层费用优化算法、逆向分层费用优化算法的比较,证明了相对效费比的有效性。
|
| 关 键 词： | 网格 工作流 有向无环图 启发式算法 相对效费比 |
Relative time-cost rate based heuristic for workflow scheduling in grids |
| |
| LONG Hao,LIANG Yi,DI Rui-hua.Relative time-cost rate based heuristic for workflow scheduling in grids[J].Computer Integrated Manufacturing Systems,2010,16(3). |
| |
| Authors: | LONG Hao LIANG Yi DI Rui-hua |
| |
| Affiliation: | 1.School of Computer Science/a>;Beijing University of Technology/a>;Beijing 100124/a>;China/a>;2.School of Software/a>;Jiangxi Normal University/a>;Nanchang/a>;330022/a>;China |
| |
| Abstract: | In order to solve the workflow time-cost optimization problem under deadline restrictions represented by directed acyclic graph(DAG) in computation grids,a novel heuristics algorithm called relative time-cost rate(RTCR)was proposed.Firstly the preliminary program was obtained by scheduling coefficient,then the scheduling was optimized gradually:when the deadline exceeded,the node with the slowest cost-decreased service was rescheduled,the selected service had the maximum positive RTCR value,otherwise the no... |
| |
| Keywords: | grid workflow directed acrylic graph heuristics relative time-cost rate |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
