论文部分内容阅读
假设有p台计算机，n张载有信息的网页，其各网页的长度都与计算机和时间有关，现在的问题是，求一个安排．使这p台计算机能在最短的时间内下载完这n张网页．对于任意的一个非负整数k，该问题没有n^k-近似算法，除非NP=P．当任务t在时刻i在处理机j上被开始执行时的加工时间l(t，tj)∈{k1，k2}，我们给出了该问题的一个近似算法．