单台机以总完工时间为目标的批排序问题

摘要：

研究单台机,工件加工时间相等,大小不同的批排序问题,给出了一个最坏情况界为9+√3/6≈1.7817的多项式时间近似算法,并证明了即使工件总大小不超过2,该问题也不存在FPTAS,除非P=NP.

关键词：组合优化、批排序问题、多项式时间近似算法、计算复杂性

所属期刊栏目：32

分类号：O223(运筹学)

在线出版日期：2017-12-21（万方平台首次上网日期，不代表论文的发表时间）

页数：共11页

页码：462-472