排序问题是组合最优化中一类重要问题。经典的排序问题中,所有的工件必须被接受,工件的加工时间为固定常量。然而,在某些实际问题中,工件可以被拒绝,工件的加工时间往往与其所排位置、开工时间或分配的资源有关。　　本文包括五个部分。首先介绍了排序问题的一些背景知识和本文所做的工作。　　第二章讨论带有退化效应,学习效应和资源分配的交货期指派的单机排序问题。所有工件有一个共同的交货期,工件如果在交货期内完工不产生费用,而在交货期之前或之后完工产生相应的提前或延误费用。工件的实际加工时间为与资源分配、开工时间和在排序中位置有关的函数。目标是确定最优交货期的位置、交货期的大小、最优资源分配和工件最优排序,最小化包括提前、延误、交货期位置、交货期大小和资源消耗的总费用。证明该问题是多项式可解的,并给出了一个最优算法。　　第三章考虑带有拒绝工件和机器具有不可用区间的单机排序问题。工件有不同的权和释放时间,权等于工件的加工时间。目标是最小化被接受工件的特定加权总完工时间和被拒绝工件总费用的和。这个问题是一般NP-难的。给出了一个全多项式时间近似方案。　　第四章讨论在同类机环境下,带有退化效应和拒绝的排序问题。工件的加工时间是与开工时间有关的线性不减函数。对于每一个工件能通过支付一定的费用而拒绝加工。目标为最小化接受工件的最大完工时间和拒绝工件总费用的和。给出一个全多项式时间近似方案,从而证明了这个问题是一般NP-难的。　　最后,对本文内容进行了总结,并提出了未来某些可进一步研究的问题的方向。