中文摘要：

在安装时间和次序相关的单机调度问题中，为应对突发性的工件优先级变动造成的影响，构建了双目标重调度模型。原目标为生产的流程时间，扰动目标为工件的加工次序扰动。针对模型中的双目标，设计了基于有效解的两阶段混合启发式算法进行求解，在原目标和扰动目标之间进行权衡。混合算法第一阶段里，基于任意单个工件次序变化将双目标问题转化成单目标TSP问题，利用最近邻域和插入混合求得单目标问题的若干解，构成初始种群。第二阶段中基于非支配排序遗传算法在处理多目标问题上的优势，对初始种群进行扩展搜索，最后输出问题的有效前沿。通过数值试验运算比较分析若干针对有效解集的指标，验证了混合算法求得的解集在多样性和临近性上要优于单纯的非支配排序遗传算法。该混合算法可以有效地解决具有安装时间的加工次序扰动问题。

英文摘要：

In this paper, a disruption management problem on single machine scheduling with sequence de- pendent setup times 11 sii Cmox is studied. It is originated from practical situations where jobs come from different job families, and during the implementation of initial schedule the priority of certain job would besuddenly upgraded, causing disruption to the original plan. This makes it necessary to conmder jobs＂ se- quence deviation from original plan during rescheduling, which is calculated based on job i~s relative posi- tion to job j in the revised schedule. In this paper, a hi-objective rescheduling model is built, considering both C~ and sequence deviation. In order to effectively solve the model, local search is combined with global search and a two-stage approach is designed. In stage 1 construction heuristic based on mixed Nea- rest Neighbor and Insertion is used to obtain good initial solutions for stage 2 to make extension search a- long the Pareto front. Computational study shows that the proposed approach outperforms the widely ap- plied NSGA-II in both proximity and diversity metrics. And for decision-makers, better decision alterna- tives could be provided for the trade-off between production cost and deviation of disruption. The research sets an example for applying hybrid metaheuristic to deal with disruption in machine scheduling and com- putational results could serve as comparison for further studies of this problem.