计算机学报
計算機學報
계산궤학보
CHINESE JOURNAL OF COMPUTERS
2009年
8期
1631-1636
,共6页
多处理机任务调度%规则调度%近似算法%NP-难问题
多處理機任務調度%規則調度%近似算法%NP-難問題
다처리궤임무조도%규칙조도%근사산법%NP-난문제
多处理机任务调度问题P4|fix|Cmax(m≥=)是典型的强NP难问题,由于其在并行环境中的实际意义而受到越来越多的关注.但在一般情形下,寻求该问题的较为理想的近似算法是极其困难的,通常从较少处理机数的系统着手研究.对于m=4的情形,文中研究了P4|fix|Cmax的规则调度算法,通过引入组调度技术,给出了该问题的一个线性时间的4/3-近似算法,并证明了该算法是4-处理机系统中的最优规则调度算法.
多處理機任務調度問題P4|fix|Cmax(m≥=)是典型的彊NP難問題,由于其在併行環境中的實際意義而受到越來越多的關註.但在一般情形下,尋求該問題的較為理想的近似算法是極其睏難的,通常從較少處理機數的繫統著手研究.對于m=4的情形,文中研究瞭P4|fix|Cmax的規則調度算法,通過引入組調度技術,給齣瞭該問題的一箇線性時間的4/3-近似算法,併證明瞭該算法是4-處理機繫統中的最優規則調度算法.
다처리궤임무조도문제P4|fix|Cmax(m≥=)시전형적강NP난문제,유우기재병행배경중적실제의의이수도월래월다적관주.단재일반정형하,심구해문제적교위이상적근사산법시겁기곤난적,통상종교소처리궤수적계통착수연구.대우m=4적정형,문중연구료P4|fix|Cmax적규칙조도산법,통과인입조조도기술,급출료해문제적일개선성시간적4/3-근사산법,병증명료해산법시4-처리궤계통중적최우규칙조도산법.
