重新排序是人们十分关注的现代排序模型,它广泛存在于人类的生活中.例如在制造业中由于新订单的到达,订单的取消,订单优先性能的改变,工件到达时间的改变,机器的故障等突然的错位使得我们不得不对未加工的工件进行重新排序.在对有新工件到达的重新排序研究中,Hall和Potts(2004)引入了原始工件的序列错位和时间错位,并研究了在错位限制下最小化排序费用的多个重新排序问题.此后,这一模型的研究十分活跃.本文的研究是在Hall和Potts的工作的基础上引入了原始工件的错位指标数,并约定工件之间具有双全序约束或者单全序约束.我们用prec(O,N)表示双全序约束,用prec(O,φ)表示原始工件单全序约束,并用prec(φ,N)表示新工件单全序约束.我们研究的内容是按照序约束的不同,错位限制的不同,以及目标函数的不同,对由此产生的多个重新排序问题的计算复杂性进行分析.本文的主要结果如下：●对于r∈{Dmax(π*),△max(π*)},γ∈{∑fj(Cj),fmax},重新排序问题1|prec(O,N),r≤κ|γ在多项式时间O(nOnN)内可解.●对于r=∑Dj(π*),γ∈{∑fj(Cj),fmax),重新排序问题1|prec(O,N),r≤k|γ在多项式时间O(no2nN2)内可解.●对于Γ=∑△j(π*),γ∈{∑fj(Cj),fmax},重新排序问题1|prec(O,N),r≤k|γ在拟多项式时间O(n2OnNP(N)nN)内可解.●对于r∈{∑wj∧Dj(π*),∑wj∧△j(π*)},γ∈{∑fj(Cj),fmax},重新排序问题1|prec(O,N),Γ≤k|γ在多项式时间O(nOnN)内可解.●重新排序问题1｜prec(O,φ),∑∧Dj(π*)≤k|∑Cj在多项式时间O(nOnN)内可解.而当prec(O)是以SPT序给出时,该问题在多项式时间O(n+nNlognN)内可解.●重新排序问题1|prec(O,φ),∑∧Dj(π*)≤k|Lmax在多项式时间O(nOnN)内可解.而当prec(O)是以EDD序给出时,该问题在多项式时间O(n+nNlognN)内可解.●对于任意的r重新排序问题1|prec(O,φ),Γ≤k|∑jfj(Cj)和1|prec(φ,N),Γ≤k|∑jfj(CJ)都是强NP-困难的.