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

发布时间：2018-06-22 08:59

  本文选题：组合优化 + 批排序问题　； 参考：《高校应用数学学报A辑》2017年04期

【摘要】：研究单台机,工件加工时间相等,大小不同的批排序问题,给出了一个最坏情况界为9+3~(1/2)/6≈1.7817的多项式时间近似算法,并证明了即使工件总大小不超过2,该问题也不存在FPTAS,除非P=NP.
[Abstract]:In this paper, we study the batch scheduling problem of a single machine with equal workpiece processing time and different size. A polynomial time approximation algorithm with a worst-case bound of 9.3 ~ (1 / 2) / 6 鈮，

本文编号：2052313