1|B,rj∈{0,r}|∑Cj问题的复杂性及近似算法

• 作者: 丁际环 刘丽丽 姜宝山 张玉忠
• 来源期刊: 曲阜师范大学学报（自然科学版）
• 学科: 数学
• 关键词: 分批排序 动态规划 NP-完备 性能指标
• 年，卷（期）: 2000,（4）
• 页码范围: 19-21
• 页数: 3页
• 分类号: O223
• 字数: 2973字
• 语种: 中文
• DOI: 10.3969/j.issn.1001-5337.2000.04.006

摘要

讨论了分批排序中工件有两个到达时间,以工件完工时间总和为目标函数的批处理问题 ,证明了其NP-完备性,并以Brucker等[1]给出的动态规划算法为基础,给出了一性能指标为2的多项式时间近似算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张玉忠	曲阜师范大学运筹学研究所	115	657	14.0	21.0
2	丁际环	曲阜师范大学运筹学研究所	5	27	2.0	5.0
3	刘丽丽	曲阜师范大学运筹学研究所	4	22	1.0	4.0