多处理器任务调度问题的新近似算法  

New Approximation Algorithm for Multiprocessors Scheduling Problem

作　　者：肖建华[1] 

机构地区：[1]湖南工程学院计算机科学与技术系,湘潭411101

出　　处：《计算机工程》2005年第24期50-52,60,共4页Computer Engineering

基　　金：国家自然科学基金资助项目(69928201)

摘　　要：研究任务有多种处理方式的多处理器任务调度问题(MTS)的求解算法,给出求解这种问题的二阶段方法:第1阶段为指派问题,第二阶段为调度问题Pm|fix j|Cmax,从而得到一个新的求解Pm|set j|Cmax近似算法的方法,并针对P4|setj|Cmax给出了具体算法,证明这种近似算法是一个2-逼近度算法,是文献[4]中在4-处理器问题上的推广。This paper studies the approximation algorithm for multiprocessor tasks scheduling（MTS） problem. It provides a two-phase method for solving MTS problem： Phase Ⅰ is assignment problem, Phase Ⅱ is the Pm｜fixj｜Cmax scheduling problem. By this two-phase method, it presents 2-approximation algorithm for Pm｜setj｜Cmax scheduling problem. The running time of this algorithm is O（nT0^3 ）, it is better than that of the algorithm in paper.

关 键 词：MTS问题 调度算法 近似算法 

分 类 号：TP399[自动化与计算机技术—计算机应用技术]