摘要
研究多处理机任务调度模型Pm|fix,pj=1|Cmax,即在m个处理机系统中调度n个时间长度都为1的多处理机任务,每个任务指派到所需一组处理机上不可剥夺地执行。这类问题在网络并行计算、多播系统及工程规划等领域都有广泛的应用,但早已被证明为NP难问题,而且也不存在常数近似算法。基于团划分方法构造了该问题的多项式时间近似算法,通过模拟实验进行了验证,和最大宽度优先(LWF)算法相比,该算法花费时间较长,近似比性能要好。
This paper studies the problem of scheduling model Pm ｜fix,pj =1｜Cmax,that schedules a set of n independent multipro-cessor jobs with unit process time and prespecified processor allocation on a set of identical processors in order to minimize the makespan.The general problem Pm ｜fix｜Cmax,that has widely been used in various fields such as the network parallel computing,the multi-casting system and the project plan,is proved to be NP-hard and cannot be approximated within a constant factor unless P=NP.This paper proposes an approximation algorithm for this problem based on the approximation clique partition method.By the analysis from test data,this algorithm presents more optional ratio preference.
出处
《计算机工程与应用》
CSCD
北大核心
2009年第4期4-8,共5页
Computer Engineering and Applications
基金
国家自然科学基金No.60872039
湖南省自然科学基金No.06JJ50105~~
关键词
多处理机任务
调度
近似算法
NP难问题
团划分
multiprocessor job
scheduling
approximation algorithm
NP-hard problem
clique partition
