计算机研究与发展
計算機研究與髮展
계산궤연구여발전
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
2005年
3期
507-513
,共7页
调度问题%组合优化%NP%NP完全%多项式时间归约%NP难
調度問題%組閤優化%NP%NP完全%多項式時間歸約%NP難
조도문제%조합우화%NP%NP완전%다항식시간귀약%NP난
提出了具有不同中断时间代价的抢先调度问题(P|ptmn(δi)| Cmax).该问题在工程任务分配、分布式计算和网络通信等实际问题中有着广泛的应用背景.首先证明了这个问题是一个NP难优化问题.并给出了一个时间复杂度为O(nlogn)的近似算法,其近似度为5/3.算法的特点是结合中断时间δi来应用LPT思想,而不只是把它应用到任务i的执行时间pi上,从而避免了LPT算法在最坏情形下的近似度差的问题.在算法的关键部分,运用了均分的技巧来提高任务执行的并行性,进一步提高了近似度.
提齣瞭具有不同中斷時間代價的搶先調度問題(P|ptmn(δi)| Cmax).該問題在工程任務分配、分佈式計算和網絡通信等實際問題中有著廣汎的應用揹景.首先證明瞭這箇問題是一箇NP難優化問題.併給齣瞭一箇時間複雜度為O(nlogn)的近似算法,其近似度為5/3.算法的特點是結閤中斷時間δi來應用LPT思想,而不隻是把它應用到任務i的執行時間pi上,從而避免瞭LPT算法在最壞情形下的近似度差的問題.在算法的關鍵部分,運用瞭均分的技巧來提高任務執行的併行性,進一步提高瞭近似度.
제출료구유불동중단시간대개적창선조도문제(P|ptmn(δi)| Cmax).해문제재공정임무분배、분포식계산화망락통신등실제문제중유착엄범적응용배경.수선증명료저개문제시일개NP난우화문제.병급출료일개시간복잡도위O(nlogn)적근사산법,기근사도위5/3.산법적특점시결합중단시간δi래응용LPT사상,이불지시파타응용도임무i적집행시간pi상,종이피면료LPT산법재최배정형하적근사도차적문제.재산법적관건부분,운용료균분적기교래제고임무집행적병행성,진일보제고료근사도.
