灰狼算法在典型车间调度问题中的应用研究

发布时间：2018-05-09 01:24

本文选题：典型车间调度问题 + 不相关并行机调度　；参考：《昆明理工大学》2017年硕士论文

【摘要】：生产调度是制造业企业生产管理的重要工作之一。其中,并行机车间调度问题和置换流水车间调度问题是两类典型的车间调度问题,它们是n个工件在m台机器上加工的许多实际生产系统生产调度问题的简化模型。其中,前者的特征是n个的工件中的每个工件可以在m台机器中的任意一台上进行加工,而后者的特征是n个工件以相同顺序经过m台机器进行加工。业已证明3台以上机器的两类典型车间调度问题即为NP难题,也是目前生产调度研究的热点问题。近年来,随着计算机技术和人工智能的飞速发展,生产调度的智能算法得到了越来越广泛的关注。灰狼算法就是一种新近提出的智能优化算法,由于其有效性高效性,已被应用于求解多种困难的组合优化问题。本文运用灰狼算法对以上两种典型车间调度问题进行研究。首先,以最大完工时间为优化目标,针对不相关并行机调度问题和置换流水车间调度问题,利用灰狼算法思想,基于工序的编码方式随机产生初始种群,采用高效的更新算子分别实现对30个随机产生的实例和240个标准测试实例的测试,并将测试结果与遗传算法进行对比,实验结果表明了灰狼算法的可行性与有效性。其次,以最大完工时间和总流程时间为优化目标,针对多目标置换流水车间调度问题,利用多目标灰狼算法思想,采用基于工序的编码方式,使用构造启发式算法NEH和随机产生两种方式产生初始种群,实现对24个实例的测试,并将结果与经典多目标算法——SPEA2算法进行比较,测试结果表明了多目标灰狼算法的优越性。最后,将求解置换流水车间调度问题的灰狼算法应用于解决工程实例,相比回溯搜索算法最优解加快430s,使得总完工时间缩短了 9.75%,进一步验证了灰狼算法的优越性。
[Abstract]:Production scheduling is one of the important work of manufacturing enterprise production management. Among them, the parallel machine shop scheduling problem and the replacement flow shop scheduling problem are two kinds of typical job shop scheduling problems. They are the simplified models of the production scheduling problems of many practical production systems in which n jobs are processed on m machines. The feature of the former is that each workpiece of n workpieces can be machined on any one of m machines, while the latter is that n workpieces are machined by m machines in the same order. It has been proved that two typical job shop scheduling problems for more than three machines are NP problems and are also hot issues in production scheduling research. In recent years, with the rapid development of computer technology and artificial intelligence, the intelligent algorithm of production scheduling has been paid more and more attention. Grey wolf algorithm is a newly proposed intelligent optimization algorithm. Because of its high efficiency and efficiency, it has been applied to solve a variety of difficult combinatorial optimization problems. In this paper, the gray wolf algorithm is used to study the above two typical job shop scheduling problems. Firstly, aiming at the scheduling problem of unrelated parallel machines and the replacement flow shop scheduling problem, taking the maximum completion time as the optimization goal, the initial population is generated randomly based on the coding method based on the gray wolf algorithm. An efficient update operator is used to test 30 randomly generated and 240 standard test cases, and the test results are compared with the genetic algorithm. The experimental results show the feasibility and effectiveness of the gray wolf algorithm. Secondly, taking the maximum completion time and the total flow time as the optimization goal, aiming at the multi-objective replacement flow shop scheduling problem, using the multi-objective gray wolf algorithm, the coding method based on the working procedure is adopted. The initial population is generated by constructing heuristic algorithm NEH and random generation method, and the test results of 24 instances are realized, and the results are compared with the classical multi-objective algorithm, SPEA2 algorithm. The test results show the superiority of the multi-objective gray wolf algorithm. Finally, the gray wolf algorithm is applied to solve the replacement flow shop scheduling problem. Compared with the backtracking search algorithm, the optimal solution is 430s faster, which shortens the total completion time by 9.75, and further verifies the superiority of the gray wolf algorithm.
【学位授予单位】：昆明理工大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TB49

【参考文献】