排序与调度问题是一类重要的组合最优化问题。在经典排序与调度问题中，通常假设工件的加工时间为常数。但在许多实际问题中，工件的加工时间可能与其开工时间或所排位置有着某种联系，由此产生一些新型排序与调度问题。这些加工时间非常数的新型排序与调度问题比经典调度问题更为复杂，绝大多数都是NP-难问题。考虑实际应用的需要，研究这些新型排序与调度问题存在多项式算法的情况很有必要。这些问题的多项式算法一方面可以对某些问题给出求解方法，另一方面还可以为解决其它问题提供近似算法。本文结合现代排序与调度问题研究具有加工时间非常数的几类排序问题。研究的基本思路都是先根据考虑问题构建模型，然后考虑问题的计算复杂性，因为这些问题大多都是NP-难的，因此从一些特殊情况入手，给出问题在可解情况下的多项式时间最优算法，然后再对一般情况给出启发式算法并分析最坏情形下界或者给出动态规划算法。本文研究以下几方面问题：⑴与已经加工过工件之和有关的排序与调度问题考虑了五种排序与调度问题模型，分别是：一般学习效应的模型、已经加工过的工件加工时间的指数函数的学习效应模型、对数效应模型、成组技术下的学习效应模型。对于具有学习效应下单台机器问题，最大完工时间问题利用经典的SPT序的性质均可以得到最优解。总完工时间问题在不考虑成组技术时也可以利用SPT性质得到最优解。具有成组技术的学习效应下，每组中的工件个数相等，利用分组个数和安装时间满足一致关系可以得到问题的最优解。具有学习效应的流水机排序与调度问题更为复杂，考虑机器具有某些优势关系和给定工件在所有机器上的加工时间相同两种情形。对于目标函数为最大完工时间和总完工时间问题分别给出多项式时间算法。对于具有老化效应时，考虑了最大完工时间最小化和总完工时间最小化问题，讨论了0＜a₁≤1，1＜a₁＜M，a₁≥M三种情形，当老化因子1＜a₁≤M时，该问题的最优解仍然没有得到解决。⑵时间相关和学习效应下的排序与调度问题工件的到达时间依赖资源分配问题，对于最大完工时间问题和资源消耗量总和问题进行分析。给出了资源消耗量限制下最小化最大完工时间问题的最优解。对于给定的工件序列，提出最大完工时间限制下最小化资源消耗量的最优分配方案。时间相关和指数学习效应的问题，证明最大完工时间问题和总完工时间问题具有多项式时间算法。而总权完工时间问题、最大延迟问题、总折扣完工时间问题和总误工个数问题不存在多项式时间算法。经典的算法作为问题的启发式算法，得出问题的最坏情况的误差界。并证明在某些特殊情况下这些问题具有多项式时间算法。对于RW问题给出了动态规划算法，当批工件的完工时间和批的规模满足一致关系，给出了多项时间算法。最后研究了成组技术下的退化和学习效应问题。⑶与工期相关的排序与调度问题具有位置退化的共同交货期问题，分析了工件的退化率不相同和相同两种情形，并把这两个问题转化为指派问题进行求解。机器具有多次维修的问题，共同交货期分为包括维修区间和不包括维修区间两种情形讨论，并给出相应的算法和时间复杂性。利用共同工期指派方法和松弛工期指派方法，研究了工期费用函数，提前工件费用和放弃加工的工件的惩罚费用之和最小化的工期指派问题。⑷重新排序与调度问题本节的主要贡献是把重新排序与调度问题引入退化效应和学习效应概念。研究了序列错位和时间错位扰动下的总误工问题，提出了多项式时间算法或者拟多项式时间算法、动态规划算法。与前人的研究相比，本文有以下几个主要的创新点：其一，根据电脑操作系统VISTA和WIN7的实际，提出机器和工人相关的学习效应同时发生的模型，该模型具有更一般性和普适性。根据当前研究学习效应相关的排序与调度学习模型中，出现当工件的数目增加比较多时，给定的工件的实际加工时间可能会突然降到0或者会突然变得更大现象；结合这样方面的实际生产需要，提出了对数相关和指数相关的学习效应模型。改进了以往模型的不足。其二，通过调研发现，在实际的生产中，客户往往是根据生产商的实际的生产能力提供订单的。客户提供加工的工件并不一定是提前到达，因此考虑到达时间和资源量有关的问题是很现实的，也是很迫切的。本文根据生产实际，初次提出加工工件的到达时间是其资源消耗量的减函数。把资源消耗量作为目标或者限制条件去分析问题。其三，在供应链管理的问题中，根据逆向物流企业实际生产情况和要求，本文开创性地提出次品工件重加工问题在退化和学习效应的排序与调度问题应用，并给出有效解的动态规划算法。其四，重新排序尽管比较热，但是由于难度比较大，成果却比较少。特别是在加工时间非常数的情形几乎没有涉及，本研究的一些工作是开创性的。