带不相关并行机的阻塞FFP的混合遗传算法

Hybrid genetic algorithm for blocking flexible flowshopproblem with unrelated parallel machines

针对带释放时间和运输时间的柔性流水车间问题,每个处理阶段含不相关并行机,且中间无缓冲,以最小化所有工件的加权完成时间之和为目标,提出一种基于遗传算法的EGA&LS优化方法。采用二维矩阵编码方式产生初始种群,执行交叉和变异操作后提出基于工件的多点交换、基于机器号的单点交换和基于工件的多点变异3种邻域结构来产生邻域解。为验证所提算法的性能及有效性,利用大量随机数据进行数据实验,将所提算法与传统GA、结合NEH启发式的改进GA(NEH-IGA)以及遗传参数自适应策略改进GA(IAGA)进行对比分析,实验结果表明了所提算法能够在较短的CPU时间内得到较好的近优解,尤其是求解大规模问题时。

A flexible flowshop problem with release times and transportation times was studied where there were unrelated parallel machine and no buffer between adjacent production stages.The objective was to minimize the sum of weighed completion time of all jobs.A genetic algorithm(GA)-based EGA&LS optimization approach was proposed where two-dimensional matrix coding scheme was used to generate the initial population.After crossover and mutation operations were performed,three new neighborhood structures were applied to yield neighbor solutions,including job-based multiple-point exchange,machine number-based single-point exchange and job-based multiple-point mutation.The performance and effectiveness of the proposed algorithm were assessed over extensive randomly generated instances.Computational results demonstrate that the proposed algorithm can get better near-optimal solutions within a shorter CPU time compared with traditional GA,improved GA with NEH heuristic(NEH-IGA)and improved adaptive GA(IAGA),especially for large-sized problems.