有尺寸的单机分批排序问题的近似算法

摘要

本文主要讨论了特定情形下单机分批排序问题1｜B,rj,sj｜Cmax的近似算法。对于大工件(工件的尺寸严格大于机器容量的1/2)的加工时问不小于小工件(工件的尺寸小于或等于机器容量的1/2)的加工时间的特定情形，利用动态规划的方法和拆分的技巧，我们提出了最差性能比为3/2+ε的多项式时间近似算法，此处，ε是任意小的正数。除非，P=NP，在此情形下，不存在最差性能比小于3/2+ε的近似算法。