摘要
针对带准备时间的最小机器完工时间最大化排序问题,结合原始阈值算法、对偶阈值算法并加以修正,提出并行层次阈值算法,证明了三台机器情况下当参数ε=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.
出处
《科学技术与工程》
2008年第7期1649-1654,共6页
Science Technology and Engineering
基金
上海高校选拔培养优秀青年教师科研专项基金项目(LX306002)
上海市教委研创新(08ZY78,07ZZ178)
国家自然科学基金(70731160015,10371071)资助
关键词
排序
阈值算法
最坏情况界
机器准备时间
线性时间
schuling threshold algorithm worst-case ratio machine available times linear times