Abstract: Based on the periodical preventive maintenance in flow shop,the mathematical optimization model for permutation and non-permutaion flowshop were built respectively by taking min-max makespan as the optimized objective.A Hybrid Genetic Algorithm (HGA) by combining incremental evolution strategy,local search and population diversity supervision scheme was proposed to solve the model.Based on NEH theory,a fast heuristic algorithm was proposed which combined the neighborhood search and the sequence destroy recombination-based global search.Under different problem scales,the comparable result indicated that HGA was more efficient and effective than CPLEX to solve these problems,and the proposed heuristic algorithm could promote operational speed greatly based on assuring optimal solution.In addition,the performance of non-permutation flowshop was much better than that of permutation flowshop with the increasing of workpiece quantity and maintenance frequency.

Key words: flow shop, product scheduling, preventive maintenance, genetic algorithms, heuristic algorithms

摘要： 针对流水线车间,在考虑周期预防性维护的基础上,以最小化最大完工时间为优化目标,分别建立了置换车间与非置换车间两种不同情形下的数学优化模型。设计了结合增量式进化策略、局域搜索机制、种群密度管理的混合遗传算法,对问题进行优化求解。提出了以NEH思想为基础的快速启发式算法,该算法结合了邻域搜索与基于解序列破坏重组的广度搜索机制。在不同问题规模下,混合遗传算法的解与CPLEX精确解的对比结果表明:混合遗传算法可有效求解此类问题,而所提出的启发式算法可在保证解的较优性的基础上大幅度提高运算速度。随着工件数量和维护频次的增加,非置换车间的柔性使得其表现相比置换车间更加优异。

关键词: 流水车间, 生产调度, 预防性维护, 遗传算法, 启发式算法