论文部分内容阅读
针对带准备时间的最小机器完工时间最大化排序问题,结合原始阈值算法、对偶阈值算法并加以修正,提出并行层次阈值算法,证明了三台机器情况下当参数ε=1/4时,此线性时间算法的最坏情况界为3/4。这是到目前为止最坏情况界最小且时间复杂性为线性时间的算法。进一步通过计算实验,表明并行阈值算法对于3台至50台机器、5至50000个工件数量的规模下,具备很高效率。