重新排序(rescheduling)是人们非常关注的现代排序模型，它在制造业和服务行业中起着至关重要的作用．例如，在制造业中由于新订单的到达，订的取消，订单优先顺序的改变，工件到达时间的改变，机器的故障等突发的错位使得我们不得不对还没有加工的工件进行重新排序.　　在对有新工件到达的重新排序研究中，Hall和Potts(2004)研究了在原始工件的序列错位和时间错位限制下的重新排序问题．本文的研究是在Hall和Potts工作的基础上考虑了在GDD(generalized due dates)假设下的重新排序问题，其中GDD假设指工期是按工件的完工顺序分配给工件的．我们研究的内容是按错位限制的不同，以及目标函数的不同，对由此产生的多个重新排序问题的计算复杂性进行分析．此外，我们还研究了相关的Pareto最优重新排序问题.