Abstract: In this paper, a disruption management problem on single machine scheduling with sequence dependent setup times 1|s_ij|C_max 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 be suddenly upgraded, causing disruption to the original plan. This makes it necessary to consider jobs' sequence deviation from original plan during rescheduling, which is calculated based on job i's relative position to job j in the revised schedule. In this paper, a bi-objective rescheduling model is built, considering both C_max 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 Nearest Neighbor and Insertion is used to obtain good initial solutions for stage 2 to make extension search along the Pareto front. Computational study shows that the proposed approach outperforms the widely applied NSGA-Ⅱ in both proximity and diversity metrics. And for decision-makers, better decision alternatives 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 computational results could serve as comparison for further studies of this problem.

Key words: rescheduling, sequence disruption, bi-criterion, Pareto front, NSGA-Ⅱ