本文主要讨论了带恶化效应和学习效应的单机排序和单机成组排序问题。对于这两个问题分别给出了两个模型,并对这些模型给出了相应的多项式算法。第二章的第一、二节分别研究单机排序模型1│pi,[r]=(pi=α(t))rβ│f(C)和1│pr[r]=(pirβ+α(t))│f(C),对目标函数分别为时间表长、总完工时间以及总完工时间平方和,证明了多项式可解性；对目标函数为极小化最大延误,在满足p(?)≤pk当且仅当d(?)≤dk(i=1,2..n)的情况下,同样证明了多项式可解性。第三章的第一、二节分别对单机成组排序问题的两个模型进行了研究。对于模型1|(?)和模型1│pi,j[r]=αi,j(a+bt)rβi,si=δi(a+bt),GT│f(C),当目标函数分别为时间表长和总完工时间时,我们给出了多项式算法；当目标函数为加权总完工时间,在且满足α(?)≥α(?)当且仅当wi,u≤wi,v(i=1,2..m)时,我们也给出了多项式算法。