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

• 作者: 范静
• 来源期刊: 科学技术与工程
• 学科: 数学
• 关键词: 排序 阈值算法 最坏情况界 机器准备时间 线性时间
• 年，卷（期）: 2008,（7）
• 所属期刊栏目: 论文
• 页码范围: 1649-1654
• 页数: 6页
• 分类号: O223
• 字数: 4960字
• 语种: 中文
• DOI: 10.3969/j.issn.1671-1815.2008.07.002

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	范静	上海第二工业大学理学院	16	15	2.0	3.0