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

工业工程现代制造工程(Modem Manufacturing Engineering)2015年第9期改进元胞遗传算法求解柔性作业车间调度问题.陆瞳晡，郑小东2,张屹2,孙莉莉2(1三峡大学经济与管理学院，宜昌443002 ；2三峡大学机械与动力学院，宜昌443002)摘耍:针对柔性作业车间调度问题(Flexible Job-shop Scheduling Problem,FJSP)中的不同性能指标优化，提岀一种改进的 元胞遗传算法。结合柔性作业车间调度的待点，设计一种基于工序编码和设备分配的双层编码，在交叉变异时分别对 两层编码进行操作,同时在变异时引入贪婪式变异以加快收敛速度。为了克服传统遗传算法早熟和收敛慢的待点，设 计了根据邻居个体自适应的选择算子。将该改进的元胞遗传算法求解柔性作业车间调度问题并同其他遗传算法的测 试结果进行比较,表明所提出的改进元胞遗传算法在求解柔性作业车间调度问题上的有效性。关赞词:柔性作业车间调度;元胞遗传算法;双层编码；自适应选择算子中图分类号:TH186文献标志码:A文章编号：1671-3133(2015)09-0042-06Solving flexible job-shop scheduling problem based onimproved cellular genetic algorithmLu Tongtong1, Zheng Xiaodong2, Zhang Yi2 ,Sun Lili2(1 College of Economics & Management, China Three Gorges University, Yichang 4430021 Hubei, China ；2 College of Mechanical & Power Engineering9China Three Gorges University,Yichang 443002, Hubei f China )Abstract: 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 machine assignment-based coding mechanism is presented. The crossover and mutation processes are carried out to the two levels of the coding and a greedy mutation 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 live on FJSP.Key words: flexible job-shop scheduling ； cellular genetic algorithm ； double-level coding ； adaptive selection operator0引言生产调度优化是先进制造业和现代管理技术的 核心，国内外许多学者对此进行了研究，其中大部分 研究针对的都是经典作业车间调度问题(Job-shop Scheduling Problem,JSP)O然而在企业的实际生产中， 柔性作业车间调度问题(Flexible Job-shop Scheduling Problem,FJSP)更加符合企业的需求。在JSP中，工件 的每道工序只能在唯一确定的设备上加工。而在 FJSP中，每道丄序至少可以在一台设备上加丄。FJSP 减少了设备约束，使得调度更具柔性，也更加符合实际的生产情况。同JSP相比,FJSP是更加复杂的NP-Hard问题, 目前为止不存在求解FJSP多项式时间复杂度的确定 性算法。比较常用的求解FJSP的方法有整数规划 法、模拟退火(Simulated Annealing, SA)、粒子群 算法"(Particle Swann Optimization, PSO)和遗传算 法(Genetic Algorithm,GA)等。其中,遗传算法以其 原理简单、通用性强且全局搜索能力强的特点在求解 FJSP中得到了广泛地应用。杨晓梅等人在遗传算 法的染色体编码上进行了改进;刘壕等人提出了一 种主动调度的解码机制;张国辉等人设计了一种全42工业工程现代制造工程(Modem Manufacturing Engineering)2015年第9期42工业工程现代制造工程(Modem Manufacturing Engineering)2015年第9期国家自然科学基金资助项目(51275274)42