学位论文 > 优秀研究生学位论文题录展示

基于混合粒子群优化的置换流水车调度方法研究

作　者: 孙艺
导　师: 张超勇；李培根
学　校: 华中科技大学
专　业: 工业工程
关键词: 粒子群优化算法变邻域搜索置换流水车间调度多目标优化
分类号: TH186
类　型: 硕士论文
年　份: 2011年
下　载: 63次
引　用: 0次
阅　读: 论文下载

内容摘要

制造业中的调度就是对加工过程进行计划,有效的调度方案可以减少加工时间,减小库存,保证交货期,增加企业的效益等。随着全球市场竞争的激烈和客户需求日益的个性化和多样化,调度问题越来越受到人们的重视。置换流水车间调度问题(Permutation Flow Shop Scheduling Problem, PFSP)是实际生产制造车间中十分常见且重要的一类排产方式,也是车间调度的一个热点。本文基于粒子群优化(Particle Swarm Optimization,PSO)算法,在解决单目标PFSP的基础上,深入系统的研究了多目标PFSP(Multi-objective PFSP,MPFSP)。首先,阐述了研究的目的和意义,对流水车间单目标、多目标调度问题的算法和研究概况进行了综述。分析了该问题研究存在的不足及未来发展趋势。其次,针对最小化最大完工时间为目标的PFSP,提出一种混合PSO,记为NE-HPSO。该算法采用NEH产生部分初始解,提高算法初始解的质量,采用基于随机键表示法的最小位置实数排序规则(Smallest Position Value,SPV)进行编码。为增强算法的局部搜索能力,设计了基于变邻域搜索算法(Variable neighborhood search, VNS)的局部搜索,邻域结构基于关键路径进行搭建。为了验证该算法的有效性,采取Taillard基准测试集进行测试,测试的到的结果与在该问题取得较好结果的算法进行比较,验证算法的有效性。随后,在单目标PFSP问题研究的基础上,对多目标PFSP问题进行研究。考虑到MPFSP的各个目标的特点,采用四种启发式算法NEH,SPT,EDD及CDS产生四个高质量的初始解,提高初始解的质量。建立外部精英归档集储存Pareto解,并采用聚类的方式维持外部精英归档集的规模。设计一种基于距离的保持解分散性的方法,保证种群的多样性。对于外部精英归档集中的Pareto解进行局部搜索,局部搜索基于改进VNS,邻域结构采用交换,插入,逆序和Or-opt操作。为验证算法的有效性,测试实例仍采用Taillard基准测试集。该算法与解决多目标问题效果较优的改进强度Pareto进化算法(Strength Pareto Evolutionary Algorithm2,SPEA2)进行比较,得到了相当或者更优的结果,证明了算法的优良性能。最后,在上述理论研究的基础上,开发了基于单目标和多目标的置换流水车间调度问题原型系统。对全文进行总结,并对PSO算法以及置换流水车间调度的今后研究工作进行了展望。

基于混合粒子群优化的置换流水车调度方法研究

内容摘要

全文目录

相似论文