基于优先权编码改进遗传算法的车间作业调度优化

发布时间：2018-03-05 11:21

本文选题：车间作业调度　切入点：改进遗传算法　出处：《青岛理工大学》2011年硕士论文　论文类型：学位论文

【摘要】：车间作业调度问题（Job-shop Scheduling Problem，简称JSP）是生产管理的关键内容之一，好的求解方法不仅可以提高生产效率、降低生产成本，而且还可以加快企业对市场的响应速度以提高企业的经济效益和市场竞争力。由于车间作业调度问题是典型的NP-hard问题，传统的优化算法很难求得其最优解，所以本文在前人研究的基础上，采用了目前应用最广泛的遗传算法作为求解方法，并对传统的遗传算法进行了改进，提高了算法优化性能。设计了基于优先权矩阵的编码方法，并建立了以最大完工时间为目标的车间作业调度优化数学模型，根据优先权矩阵编码方法，设计了相应的交叉和变异算子，实例计算表明该改进遗传算法可以提高对车间作业调度问题的寻优能力和求解效率。建立了柔性车间作业调度模型，设计了基于双层编码的遗传算法对其进行求解，并以优先权编码为基础设计了相应的双层编码方法、解码算子、交叉算子和变异算子，，针对不同的优化目标对计算实例进行了优化。以最大完工时间、机床最大负荷、机床总负荷与交货期为目标，建立了多目标柔性车间作业调度问题的数学模型。根据其特点设计了分层Pareto非劣前沿分级方法，提高了优化效率。分析了调度问题中的时间因素，将工件运输时间作为独立一部分进行计算，使得调度模型更加贴近生产实际。在相应理论研究的基础上，采用VC++语言编制完成了车间作业调度优化设计软件，优化实例表明了算法的有效性。
[Abstract]:Job shop scheduling problem Job-shop Scheduling problem (JSP) is one of the key contents of production management. A good solution method can not only improve production efficiency, but also reduce production cost. Moreover, it can speed up the response of enterprises to the market to improve their economic efficiency and market competitiveness. Because the job-shop scheduling problem is a typical NP-hard problem, it is difficult for the traditional optimization algorithm to find its optimal solution. Therefore, based on the previous research, this paper adopts the most widely used genetic algorithm as the solution method, and improves the traditional genetic algorithm to improve the optimization performance of the algorithm. The coding method based on priority matrix is designed, and the mathematical model of job shop scheduling optimization with maximum completion time is established. According to the coding method of priority matrix, the corresponding crossover and mutation operators are designed. The example shows that the improved genetic algorithm can improve the optimization ability and efficiency of the job shop scheduling problem. The flexible job shop scheduling model is established, and the genetic algorithm based on two-layer coding is designed to solve it. Based on priority coding, the corresponding double-layer coding method, decoding operator, crossover operator and mutation operator are designed. The calculation examples are optimized for different optimization objectives. Aiming at the maximum completion time, the maximum load of machine tool, the total load of machine tool and the due date, the mathematical model of multi-objective flexible job shop scheduling problem is established. According to its characteristics, a hierarchical Pareto non-inferior frontier classification method is designed. The optimization efficiency is improved. The time factor in the scheduling problem is analyzed and the workpiece transportation time is calculated as an independent part to make the scheduling model more close to the production practice. On the basis of the corresponding theoretical research, the optimization design software of job shop scheduling is developed by using VC language. The optimization example shows the effectiveness of the algorithm.
【学位授予单位】：青岛理工大学
【学位级别】：硕士
【学位授予年份】：2011
【分类号】：TH186;TP18

【参考文献】