变邻域遗传算法求解考虑维修时间的柔性作业车间调度问题
首发时间:2021-11-05
摘要:柔性作业车间调度问题是车间生产过程经常遇到的组合优化问题,本文结合实际情况,考虑了机器的预防性维修时间,将其与加工工序合并调度,以最大完工时间最小化为优化目标,生成调度方案。在遗传算法的基础上加入变邻域搜索算法的思想,设计了一种兼具遗传算法和变邻域算法优势的变邻域遗传算法。采用了三种产生初始解的种群初始化方法;在交叉操作时考虑了个体间的相似度,将个体相似度低的个体进行配对以作为交叉操作的父代;设计了基于关键路径的邻域结构,根据适应度值将个体分等级,然后设置与个体等级值等值的邻域搜索范围,使得搜索更加有效。最后,通过实例进行验证,证明了考虑维修时间的必要性,以及所设计算法的有效性。
关键词: 管理工程 柔性作业车间调度 遗传算法 变邻域搜索 预防维修时间
For information in English, please click here
Variable Neighborhood Genetic Algorithm for Flexible Job Shop Scheduling Problem Considering Maintenance Time
Abstract:Flexible job shop scheduling is a combinatorial optimization problem frequently encountered in the process of workshop production. Combining with the actual situation, this paper considers the preventive maintenance time of the machine and combines it with the processing procedure to generate a scheduling scheme with the optimization goal of minimizing the makespan. This paper introduces the idea of variable neighborhood search algorithm and designs a variable neighborhood genetic algorithm which has the advantages of both genetic algorithm and variable neighborhood algorithm. Three population initialization methods are used to generate initial solutions. In the crossover operation, the similarity betweVariable Neighborhood Genetic for Flexible Job Shop Scheduling Problem Considering Maintenance Timeen individuals was considered, and the individuals with low similarity were paired as the parent of the crossover operation. A neighborhood structure based on critical path was designed, and individuals were classified according to fitness value, and then the neighborhood search range was set equal to individual level value, which made the search more effective. Finally, an example is given to prove the necessity of considering the maintenance time and the effectiveness of the proposed algorithm.
Keywords: management engineering flexible job shop scheduling genetic algorithm neighborhood search preventive maintenance time
基金:
引用
No.****
动态公开评议
共计0人参与
勘误表
变邻域遗传算法求解考虑维修时间的柔性作业车间调度问题
评论
全部评论0/1000