计算机研究与发展
計算機研究與髮展
계산궤연구여발전
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
2008年
5期
841-847
,共7页
决策任务%网格计算%启发式%调度%死锁
決策任務%網格計算%啟髮式%調度%死鎖
결책임무%망격계산%계발식%조도%사쇄
网格下的任务调度是一个NP问题.一些迭代算法例如遗传算法可以较有效地解决,但是迭代次数过多时间复杂度高.传统的启发式策略则往往会造成资源空闲时刻过多,反而延误整个程序的完成时间.采用一种"先调度、后优化"的思想,首先采用普通的启发式算法得到调度方案,然后根据得到的甘特图重新生成DAG图,生成决策任务和决策路径,采用启发式算法将决策任务尽可能提前调度到资源的空闲时段提前运行,达到缩短整个任务收敛时间的目的,同时给出任务之间的死锁判定方法.实验证明,新算法优于其他启发式算法.
網格下的任務調度是一箇NP問題.一些迭代算法例如遺傳算法可以較有效地解決,但是迭代次數過多時間複雜度高.傳統的啟髮式策略則往往會造成資源空閒時刻過多,反而延誤整箇程序的完成時間.採用一種"先調度、後優化"的思想,首先採用普通的啟髮式算法得到調度方案,然後根據得到的甘特圖重新生成DAG圖,生成決策任務和決策路徑,採用啟髮式算法將決策任務儘可能提前調度到資源的空閒時段提前運行,達到縮短整箇任務收斂時間的目的,同時給齣任務之間的死鎖判定方法.實驗證明,新算法優于其他啟髮式算法.
망격하적임무조도시일개NP문제.일사질대산법례여유전산법가이교유효지해결,단시질대차수과다시간복잡도고.전통적계발식책략칙왕왕회조성자원공한시각과다,반이연오정개정서적완성시간.채용일충"선조도、후우화"적사상,수선채용보통적계발식산법득도조도방안,연후근거득도적감특도중신생성DAG도,생성결책임무화결책로경,채용계발식산법장결책임무진가능제전조도도자원적공한시단제전운행,체도축단정개임무수렴시간적목적,동시급출임무지간적사쇄판정방법.실험증명,신산법우우기타계발식산법.
