【作者】 孙艺；

【导师】 张超勇； 李培根；

【作者基本信息】 华中科技大学 ， 工业工程， 2011， 硕士

【摘要】 制造业中的调度就是对加工过程进行计划,有效的调度方案可以减少加工时间,减小库存,保证交货期,增加企业的效益等。随着全球市场竞争的激烈和客户需求日益的个性化和多样化,调度问题越来越受到人们的重视。置换流水车间调度问题(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算法以及置换流水车间调度的今后研究工作进行了展望。更多还原

【Abstract】 Scheduling in manufacturing industry plays the role of planning in production process. Proper and effective flowshop scheduling can help the enterprise to save time, decrease storage, guarantee due date and improve the production efficiency. With fierce competition in global markets and the increasing customer demand for personalized and diversified, scheduling attracts more and more attention. Permutation flowshop scheduling problem (PFSP) is one common and important scheduling problem. A hybrid particle swarm optimization (PSO) was proposed in this paper to solve single objective PFSP. Meantime, based on solving PFSP, deep research about handling multi-objective PFSP (MPFSP) was developed.Firstly, the aim and significance of this research work are given. Then, A comprehensive review of both former and the state-of-the-art approaches on PFSP and MPFSP was introduced. Meantime, future research trends and challenges in this field were analyzed.Secondly, a hybrid PSO, named NE-HPSO, was proposed to solve PFSP with minimization of makespan. NEH algorithm was taken to produce high quality initial solutions. An improved solution representation rule, smallest position value (SPV), is used to present solutions. Variable neighborhood search (VNS) algorithm is combined with PSO to enhance the local search ability. Two effective neighborhood structures concerned with characteristics of PFSP have been adopted to enhance the performance of VNS. Computational experiments have been conducted on benchmarks (Taillard’s instances) and comparison results with other existing algorithms show the efficiency of the proposed algorithm.Thirdly, research on MPFSP was based on the research of PFSP. Considering the characters of three objectives solved, four constructed methods, NEH,SPT,EDD and CDS was used to improve the quality of inintial solutions. Meantime, a method based on distance was used to keep the diversity of solutions. To improve the performance of PSO, Pareto solutions were stored in a special elite set. What’s more, a vibrate procedure was adopted to enhance the search exploitation of searching optimal solutions for MPFSP. Then comparison of performance between Strength Pareto Evolutionary Algorithm2 (SPEA2) and this proposed was given based on Taillard’s tests.Finally, a software prototype system for solving PFSP and MPFSP was developed with MFC in Visual C++ language based on the previous chapters. Conclusions of the paper as well as the future perspectives of PSO for PFSP were discussed.更多还原