变长安排问题

Variable length scheduling problem

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

There are p processors to schedule n tasks, each task t at unit time i on processor j having a processing time l(t, i, j). Our goal is to find a scheduling scheme to minimize its completion time, namely, makespan. The problem is inapproximable within a factor nk for any fixed non-positive integer k unless NP=P. When each task t at unit time i on processor j has a processing time l(t, i, j)∈{k_1, k_2}, this paper gives an approximation algorithm for the problem.