使两台和三台平行机的最小完工时间为最大的线性算法

• 作者: 张峰 范静
• 来源期刊: 上海第二工业大学学报
• 学科: 数学
• 关键词: 排序 最坏情况界 线性算法
• 年，卷（期）: 2006,（2）
• 页码范围: 84-91
• 页数: 8页
• 分类号: O223
• 字数: 6627字
• 语种: 中文
• DOI: 10.3969/j.issn.1001-4543.2006.02.001

摘要

讨论使两台和三台平行机的最小完工时间为最大的线性算法--对偶阈值算法DAm(ε),其中ε是参数.对于问题P2‖Cmin,证明对偶阈值算法DA2(1/7)的最坏情况界为6/7,并证明此界为紧界;对于问题P3‖Cmin,进而提出层次对偶阈值算法TDA3(ε),并证明当ε取2/11时,算法的最坏情况界为9/11.这些都是线性时间算法中使最坏情况界值为最小的算法.

作者信息

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