排序问题是一类重要的组合最优化问题。在传统的排序问题中,工件的加工时间是一个常数,然而在实际生产环境中,工件的加工时间可能与其所处的位置、开工时间或工件本身的特性有关。对于经典排序问题,所有的工件必须被接受,并且在机器上加工,然而,在实际生产过程中,厂家为了获得更大的利润,通常会拒绝那些加工时间长且获利小的工件。同时,工期指派也是一个重要的问题。本文对上述几类排序问题进行了研究。主要内容为:　　第一章主要介绍了排序问题的定义和三参数表示法,并介绍了几类加工时间可变的排序问题的研究背景,及本文工作。　　第二章主要研究退化条件下的工期指派的单机排序问题,目标是确定工件的最优加工顺序、最优工期,使总工期惩罚、误工工件数的惩罚及总完工时间之和最小。　　第三章主要研究带有学习及退化效应和资源分配的工期指派的单机排序问题,目的是使被加工工件的提前、延误、工期指派、资源分配和总完工时间最小。　　第四章主要研究带有退化效应和拒绝惩罚的同类机排序问题。目的是使总完工时间和总拒绝惩罚最小,该问题是NP-难的。对此给出了一个全多项式时间近似算法。