| 多处理器任务调度问题的新近似算法 |
| |
| 引用本文： | 肖建华.多处理器任务调度问题的新近似算法[J].计算机工程,2005,31(24):50-52,60. |
| |
| 作者姓名： | 肖建华 |
| |
| 作者单位： | 湖南工程学院计算机科学与技术系,湘潭,411101 |
| |
| 基金项目： | 国家自然科学基金资助项目（69928201） |
| |
| 摘 要： | 研究任务有多种处理方式的多处理器任务调度问题（MTS）的求解算法，给出求解这种问题的二阶段方法：第1阶段为指派问题，第二阶段调度问题Pm｜fixj｜Cmax，从而得到一个新的求解Pm｜setj｜Cmax。近似算法的方法，并针对P4｜fixj｜Cmax给出了具体算法，证明这种近似算法是一个2-逼近度算法，是文献中在4-处理器问题上的推广。
|
| 关 键 词： | MTS问题 调度算法 近似算法 |
| 文章编号： | 1000-3428（2005）24-0050-03 |
| 收稿时间： | 2005-09-12 |
| 修稿时间： | 2005-09-12 |
New Approximation Algorithm for Multiprocessors Scheduling Problem |
| |
| XIAO Jianhua.New Approximation Algorithm for Multiprocessors Scheduling Problem[J].Computer Engineering,2005,31(24):50-52,60. |
| |
| Authors: | XIAO Jianhua |
| |
| Affiliation: | Department of Computer Science and Engineering, Hunan Institute of Engineering, Xiangtan 411101 |
| |
| Abstract: | This paper studies the approximation algorithm for multiprocessor tasks scheduling(MTS) problem.It provides a two-phase method for solving MTS problem: Phase I is assignment problem,Phase II is the Pm| fix j | Cmax scheduling problem.By this two-phase method,it presents2-approximation algorithm for Pm| set j | Cmax scheduling problem.The running time of this algorithm is O(nT 03),it is better than that of the algorithm in paper4]. |
| |
| Keywords: | MTS problem Scheduling algorithm Approximation algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
