基于改进遗传算法的PCB多级组装线调度

PCB Multi-level Assembly Line Scheduling Based on Improved Genetic Algorithm

为了减少实际工厂中的PCB(printed circuit board)生产时间,针对具有物料BOM表结构的多级PCB组装线调度问题,基于实际的PCB加工工艺在分析了由最终产品的物料清单(BOM)定义的分层部件约束基础上,建立了以最小化最大完工时间为优化目标的混合整数规划模型。基于模型特点,提出了一种三段式编码和主动调度策略的改进遗传算法对模型进行求解。对比实验表明,在相同的计算资源下,对于问题规模大于60×30(订单量×加工中心数)的测试集,所提出的算法获得的最大完工时间比OR-tools求解器减小超过15%,且问题规模越大,解的质量提升越明显,验证了算法的有效性。

In order to reduce the PCB(Printed Circuit Board)production time in the actual factory,aiming at the scheduling problem of a multi-level PCB assembly line with a material BOM structure,based on the actual PCB processing technology and the analysis of the layered component constraints defined by the final product's bill of materials(BOM),a mixed integer programming model with the optimization goal of minimizing the maximum completion time is established.Based on the characteristics of the model,an improved genetic algorithm with three-stage coding and active scheduling strategy is proposed to solve the model.Comparative experiments show that,under the same computing resources,f or the test set with a problem size larger than 60×30(order quantity×number of machining centers),the maximum completion time obtained by the proposed algorithm is reduced by more than 15%compared with the OR-tools solver,and the larger the problem scale,the more obvious the improvement of the solution quality,which verifies the effectiveness of the algorithm.