机器带准备时间的平行机排序问题的并行阈值算法

Compound-threshold Algorithm for Scheduling on Parallel Machines with Non-simultaneous Machine Available Times

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

For maximizing the minimum machine completion time on parallel machines with non-simultaneous machine available times, the compound-threshold algorithm has been researched, associated with primary-threshold algorithm and dual-threshold algorithm. And the two phase compound-threshold algorithm for three machines has the worst-case ratio 3/4 when ε = 1/4, which is the best result. Moreover, according to the numerial examples, high efficiency of the compound-threshold is showed under some large scale, with 3 to 500 machines and 5 to 50 000 jobs.