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

摘要

对工件有不同到达时间、不同加工时间和尺寸的同型机分批排序问题寻找近似算法.对于大工件(工件的体积严格大于机器容量的÷)的加工时间不小于小工件(工件的体积小于或等于机器容量的÷)的加工时间的特定情形,利用动态规划的方法和拆分的技巧,我们设计了近似算法并分析了其最差性能比.%We study the problem Pm | B,rj,sj | Cmax for the version where the processing times of large jobs(with sizes greater than half the capacity of machine) are not less than those of small jobs (with sizes not greater than half the capacity of machine).The methods applied in this paper are scaling-and-rounding and dynamic programming.An algorithm is proposed with worst-case ratio 3/2 + ε.