基于改进遗传算法的混合流水车间批量调度问题求解

Hybrid Flow Shop Batch Scheduling Problem Solving Based on Improved Genetic Algorithm

针对多品种小批量混流生产模式中生产计划调度复杂的特点,提出解决批量问题的等量分批策略,实现工件在不同工序上同时加工,缩减机器等待时间;以最大完工时间为优化目标,建立混合流水车间批量调度问题数学模型;设计求解模型的改进遗传算法,使用NEH启发式算法和随机生成结合的方式生成优质初始解,采用二元锦标赛进行选择操作,采用二元交叉法进行交叉操作,采用插入变异生成新个体,并使用贪婪插入的领域搜索算法进行局部搜索,解码时采用“子批优先+先空闲先加工”策略。发动机连杆生产案例应用结果表明,混合流水车间批量调度问题模型与改进的遗传算法正确有效。

To address the complex production planning and scheduling characteristics of the mixed flow production model with multiple variet⁃ies and small batches,this paper presents an equal batching strategy to solve the batching problem,so as to realize the simultaneous process⁃ing of workpieces in different processes and reduce the machine waiting time.With the maximum completion time as the optimization objec⁃tive,this paper establishes a mathematical model of the batch scheduling problem in the mixed flow shop;this paper designs an improved ge⁃netic algorithm to solve the model,using a combination of the NEH heuristic algorithm and random generation.The improved genetic algorithm is designed to generate high-quality initial solutions using a combination of the NEH heuristic algorithm and random generation,a binary tour⁃nament for selection operations,a binary crossover for crossover operations,insertion variation for generating new individuals,a greedy inser⁃tion of the domain search algorithm for local search,and a"sub-batch first+idle first"strategy for decoding.The application results of the en⁃gine connecting rod production case show that the hybrid flow shop batch scheduling problem model and the improved genetic algorithm are correct and effective.