改进元胞遗传算法求解柔性作业车间调度问题  

Solving flexible job-shop scheduling problem based on improved cellular genetic algorithm

作　　者：陆曈曈[1] 郑小东[2] 张屹[2] 孙莉莉[2] 

机构地区：[1]三峡大学经济与管理学院,宜昌443002 [2]三峡大学机械与动力学院,宜昌443002

出　　处：《现代制造工程》2015年第9期42-47,共6页Modern Manufacturing Engineering

基　　金：国家自然科学基金资助项目(51275274)

摘　　要：针对柔性作业车间调度问题(Flexible Job-shop Scheduling Problem,FJSP)中的不同性能指标优化,提出一种改进的元胞遗传算法。结合柔性作业车间调度的特点,设计一种基于工序编码和设备分配的双层编码,在交叉变异时分别对两层编码进行操作,同时在变异时引入贪婪式变异以加快收敛速度。为了克服传统遗传算法早熟和收敛慢的特点,设计了根据邻居个体自适应的选择算子。将该改进的元胞遗传算法求解柔性作业车间调度问题并同其他遗传算法的测试结果进行比较,表明所提出的改进元胞遗传算法在求解柔性作业车间调度问题上的有效性。An improved cellular genetic algorithm is proposed to study the optimization of different indicators in Flexible Job-shop Scheduling Problem （ FJSP）. Combining with the characteristics of FJSP, a sequence-based and maehine assignment-based coding mechanism is presented. The crossover and mutation processes are carried out to the two levels of the coding and a greedy muta- tion operator is introduced to speed the convergence of the algorithm. An adaptive selection operator based on the fitness of neigh- borhood is designed to prevent from getting into local optimal. The improved cellular genetic algorithm is tested on some instances and compared with other genetic algorithms. The computational results show that the improved cellular genetic algorithm is effec- tive on FJSP.

关 键 词：柔性作业车间调度 元胞遗传算法 双层编码 自适应选择算子 

分 类 号：TH186[机械工程—机械制造及自动化]