由于排序论在运筹学中的重要性,排序问题从不同的角度引起了越来越多学者的关注.为了让排序问题和现实生活更紧密地联系起来,多代理排序、多指标排序以及工件具有约束限制等一系列排序模型被学者们广泛研究.在排序论的研究中,研究者们一般用“工件”表示任务或者订单,用“机器”表示可利用的资源.在本学位论文中,我们主要研究了工件具有加工位置上限及完工截止期的单机排序问题.其中,工件Jj具有加工位置上限kj是指工件Jj必须在前kj个位置上进行加工,而工件Jj具有完工截止期dj是指工件Jj的完工时间不能晚于时刻dj.第一章介绍了排序论的背景知识以及相关的记号和术语,并着重介绍了与本学位论文相关的排序模型及研究现状.第二章研究了工件既具有加工位置上限又具有完工截止期的单机排序问题.当排序问题1丨kj,dj丨f是多项式时间可解时,我们证明了 Pareto排序问题1|kj,dj|#（Lmax（V）,f）也是多项式时间可解的.其中,f是任意一个正则函数.此外,我们还研究了工件具有退化效应的排序模型,并对此排序模型下的一些问题均给出了多项式时间算法.第三章研究了工件具有加工位置上限的单机排序问题.当工件具有线性退化效应时,对于排序问题1|rj,kj,prec,pj（t）=αj（a+bt）|f,其中f∈{Cmax,Tmax,Lmax,WCmax,fmax,Fmax},通过利用第2.3节中的Lawler规则和扩展的Smith规则,我们给出了相应的多项式时间算法.当工件不具有退化效应时,我们证明了排序问题1|rj,pj=αj|WCmax,1|rj,pj=αj,chains|Fmax和1|kj,pj=αj|∑Uj均是一元NP-困难的.当考虑双代理模型时,我们给出了Pareto排序问题1|ND,kj,pj（t）=αj（a+bt）|#（∑Cj（A）,fmax（B））的一个多项式时间算法.其中,“ND”表示非不交代理模型.此外,我们还考虑了与∑Cj和∑ωjVj这两个指标相关的分层排序问题和正组合排序问题.对于这两种双目标排序问题,我们分别给出了相应的多项式时间算法.第四章研究了工件具有完工截止期的单机排序问题.对于两个历史遗留问题1|dj|∑Tj和1|rj,dj,pmtn|∑Cj,我们分别证明了它们是一元NP-困难的.我们还修正了文献中关于排序问题1|CO|ΣCj（A）:∑Uj（B）≤Q的二元NP-困难性证明的推理错误,并给出了排序问题1|CO,pj（A）=p∑（A）|Cj（A）:∑Uj（B）≤Q的二元NP-困难性证明.其中,“CO”表示竞争代理模型.我们还考虑了完工截止期限制下与违反预期位置上限工件数目指标相关的单机排序问题:对于排序问题1|dj|∑Vj,我们证明了它是一元NP-困难的.对于（kj,pj,dj）一致和（kj,pj）反一致这两种特殊情形,我们分别给出了 O（n2）-时间算法和O（nlogn）-时间算法.此外,我们首次研究了工件具有完工截止期最小化误工量指标的单机排序问题:当工件具有相同工期时,我们证明了排序问题1|dj=d,dj|∑ωjYj是二元NP-困难的,并且给出了此排序问题的拟多项式时间算法和全多项式时间近似方案.当工件的权重均为1时,我们证明了排序问题1|dj|∑Yj是一元NP-困难的.