执行时间可变的任务在多处理机上的排序问题

The sequencing problem for variable length tasks in multiprocessors

研究一类有实际价值的网页下载问题,把其抽象成一类有n项独立任务在m台不同处理机上执行的排序问题,这里,每项任务在不同处理机上可以有不同起始时间和不同的执行时间.文章指出该问题是强NP-完备的,该问题在特殊情形下能够转化为图论中的最大匹配问题,从而给出了在此情形下的一个完全解决方案.

The author studies the problem involved in information gathering which has its value in real life,and this problem is theoretically treated as sequencing n independent tasks in m unrelated multiprocessors,where each task might have its different release time and variable processing time (lengths) on any different unrelated processor at per starting time unit.This problem is proved to be NPhard in a strong sense.In addition,this problem can be transmitted to the maximum matching problem in some special case,and then it is solvable in polynomial time.