分批排序是兴起于20世纪90年代初应用背景极强的一类组合最优化问题，它主要产生于大规模的现代化生产流水作业线。工件加工可拒绝的排序问题是近年来出现的一类新型排序问题，该问题更符合实际情况，具有重要的现实意义。本文将分批排序与可拒绝排序相结合，讨论了一些可拒绝分批排序问题，论文主要结构安排如下：　　第一章是本文的绪论部分，主要介绍了排序问题的背景、相关概念以及所需的基本知识，然后介绍了本文的主要结果和创新点。　　第二章中首次研究了目标函数为极小化总加权完工时间加上被拒绝工件的拒绝费用之和的单机可拒绝分批排序问题。证明了该问题是NP-难的，然后给出了基于动态规划的伪多项式时间算法和FPTAS。　　第三章中首次研究了两类特殊情况下的可拒绝分批排序问题。一个是极小化加权总完工时的有界批量可拒绝分批排序问题，考虑了该问题的一些特殊情况，如所有工件加工时间都相等、工件有两种到达时间；另一个是极小化最大延迟的无界批量可拒绝分批排序问题，考虑了所有工件的拒绝费用都相等的情况。分别给出了以上两类问题基于动态规划的多项式时间算法。