作为一类重要的组合优化问题,排序问题得到了越来越广泛的关注与研究,并且得到了重要的成果与应用。单机排序问题是最简单的一类排序问题,同时也是最重要的排序问题之一。单机排序问题大量存在于现实生活中,有着广泛的实际背景,而且比较容易求解,能够为更复杂的排序问题提供指导。 在经典的排序问题中,通常的基本假设是工件的加工时间为常数,但是在某些实际问题中,工件的加工时间不是常数,而是随着时间的推移而增加或者减少。一方面,工件的加工时间随着机器的熟练程度的提高等原因而逐渐减少,从而产生了所谓的“学习效应”。另一方面,工件的加工时间文会随着机器的磨损等原因而逐渐增加,从而产生了所谓的“退化效应”。同时具有学习效应和退化效应的情形可以在现实生活生产中大量发现。最近,关于学习效应和退化效应的排序问题得到了广泛而深入的学习。本文主要学习单机排序中的学习效应和退化效应的几个问题。 本文提出了两种不同的同时具有学习效应和退化效应的实际加工时间模型。一个是无基本加工时间模型,学习效应通过一个与工件的加工位置有关的函数反映,退化效应是工件的开工时间的线性函数。另外一个是基本加工时间与退化因子成比例模型,其中假设退化因子与基本加工时间成正比,即基本加工时间越长则退化因子越大。学习效应也是通过一个与工件的加工位置有关的函数反映,退化效应也是工件的开工时间的线性函数。基于这两个模型,我们解决了单机排序中的极小化最大完工时间、极小化总完工时间、极小化加权总完工时间和极小化最大延迟等问题。极小化最大完工时间、极小化总完工时间问题可以通过最小退化因子优先法则（SDR rule）得到最优排序。在一定条件下,极小化加权总完工时间问题可以通过加权最小退化因子优先法则（WSDR rule）得到最优排序,极小化最大延迟问题可以通过最早工期优先法则（EDD rule）得到最优排序。