基于适应度地形理论的集成式工艺规划与车间调度方法研究

发布时间：2018-05-26 16:47

本文选题：集成式工艺规划与车间调度 + 适应度地形　；参考：《华中科技大学》2014年硕士论文

【摘要】：集成式工艺规划与车间调度（Integrated Process Planning and Scheduling, IPPS）问题是一类经典的车间调度问题，并已被证明为NP-Complete问题。该类问题的适应度地形非常复杂，传统优化算法难以有效对其进行求解，同时大部分国际标准测试问题还远未求得最优解，因此，对IPPS问题求解方法的研究任重道远，该研究重点包括两方面的内容：一是对算法的流程和操作方法进行有效地改进；二是在研究该问题适应度地形的基础上，结合已有的优化算法，设计高效的混合优化算法。本文在结合IPPS问题求解方法已有研究的基础上，提出了基于改进遗传算法的IPPS问题高效求解方法。通过对遗传算法的特点进行分析的基础上，结合IPPS问题的本质特点，对算法的求解流程进行了改进，同时对算法的编码、更新算子等要素进行了合理设计，实验表明该方法取得了较好的效果。接着，以典型实例为对象，对IPPS问题的适应度地形进行了深入的研究。通过引入Logistic模型的概念对IPPS问题解的结构进行了统计分析，发现该问题的适应度地形符合Logistic模型分布，并通过实验证明该类问题的Logistic模型具有很高的分布稳定性。基于IPPS问题的Logistic模型分布，对局部搜索中的邻域结构进行了深入研究和分析，为局部搜索算法设计优良的邻域结构提供了较好的依据。基于以上研究成果，设计了高效的基于变邻域搜索（Variable Neighborhood Search,VNS）的局部优化算法，并将其嵌入改进了的遗传算法中，提出了求解IPPS问题新的高效混合遗传变邻域搜索（GAVNS）算法。该算法能较好地平衡全局搜索能力和局部搜索能力，弥补了单一算法的劣势，使其在求解复杂IPPS问题时变得更加高效。通过该算法对国际通用的Kim标准测试集的24个问题进行求解，刷新了9个问题的世界最好解，另有12个已获得最优解，，实验结果表明该算法能很有效地求解IPPS问题。结合以上研究成果，本文设计并开发了IPPS原型系统，并对系统进行了简要介绍和演示。最后，对全文进行了总结，展望了进一步的研究方向。
[Abstract]:Integrated process planning and shop scheduling integrated Process Planning and Scheduling, IPPS) problem is a classical job shop scheduling problem and has been proved to be a NP-Complete problem. The fitness terrain of this kind of problem is very complex, and it is difficult to solve it effectively by traditional optimization algorithms. At the same time, most of the international standard test problems are far from finding the optimal solution. Therefore, the research on the solving method of IPPS problem has a long way to go. The research focuses on two aspects: one is to improve the flow and operation methods of the algorithm effectively; the other is to design an efficient hybrid optimization algorithm on the basis of studying the terrain fitness of the problem and combining the existing optimization algorithms. In this paper, an efficient IPPS problem solving method based on improved genetic algorithm is proposed on the basis of the existing research on IPPS problem solving method. Based on the analysis of the characteristics of genetic algorithm and the essential characteristics of IPPS problem, the solution flow of the algorithm is improved. At the same time, the coding, updating operator and other elements of the algorithm are reasonably designed. The experimental results show that the method has a good effect. Then, taking a typical example as an example, the fitness terrain of IPPS problem is studied in depth. By introducing the concept of Logistic model, the structure of the solution of the IPPS problem is statistically analyzed. It is found that the fitness of the problem is in accordance with the distribution of the Logistic model. The experimental results show that the Logistic model of this kind of problem has a high stability of distribution. Based on the Logistic model distribution of IPPS problem, the neighborhood structure in local search is deeply studied and analyzed, which provides a good basis for the local search algorithm to design good neighborhood structure. Based on the above research results, an efficient local optimization algorithm based on variable Neighborhood search Neighborhood (VNS) is designed, and embedded in the improved genetic algorithm, a new efficient hybrid genetic variable neighborhood search algorithm for solving IPPS problem is proposed. The algorithm can balance the global search ability and the local search ability, make up for the disadvantage of the single algorithm, and make it more efficient in solving the complex IPPS problem. The algorithm is used to solve 24 problems of the international Kim standard test set, which refreshes the best solution of 9 problems in the world, and 12 other problems have been obtained. The experimental results show that the algorithm can solve the IPPS problem effectively. Based on the above research results, a prototype system of IPPS is designed and developed, and the system is introduced and demonstrated briefly. Finally, the paper summarizes the whole paper and looks forward to the future research direction.
【学位授予单位】：华中科技大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP18;TB497

【相似文献】