重新排序模型可以描述如下: 一组原始工件已经按照某个准则做好最优加工 ~(排序)~方案, 但是还没有开始加工. 此时, 另一组新工件突然到达, 需要与原始工件一起加工. 生产部门需要调整已有的加工方案, 使得在原始工件不打乱太多的情形下得到一个合理的排序. 本文研究最大加权完工时间的重新排序问题, 问题的目标是: 1) 在原始排序错位限制的条件下最小化最大加权完工时间; 2) 最小化最大加权完工时间与原始排序的错位的加权和. 在本文研究中我们假设所有工件在~0~时刻到达. 文章的主要结果:对于$\mathit{\Gamma }\in \{D_{max}({\pi }^{\ast }),{\mathrm{\Delta }}_{max}({\pi }^{\ast })\}$, 给出了问题$1|\mathit{\Gamma }\le k|max{w}_j{C}_j$~和问题$1||max{w}_j{C}_j+\mu \mathit{\Gamma }$~多项式时间的求解算法;证明了问题$1|\sum {\mathrm{\Delta }}_j({\pi }^{\ast })\le k|max{w}_j{C}_j$~和问题$1||max{w}_j{C}_j+\mu \sum {\mathrm{\Delta }}_j({\pi }^{\ast })$~是强~NP-困难的.

The model of rescheduling can be stated as follows: A set of original jobs has been scheduled, but has not been processed. Then a new set of jobs arrives unexpectedly before the processing starts and has to be scheduled on a common machine with the set of original jobs. The production planners need to adjust the existing schedule and make a trade-off between the scheduling cost and the disruptions of the original jobs. In this paper, we study the rescheduling problem with the maximum weighted completion time of all jobs as the scheduling cost. The goal of the problem is to minimize either 1) the maximum weighted completion time of the jobs under an upper restriction on the disruption constraints of the original schedule, or 2) the weighted sum of the maximum weighted completion time of the jobs and the disruption cost of the original schedule. All jobs arrive at time zero. The main results of this paper are as follows: For $\mathit{\Gamma }\in \{D_{max}({\pi }^{\ast }),{\mathrm{\Delta }}_{max}({\pi }^{\ast })\}$, we provide polynomial time algorithms for problems $1|\mathit{\Gamma }\le k|max{w}_j{C}_j$ and $1||max{w}_j{C}_j+\mu \mathit{\Gamma }$; We also show that problems $1|\sum {\mathrm{\Delta }}_j({\pi }^{\ast })\le k|max{w}_j{C}_j$ and $1||max{w}_j{C}_j+\mu \sum {\mathrm{\Delta }}_j({\pi }^{\ast })$ are strongly NP-hard.