排序问题是一类重要的组合优化问题.在经典排序模型中通常假设工件的加工时间为常数.但在许多实际问题中,工件的加工时间可能与其开工时间、所用资源或所处的位置有着某种联系。由此产生一类现代排序问题:具有学习与退化效应的排序问题.例如,产业工人由于连续重复做相似的工作,效率会越来越高,这种现象在文献中称之为“学习效应”;由于机器的老化,会使机器的运行速度慢下来,工件的实际加工时间会变长,这种现象在文献中称之为“退化现象”(Pinedo,2002[31]).　　本文研究了具有学习效应与退化现象的排序问题,主要结果如下:　　1.具有学习与退化效应的单机排序问题,(a)对于问题1|Pj[r]=pjα(t)ra|Cmax,证明了工件按pj非减顺序排列可以得到最优排序(即SPT序).(b)对于问题(?),证明当pi≤pj有wj≤wi时,工件按(?)非减的顺序排列可以得到最优序.(c)对于问题1|Pj[r]=pjα(t)ra|Lmax,证明当di≤dj有pi≤pj时,工件按dj非减顺序排列可以得到最优排序.其中退化因子α(t)≥0为t的非减凸函数,r表示工件在序列中所处的位置,a表示学习因子.　　2.具有学习与退化效应的资源限制排序问题对于问题1|pj[r]=(pj+βt)ra,rj=f(uj),Cmax≤C|(?)和1|Pj[r]=(pj+βt)ra,rj=f(uj),(?)≤U|Cmax,分别给出了最优算法,并证明了算法的正确性.其中uj是分配工件Jj的资源量,f是正值严格递减的函数.U是连续可分配的资源总数,C满足(?)的常数.　　3.具有学习效应的排序问题(a)对于问题(?)给出了最优算法;对于问题(?)在某些特殊情形下给出最优算法.(b)对于排序模型证明了SPT规则能够得到最优序.其中ord表示工件满足下列条件:对任一工件j有aj≤bj,且对于两个工件j,k,若aj≤ak,则有bj≤bk.这里的aj,bj表示工件j的分别在第一台机器和第二台机器上的基本加工时间; prp表示工件满足:bj=caj(这里c≥1是一个常数).