软件学报
軟件學報
연건학보
JOURNAL OF SOFTWARE
2010年
12期
3211-3219
,共9页
多处理机任务调度%近似算法%近似比%NP难问题
多處理機任務調度%近似算法%近似比%NP難問題
다처리궤임무조도%근사산법%근사비%NP난문제
研究独立多处理机任务静态调度问题Pm|fix|Cmax,即在m个处理机系统中调度n个多处理机任务,每个任务指派到所需一组处理机上不可剥夺地执行.该问题应用广泛但早已证明为NP难问题,而且也不存在常数近似算法.分析了问题Pm|fix|Cmax和其中所有任务都是单位处理机时间的特殊情形Pm|fix,p=1|Cmax的调度,并利用实例划分(split scheduling,简称SS)、首次满足优先(first fit,简称FF)和最大宽度优先(large wide first,简称LWF)等方法,构造了问题Pm|fix,p=1|Cmax的√2m+1近似算法和问题Pm|fix|Cmax的2√m近似算法,优于目前已有文献的最好结果.
研究獨立多處理機任務靜態調度問題Pm|fix|Cmax,即在m箇處理機繫統中調度n箇多處理機任務,每箇任務指派到所需一組處理機上不可剝奪地執行.該問題應用廣汎但早已證明為NP難問題,而且也不存在常數近似算法.分析瞭問題Pm|fix|Cmax和其中所有任務都是單位處理機時間的特殊情形Pm|fix,p=1|Cmax的調度,併利用實例劃分(split scheduling,簡稱SS)、首次滿足優先(first fit,簡稱FF)和最大寬度優先(large wide first,簡稱LWF)等方法,構造瞭問題Pm|fix,p=1|Cmax的√2m+1近似算法和問題Pm|fix|Cmax的2√m近似算法,優于目前已有文獻的最好結果.
연구독립다처리궤임무정태조도문제Pm|fix|Cmax,즉재m개처리궤계통중조도n개다처리궤임무,매개임무지파도소수일조처리궤상불가박탈지집행.해문제응용엄범단조이증명위NP난문제,이차야불존재상수근사산법.분석료문제Pm|fix|Cmax화기중소유임무도시단위처리궤시간적특수정형Pm|fix,p=1|Cmax적조도,병이용실례화분(split scheduling,간칭SS)、수차만족우선(first fit,간칭FF)화최대관도우선(large wide first,간칭LWF)등방법,구조료문제Pm|fix,p=1|Cmax적√2m+1근사산법화문제Pm|fix|Cmax적2√m근사산법,우우목전이유문헌적최호결과.
