排序是一类重要的组合最优化问题,是运筹学中的一个重要分支。它产生的背景主要是机器制造,后来被广泛应用于计算机系统、运输调度、生产管理和工程技术等许多领域,是目前运筹学研究的一个非常活跃的分支,有广阔的应用前景。机器具有学习效应的分批排序问题是近几年来新兴起的一种现代排序模型,因其更接近于现实生产,因此具有很高的研究价值,本文就以上模型为基础,研究了几种特殊的分批排序问题,并给出了问题的最优算法,分析了它们的计算复杂性,对于论文的结构我们做了如下安排:第一章首先介绍了排序问题应用背景,然后给出了必要的预备知识,分析了本文所研究问题的现状。最后简要介绍了本文研究的主要结果和创新点。第二章主要讨论了机器具有学习效应,目标函数为加权总完工时间的平行机分批排序问题。主要分析了机器环境为同型机和同类机的情形。此问题的一般情形已被证明是NP-困难的。本章在工件加工时间都相等的这一特殊条件下,给出了最优算法,并分析了算法的计算复杂性。第三章主要研究了机器具有学习效应,目标函数为超前有奖延误受罚的平行机排序问题,这个问题的一般情形也是NP-困难的。本章分析了它的几种特殊情况,给出了这几种情况的最优算法,并分析其计算复杂性。