排序问题是一类重要的组合最优化问题,也是运筹学研究的一个非常活跃的分支,具有较强的应用背景。机器具有学习效应的排序是一种新兴起的现代排序模型,因其更接近于现实生产,具有很好的研究价值。本文就以此模型为基础,研究了两类带学习效应的排序问题。对于论文的主要结构安排如下：第一章首先介绍了排序问题应用背景以及问题的描述,给出了必要的预备知识,然后简要介绍了本文的主要结果和创新点。第二章主要讨论了机器具有学习效应的条件下,目标函数为加权总完工时间、最大延迟时间、最大延误时间和误工工件个数的单机排序问题。文中对极小化加权总完工时间的单机排序问题给出了多项式时间算法,并证明了算法的最优性。在工件的加工时间与交货期一致的条件下,对于极小化最大延迟、极小化最大延误时间和极小化误工工件个数的单机排序问题,分别给出了最优算法并证明了算法的最优性。第三章主要研究了在机器具有学习效应的条件下,目标函数为最大完工时间、总完工时间、加权总完工时间和最大延迟时间的单机成组排序问题。文中对前三个问题分别给出了多项式时间算法,并证明了算法的最优性。对于目标函数为最大延迟时间的问题,在工件的加工时间与交货期一致的条件下,给出了该问题的最优算法,并证明了算法的最优性。