具有可变时间的并行排序问题

Variable length scheduling problem withtwo lengths in multiprocessor environment

设有p台处理机要加工n项任务,当每项任务t在时刻i和处理机j上被开始执行时,都有一个不可间断的加工时间l(t,i,j)∈{k1,k2},我们的目标是要找一个可行方案σ,使得总的完工时间最短.该问题是NP-完备的.本文给出该问题的一个近似算法.

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)∈{k_1,k_2}.Our goal is to find a scheduling scheme to minimize its completion time,namely,makespan.The problem is NP-complete.It is given an approximation algorithm for the problem.