本文考虑几类加工时间可变的单机排序问题,详述如下：首先,第一章介绍排序问题的研究背景、研究现状及研究内容。其次,第二章针对带有学习效应、加工时间可控和退化工件在单机环境下进行了研究,目标为确定工件最优排序、最优加工时间和最优资源分配量,将最大完工时间、总完工时间、完工时间差和资源消耗的费用之和进行极小化。考虑了学习因子与工件有关的线性资源函数,学习效应与工件的实际加工时间依赖开始时间结合在一起的凸资源函数两种情况,通过分析最优解的一些重要性质,将这两个问题分别转化为指派问题,给出了两个计算复杂性为O(n3)的最优算法。再次,第三章针对带有配送时间、加工时间与位置相关和多个工期在单机问题下进行研究。假设工件配送时间与工件等待时间成比例,将带有配送时间和加工时间依赖位置的单机排序问题与多个工期的单机排序问题结合成新的模型。首先分析了此类问题相关重要的性质;然后将这个问题转化为一个指派问题,证明出这个问题可以在多项式时间内可以解决的;最后,通过复杂性为O(n3)的算法,确定了最优排序、最优工期和极小化工件的提前、延误和工期的总费用。然后,第四章研究了带有分段线性递减加工时间和拒绝工件的单机排序问题。在这一模型中,工件的实际加工时间是关于开始时间的分段线性递减函数,目标是使被接受工件最大完工时间与被拒绝工件总惩罚达到最优的值,即最小值。该问题为NP难的问题。在对此问题的分析的基础上,设计了一个全多项式近似策略。全多项式近似策略的计算复杂性为O(n4L4/ε3)。最后,对本文的主要结论进行归纳总结。