运筹与管理2013，Vol.22Issue(1)：77-82,6.
有尺寸的同型机分批排序问题的近似算法
Scheduling Jobs with Non-identical Sizes on Parallel Batch Prosessors
摘要
Abstract
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 + ε.关键词
组合最优化/分批排序/近似算法/动态规划/最差性能比Key words
combinatorial optimization/ parallel batch prosessors/ algorithm / dynamic programming/ worst-case ratio分类
数理科学引用本文复制引用
吴翠连,陈俊..有尺寸的同型机分批排序问题的近似算法[J].运筹与管理,2013,22(1):77-82,6.基金项目
国家自然科学基金资助项目资助(11071142) （11071142）
