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

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