论文部分内容阅读
重新排序(rescheduling)是人们非常关注的现代排序模型,它在制造业和服务行业中起着至关重要的作用.例如,在制造业中由于新订单的到达,订单的取消,订单优先顺序的改变,工件到达时间的改变,机器的故障等突发的错位使得我们不得不对还没有加工的工件进行重新排序.在对有新工件到达的重新排序研究中,Hall和Potts (2004)研究了在原始工件的序列错位和时间错位限制下的重新排序问题.本文的研究是在Hall和Potts工作的基础上考虑了在GDD(generalized due dates)假设下的重新排序问题,其中GDD假设指工期是按工件的完工顺序分配给工件的.我们研究的内容是按错位限制的不同,以及目标函数的不同,对由此产生的多个重新排序问题的计算复杂性进行分析.此外,我们还研究了相关的Pareto最优重新排序问题.本文的主要结果如下：·对于Γ∈{Dmax(π*),△max(π*)},γ∈{∑Tj,Lmax},重新排序问题1 | gdd,Γ≤k| γ在多项式时间O(n+nNlognN)内可解.·对于Γ=∑△j(π*),γ∈{∑Tj,Lmax},重新排序问题1| gdd,Γ≤k|γ和1 | gdd | γ+μΓ是强NP-困难的.·对于Γ∈{Dmax(π*),△max(π*)},γ∈{∑Tj,Lmax},重新排序问题1 | gdd |γ+μΓ在多项式时间O(nNlognN+nNno)内可解.·对于γ∈{∑Tj,Lmax},Pareto最优重新排序问题1| gdd |(Dmax(π*),γ)和1 | gdd |(△max(π*),γ)都在多项式时间O(nnN)内可解.·重新排序问题1 | gdd,△max(π)≤k | Lmax是强NP-困难的.但当假设所有的位置工期dj≤0,对于0≤j≤n均成立时,我们给出问题1| gdd,△max(π)≤k | Lmax的一个最好可能的多项式时间近似算法.·建立了重新排序问题1| gdd,rR,△max(π*)≤k | γ的若干性质.其中γ,∈ {∑Tj,Lmax)证明重新排序问题1| gdd,rR,△max(π)≤k | Lmax是强NP-困难的.证明重新排序问题1| gdd,rR,△max(π)≤k | ∑Tj在拟多项式时间O(n2PT)内可解.