最小基数箱子覆盖问题及其启发式算法

研究了一个新颖的装箱问题,即最小基数箱子覆盖问题(MinimumCardinalityBinCoveringProblem),证明了该问题是强NP-完备的;在物件大小满足一定的条件下,给出了一个时间复杂度为O(n)的启发式算.

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

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