重新排序是排序论中的新兴研究课题.由于其重要的理论研究价值及广阔的实际应用背景,在过去的十年里,重新排序得到广泛的研究。重新排序模型可以描述如下：生产计划者已经将一组原始工件按照某个最优准则做好加工计划(排序),并且承诺于客户的交货日期已经确定下来,但是工件的加工还没有开始.此时,另外一组新工件非预期地到达并需要与原始工件一起进行加工.生产计划者需要调整已有的加工计划并在排序费用和原始工件的错位之间进行权衡,目的是在不过多地失信于客户的条件下,得到一个费用合理的排序。　　 本研究分两部分。第一部分研究工件有到达时间的Pareto最优化重新排序问题,目标函数是同时最小化最大完工时间与总的序列错位和.第二部分研究本文新引入的两个重新排序问题：⑴工件错位限制重新排序问题,其特点是每个原始工件都有自己的错位限制；⑵加权错位重新排序问题,其特点是每个原始工件都有自己的错位权重。在第二章,我们研究Pareto最优化重新排序问题1|ri|Cmax,∑Dj).对于工件有到达时间的总序列错位和约束下最小化最大完工时间的重新排序问题.文献中给出一个弱多项式时间算法.对于其相应的Pareto最优化问题,本文给出一个强多项式时间算法来找到所有的Pareto最优点.作为推论,工件有到达时间的总序列错位和约束下最小化最大完工时间重新排序问题也可在强多项式时间内得到解决。在第三章,我们研究工件错位限制重新排序问题以及加权错位重新排序问题.主要结果如下：①给出了工件序列错位约束下最小化最大延迟的重新排序问题的多项式时间算法；②给出了工件序列错位约束下最小化完工时间总和的重新排序问题的多项式时间算法；③分别给出了工件时间错位约束下最小化完工时间总和及最小化最大延迟这两个重新排序问题的强NP-困难性证明,近似算法及其不可近似性结果；④分别给出了加权时间错位和约束下,目标函数为最小化完工时间总和,最大完工时间及最大延迟这三个重新排序问题的强NP-困难性证明；⑤对特殊情形下的工件错位限制重新排序问题和加权错位重新排序问题,分别给出了多项式时间算法。