加工时间和尺寸成正比单机排序和工件运输的最小化最大完工时间问题

• 作者: 原晋江 录岭法 陈友军
• 来源期刊: 运筹学学报
• 学科: 数学
• 关键词: 运筹学 排序 启发式算法 最差执行比 渐进的PTAS
• 年，卷（期）: 2007,（1）
• 页码范围: 16-22
• 页数: 7页
• 分类号: O22
• 语种: 中文
• DOI: 10.3969/j.issn.1007-6093.2007.01.002

摘要

在单机排序和工件运输的最小化最大完工时间问题中,工件首先在一台机器上加工,然后被一辆有容量限制的汽车运送到一个顾客.当工件的加工时间和尺寸无关时,Chang和Lee[4]已经证明该问题是强NP困难的.他们也给出了一个启发式算法,它的最差执行比为5/3,并且这个界是紧的.本文考虑工件的加工时间和尺寸成正比的情形,证明了Chang和Lee的算法有更好的最差执行比53/35,并提供了一个新的启发式算法,它的最差执行比是3/2,并且这个界是最好的.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	原晋江	郑州大学数学系	26	97	6.0	7.0
2	录岭法	郑州大学数学系	3	6	2.0	2.0
3	陈友军	郑州大学数学系	1	4	1.0	1.0