作业车间排序重调度问题及其改进修复约束满足算法

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

作业车间往往因出现新作业而需要进行重调度。为尽量减少由重调度带来的计划变更,除了优化原有的性能指标外,还应减小重调度结果与原排序之间的差异。由此,提出一种双目标优化模型。为方便求解,将模型进行了分解,构建了可以分步求解的分级模型。对分级模型提出改进的修复约束满足算法(修复法),通过采用新的变量表示形式,设计了变量排序的启发式算法,并采用变量互换启发式算法,以保证全局搜索性能。以90个作业车间标准算例为基础,设计了重调度算例,并与现有代表性的第二代非支配排序遗传算法优化结果进行了对比,结果表明在相同运行时间下,所提算法更具优越性。

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.