排序问题是一类重要的组合优化问题。在经典排序问题中,通常假设工件的加工时间为常数。但在许多实际问题中,工件的加工时间可能与其开工时间、所用资源或所排位置有着某种联系,由此产生一些现代排序问题.这些现代排序问题比经典排序问题更为复杂,绝大多数都是NP-难问题.对这些NP-难问题,讨论它的近似算法,并给出算法的最坏情况界很有必要;考虑实际应用的需要,研究现代排序问题存在多项式算法的情况也很有必要,这些问题的多项式算法一方面可以对某些问题给出求解方法,另一方面还可以为解决其它问题提供近似算法。本文研究工件加工时间可变的现代排序问题,主要在如下几个方面做了一些工作: 1.工件加工时间是开工时间的增加函数的排序问题。 (a)最大完工时间单机排序问题。对于一般模型中工件具有有跟森林约束和有串并有向图约束的极小化最大完工时间单机问题分别给出了最优算法。 (b)加权完工时间和单机排序问题.对增长率与基本加工时间相关且工件具有有跟森林约束和有串并有向图约束的的单机问题进行研究,分别给出了最优算法。 (C)流水作业排序问题.对机器间满足优势关系的不等待或无空闲问题进行研究,目标函数分别为最大完工时间、加权完工时间和与最大延误,对它们分别给出了最优算法。 2.工件加工时间是开工时间的减少函数的排序问题。 (a)单机排序问题。研究递减率与基本加工时间相关的单机问题,对最大完工时间问题、加权完工时间和问题、工件具有平行链约束的加权完工时间和问题、最大费用问题与最大延误问题分别给出了最优算法。 (b)流水作业排序问题。对两台机器极小化最大完工时间问题,证明了利用John-son规则可以求得最优排序。对工件各工序基本加工时间均相等的流水作业问题进行了研究,并对某些情况给出了明确结论。 3.加工时间可控的单机可控排序问题。 首先,研究加工时间一般可控的排序问题,目标函数分别为极小化完工时间和、完工时间偏差和与压缩费用的线性组合,等待时间和、等待时间偏差和与压缩费用的线性组合。提前时间、延误时间、工期与压缩费用的线性组合。所有这些问题都可转化为指派问题,从而多项式时间可解。其次,研究加工时间离散可控的排序问题,对几类多目标问题进行了转化。4.具有学习效应的排序问题. 对单机问题,研究了几类多目标问题,它们都可转化为指派问题,从而多项式时 间可解.对流水作业问题,用反例说明在工件引入学习效应后经典的Johllson规则 对两台机器最大完工时间问题不是多项式最优算法,从而用,Jo hnson规则作为它的 近似算法,分析了它的最坏情况界.对m台机器最大完工时间与完工时间和情况, 分别给出了近似算法并分析了它们的最坏情况界.同时对某些特殊情况给出了多项 式算法.关键词:排序,单机,流水作业,线性加工时间,有跟森林,串并有向图,最坏情况界,最优算法,恶化工件,可控加工时间,学习效应