带机器准备时间的同类机在线与半在线排序问题

• 作者: 丁际环 岳丽 张伟 张玉忠 曲桂东
• 来源期刊: 曲阜师范大学学报(自然科学版)
• 学科: 数学
• 关键词: 在线排序 近似算法 最坏情况
• 年，卷（期）: 2003,（3）
• 页码范围: 1-5
• 页数: 5页
• 分类号: O223
• 字数: 4420字
• 语种: 中文
• DOI: 10.3969/j.issn.1001-5337.2003.03.001

摘要

研究带机器准备时间的m台同类机(uniform machines)在线和半在线排序问题,目标函数为极小化最大机器(工件)完工时间. 对于在线情形,证明了LS算法的最坏情况为ρ=(1+5)/2, m=2,1+2m-2/2, m≥3, 并且当m=2时,LS算法是最好的近似算法;当m=2,3,...,6时界是紧的,特别地,当s1=s2=...=sm-1,sm≥1时,证明了LS算法的最坏情况界为ρ=(1+5)/2, m=2,3-4/(m+1), m≥3, 而且界是紧的;对于已知加工时间递减的半在线排序问题,证明了LS算法的最坏情况界为2-2/(m+1).

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张玉忠	曲阜师范大学运筹与管理学院	115	657	14.0	21.0
2	丁际环	曲阜师范大学运筹与管理学院	5	27	2.0	5.0
3	曲桂东	威海职业学院信息工程系	8	23	3.0	4.0
4	张伟	青岛师范学院数学系	1	6	1.0	1.0
5	岳丽	曲阜师范大学运筹与管理学院	1	6	1.0	1.0