Flow shop rescheduling problem and its improved repair-based constraint satisfaction algorithm

A two-objective model was constructed for flow shop rescheduling problem with arrivals of new jobs. This model was designed to optimize the original performance index and to minimize differences between rescheduling result and original sequence. This model was decomposed and a two-level model was constructed so that it could be solved easily. The Improved Repair-based Constraint Satisfaction methods (IRCS) were proposed for the two-level model. A heuristic algorithm for variable ordering procedure was designed by using new variable representation, and a variable exchanging heuristic algorithm was used to escape from the local optima. Computational experiments of 90 rescheduling problems were conducted for the proposed algorithms with Nondominated Sorting Genetic Algorithm (NSGA-II) as a competitor. Results revealed the advantages of the proposed algorithms within the same running time.