云南民族大学学报（自然科学版）
雲南民族大學學報（自然科學版）
운남민족대학학보（자연과학판）
JOURNAL OF YUNNAN UNIVERSITY OF THE NATIONALITIES（NATURAL SCIENCES EDITION）
2004年
3期
172-176
,共5页
工序安排%不可近似性%近似算法
工序安排%不可近似性%近似算法
공서안배%불가근사성%근사산법
假设有p台计算机,n张载有信息的网页,其各网页的长度都与计算机和时间有关,现在的问题是,求一个安排,使这p台计算机能在最短的时间内下载完这n张网页.对于任意的一个非负整数k,该问题没有nk-近似算法,除非NP=P.当任务t在时刻i在处理机j上被开始执行时的加工时间l(t ,i, j)∈{k1, k2}, 我们给出了该问题的一个近似算法.
假設有p檯計算機,n張載有信息的網頁,其各網頁的長度都與計算機和時間有關,現在的問題是,求一箇安排,使這p檯計算機能在最短的時間內下載完這n張網頁.對于任意的一箇非負整數k,該問題沒有nk-近似算法,除非NP=P.噹任務t在時刻i在處理機j上被開始執行時的加工時間l(t ,i, j)∈{k1, k2}, 我們給齣瞭該問題的一箇近似算法.
가설유p태계산궤,n장재유신식적망혈,기각망혈적장도도여계산궤화시간유관,현재적문제시,구일개안배,사저p태계산궤능재최단적시간내하재완저n장망혈.대우임의적일개비부정수k,해문제몰유nk-근사산법,제비NP=P.당임무t재시각i재처리궤j상피개시집행시적가공시간l(t ,i, j)∈{k1, k2}, 아문급출료해문제적일개근사산법.
