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

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

作　　者：范静[1] 

机构地区：[1]上海第二工业大学理学院

出　　处：《科学技术与工程》2008年第7期1649-1654,共6页Science Technology and Engineering

基　　金：上海高校选拔培养优秀青年教师科研专项基金项目(LX306002);上海市教委研创新(08ZY78,07ZZ178);国家自然科学基金(70731160015,10371071)资助

摘　　要：针对带准备时间的最小机器完工时间最大化排序问题,结合原始阈值算法、对偶阈值算法并加以修正,提出并行层次阈值算法,证明了三台机器情况下当参数ε=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.

关 键 词：排序 阈值算法 最坏情况界 机器准备时间 线性时间 

分 类 号：O223[理学—运筹学与控制论]