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

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

两台同类机排序问题SPT算法的最坏情况比

本文研究以工件总完工时间为目标函数的两台同类机排序问题, 给出了SPT算法以两台机器速度比为参数的最坏情况比, 使该算法的常数最坏情况比上界与下界的差距由0.430 5减小到0.014 7。     

两台同类机排序问题SPT算法的最坏情况比

本文研究以工件总完工时间为目标函数的两台同类机排序问题, 给出了SPT算法以两台机器速度比为参数的最坏情况比, 使该算法的常数最坏情况比上界与下界的差距由0.430 5减小到0.014 7。