分批排序问题1|B,rj,sj| Lmax的近似算法

• 作者: 吴翠连 陈俊
• 来源期刊: 曲阜师范大学学报（自然科学版）
• 学科: 数学
• 关键词: 分批排序 最大延误时间 最差性能比 近似算法
• 年，卷（期）: 2012,（2）
• 所属期刊栏目: 运筹与控制
• 页码范围: 54-57
• 分类号: O22
• 字数: 4153字
• 语种: 中文
• DOI: 10.3969/j.issn.1001-5337.2012.02.011

摘要

主要讨论了工件有到达时间、加工时间和尺寸的目标函数是极小化最大延误时间的单机分批排序问题1|B,rj,sj|Lmax.在机器容量B为常数时,即使在B=2和工件的到达时间与尺寸都相同时,问题也是强NP-难的.基于问题1|B,rj|Lmax目前最好的多项式时间近似算法-PTAS算法(从算法的最差性能比来说是最好的),我们采用任意工件可以按尺寸拆分的技巧,针对问题1|B,rj,sj| Lmax设计了一个多项式时间的近似算法,并分析出这个算法的最差性能比为2+ε(其中ε是任意小的正数).

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈俊	泰山职业技术学院信息工程系	7	118	3.0	7.0
2	吴翠连	曲阜师范大学管理学院	3	1	1.0	1.0