解决矩阵链相乘处理器调度问题的一种新算法  

A New Algorithm to Solve the MCSP

作　　者：徐卫志[1] 王洪国[1] 于惠[1] 杨海[1] 

机构地区：[1]山东师范大学信息科学与工程学院,济南250014

出　　处：《计算机科学》2008年第4期197-199,共3页Computer Science

基　　金：山东省自然科学基金(Q2006G03)

摘　　要：本文介绍了矩阵链相乘处理器分配问题和离散处理器分配算法,描述了Lee Heejo等人提出的解决MCSP的处理器分配算法,提出了一种解决MCSP的时间复杂度更低的算法,使处理器能尽量被充分利用,并对三种分配算法进行了比较分析。In this paper, the matrix chain scheduling problem and two discrete processor allocation algorithms are introduced. Then the algorithm which was proposed by Lee Heejo is described. At last, a new greedy algorithm is proposed,which costs less time and rnake good use of the processors, and three allocation algorithms are compared and analysed.

关 键 词：矩阵链相乘 处理器分配 贪心算法 

分 类 号：O224[理学—运筹学与控制论] TN929.533[理学—数学]