关键词: 作业车间排序, 重调度, 修复约束满足算法, 启发式算法, 双目标优化

Abstract: 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-Ⅱ) as a competitor. Results revealed the advantages of the proposed algorithms within the same running time.

Key words: flow shop scheduling, rescheduling, repair-based constraint satisfaction method, heuristic algorithm, two object optimization