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

发布时间：2018-08-16 09:47

【摘要】：制造业中的调度就是对加工过程进行计划,有效的调度方案可以减少加工时间,减小库存,保证交货期,增加企业的效益等。随着全球市场竞争的激烈和客户需求日益的个性化和多样化,调度问题越来越受到人们的重视。置换流水车间调度问题(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]:The scheduling of manufacturing industry is to plan the processing process. The effective scheduling scheme can reduce the processing time, reduce the inventory, ensure the delivery time, increase the efficiency of the enterprise, and so on. With the fierce competition in the global market and the increasing individuation and diversification of customer demand, people pay more and more attention to the scheduling problem. Replacement flow shop scheduling problem (Permutation Flow Shop Scheduling Problem, PFSP) is a very common and important scheduling method in practical production shop, and it is also a hot spot in job shop scheduling. Based on the particle swarm optimization (Particle Swarm) optimization algorithm and the solution of single objective PFSP, the multiobjective PFSP (Multi-objective PFSPN MPFSP) is studied systematically in this paper. Firstly, the purpose and significance of the research are described, and the algorithms and research situation of single objective and multi-objective scheduling problem in flow shop are summarized. The deficiency of the research and the development trend in the future are analyzed. Secondly, for PFSPs with the goal of minimizing the maximum completion time, a hybrid PSO NE-HPSOs is proposed. The algorithm uses NEH to generate partial initial solution, which improves the quality of initial solution, and uses the minimum position real number sorting rule based on stochastic key representation (Smallest Position value (Smallest Position) to code. In order to enhance the local search ability of the algorithm, the local search based on the variable neighborhood search algorithm (Variable neighborhood search, VNS) is designed, and the neighborhood structure is built based on the critical path. In order to verify the validity of the algorithm, the validity of the algorithm is verified by using the Taillard benchmark set, and the results obtained are compared with those obtained in the problem. Then, based on the study of single objective PFSP problem, the multi-objective PFSP problem is studied. Considering the characteristics of each target of MPFSP, four heuristic algorithms, NEH / SPT / EDD and CDS, are used to produce four high quality initial solutions, which can improve the quality of the initial solution. The Pareto solution is stored in the external elite archive set, and the scale of the external elite archive set is maintained by clustering. A distance-based method is designed to keep the diversity of the population. The local search for the Pareto solution in the external elite archival set is based on the improved VNSs, and the neighborhood structure uses exchange, insert, reverse sequence and Or-opt operations. In order to verify the validity of the algorithm, the Taillard benchmark set is still used in the test example. The algorithm is compared with the improved strength Pareto evolutionary algorithm (Strength Pareto Evolutionary algorithm 2 / SPEA2), which has better effect in solving multi-objective problems. The results are equivalent or better, and the excellent performance of the algorithm is proved. Finally, on the basis of the above theoretical research, a prototype system of permutation shop scheduling problem based on single objective and multi-objective is developed. This paper summarizes the whole paper, and looks forward to the future research work of PSO algorithm and replacement flow shop scheduling.
【学位授予单位】：华中科技大学
【学位级别】：硕士
【学位授予年份】：2011
【分类号】：TH186

【相似文献】