平行三阶段流水作业问题的近似算法

• 作者: 余炜 曹移林
• 来源期刊: 华东理工大学学报（自然科学版）
• 学科: 数学
• 关键词: 流水作业 排序 近似算法
• 年，卷（期）: 2019,（6）
• 所属期刊栏目: 数学
• 页码范围: 989-994
• 页数: 6页
• 分类号: O223
• 字数: 4486字
• 语种: 中文
• DOI: 10.14135/j.cnki.1006-3080.20180206001

摘要

研究了n个三阶段工件在m个流水车间进行加工的排序问题,目标为最小化最大完工时间.当m是定值时,该问题是NP困难;当m>2时,问题是强NP困难.将问题分解成3种情形,情形1给出了(7/3?1/3m)的近似比;情形2给出了一个3的近似比;情形3给出了近似比为(23/6?1/3m).结合3种情形,最终给出了性能比为(23/6?1/3m)的算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	余炜	华东理工大学数学系	2	0	0.0	0.0
2	曹移林	华东理工大学数学系	1	0	0.0	0.0