摘要： 研究任务有多种处理方式的多处理器任务调度问题(MTS)的求解算法,给出求解这种问题的二阶段方法:第1阶段为指派问题,第二阶段为调度问题Pm|fix j|Cmax,从而得到一个新的求解Pm|set j|Cmax近似算法的方法,并针对P4|setj|Cmax给出了具体算法,证明这种近似算法是一个2-逼近度算法,是文献[4]中在4-处理器问题上的推广。
关键词:
MTS问题,
调度算法,
近似算法
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 paper[4].
中图分类号:
肖建华;. 多处理器任务调度问题的新近似算法[J]. , 2005, 31(24): 60-.
XIAO Jianhua. New Approximation Algorithm for Multiprocessors Scheduling Problem[J]. , 2005, 31(24): 60-.