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