工件有到达时间的平行机分批排序问题的一个PTAS算法

摘要

The problem of scheduling jobs with release dates on parallel unbounded batch processing machines to minimize total weighted completion time is considered. By adopting several techniques such as input transformation, job division and dynamic programming, a polynomial time approximation scheme is developed for this problem.%研究工件有到达时间的最小化加权完工时间和的平行机分批排序问题,通过综合运用实例转换,工件分类和动态规划等方法提出了一个多项式时间近似框架.