论文部分内容阅读
重新排序模型可以描述如下:一组原始工件已经按照某个准则做好最优加工（排序）方案，但是还没有开始加工.此时，另一组新工件突然到达，需要与原始工件一起加工.生产部门需要调整已有的加工方案，使得在原始工件不打乱太多的情形下得到一个合理的排序.本文沿用Hall和Potts(2004)提出来的序列错位(sequencedisruption)和时间错位(timedisruption)的概念来刻画原始排序被打乱的程度. 本文研究最大加权完工时间的重新排序问题.问题的目标是:(1)在原始排序错位限制的条件下最小化最大加权完工时间;(2)最小化最大加权完工时间与原始排序的错位的加权和.在第二章的研究中我们假设所有工件在0时刻到达;在第三章的研究中我们假设工件具有不同的到达时间，但与其他参数具有反一致性.本文的主要结果如下: 对于Γ∈{Dmax(π*)，Δmax（π*）}，问题1|Γ≤k|maxwjCj可以在多项式时间O(n+nNlognN)内求解. 对于Γ∈{Dmax（π*）,Δmax(π*)}，问题1‖maxwjCj+μΓ可以在多项式时间O（nnN）内求解. 问题1|ΣΔj(π*)≤k|maxwjCj是强NP-困难的. 问题1‖maxwjCj+μΣΔj(π*)是强NP-困难的. 对于Γ∈{Dmax(π*)，Δmax(π*)，ΣDj（π*）}，问题1|anti-(rj，wj),pj=p，Γ≤k|maxwjCj可以在多项式时间内求解. 对于Γ∈{Dmax（π*）,ΣDj(π*)}，问题1|anti-(rj，wj),pj=p|maxwjCj+μΓ可以在多项式时间内求解. 问题1|anti-(rj,wj)，pj=p|maxwjCj+μΔmax（π*）可以在拟多项式时间内求解. 问题1|anti-(rj,wj)，ΣΔj(π*)≤k|maxwjCj是强NP-困难的. 问题1|anti-(rj,Wj)|maxwjCj+μΣΔj（π*）是强NP-困难的.