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

作者：曹移林; 余炜^*

来源：华东理工大学学报, 2019, 45(06): 989-994.

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)的算法。

• 单位
  华东理工大学