In this paper, we make the study of two batch scheduling problems with rejection 1|B≥n, rej|∑ωjTj+ TP and 1|B≥n, rej|∑ωjUj+TP (Here the batch capacity is infinity). We present pseudo-polynomial time algorithms and fully polynomial time approximation scheme (FPTAS) for the problems under consideration, which are the best known exact and approximation algorithms by far.%本文对两个加工可拒绝的无界批量分批排序问题1|B≥n,rej|∑ωjTj+TP和1|B≥n,rej|∑ωj+TP进行了研究,对这两个问题分别给出了伪多项式时间算法和(FPTAS)近似算法.目前为止它们都是比较好的精确算法和近似算法.
展开▼
