摘要
柔性作业车间调度问题是对传统车间调度问题的扩充,它更接近于现实的生产调度问题。针对柔性作业车间调度问题,提出了带局域搜索(瓶颈移动法)的混合遗传算法。区别于传统的遗传算法,本文算法用两个向量来表达解,并采用了适应问题特征和染色体结构的交叉和变异算子。基于关键路径的思想,瓶颈移动法使用两种有效的邻域结构:改变关键路径上相邻两工序的加工顺序和为关键路径上的工序分配新设备。为了提高搜索能力,邻域结构可以动态调整。我们在3个代表性标准测试问题上检验了该算法的求解性能。
Flexible job shop scheduling problem （fJSP） is an extension of the classical job shop scheduling problem, which provides a closer approximation to real scheduling problems. We develop a new genetic algorithm hybridized with an innovative local search procedure （bottleneck shifting） for the fJSP. The genetic algorithm uses two vectors to represent solutions of the fJSP. Advanced crossover and mutation operators are proposed to adapt to the special chromosome structure and the characteristics of the problem. The bottleneck shifting works over two kinds of effective neighborhood, which use interchange of operation sequences and assignment of new machines for operations on the critical path. In order to strengthen the search ability, the neighborhood structure can be adjusted dynamically in the local search procedure. The performance of the proposed method is validated with numerical experiments on several representative problems.
出处
《系统工程》
CSCD
北大核心
2007年第9期91-97,共7页
Systems Engineering
基金
国家自然科学基金重大资助项目(70433003)
836资助项目(2003AA-413033)
关键词
柔性作业车间调度
遗传算法
瓶颈移动法
邻域结构
Flexible Job Shop Scheduling Problem
Genetic Algorithm
Bottleneck Shifting
Neighborhood Structure
