基于改进迭代局部搜索的多SMT产线多目标优化

Multi-Objective Optimization of Multi-SMT Production Line Based onImproved Iterated Local Search

针对多PCB订单在多条SMT生产线上的生产调度问题,同时考虑SMT生产线治具约束、生产线停线计划约束,建立以最小化总拖期为主目标和最大完工时间为子目标的数学模型。基于问题特性,提出了一种基于问题邻域知识的多目标迭代局部搜索算法求解问题模型,设计带约束的局部搜索在优化主目标函数时,将子目标函数限制在一定的允许量内,设计4种局部搜索算子局部寻优,扰动产生多个扰动解取Pareto最优解作为下一次的迭代解,增加算法全局搜索能力。在相同的计算资源下,对问题规模大于100×5(PCB订单数×SMT生产线数)的测试集,所提出的算法在主目标总拖期优化上相比传统迭代局部搜索算法提升35%以上,验证了算法的有效性。

For the production scheduling problem of multi-PCB orders on multi-SMT production lines,considering the constraints of SMT production line fixture and production line stop plan at the same time,a mathematical model with minimizing the total tardiness as the main goal and the maximum completion time as the sub-goal is established.Based on the characteristics of the problem,a multi-objective iterative local search algorithm based on the neighborhood knowledge of the problem is proposed to solve the problem model.When designing a constrained local search to optimize the main objective function,the sub-objective function is limited to a certain allowable amount,and four local search operators are designed for local optimization.The perturbation generates multiple perturbed solutions to take the Pareto optimal solution as the next iterative solution,which increases the global search capability of the algorithm.Under the same computing resources,for the test set with the problem scale greater than 100×5(the number of PCB orders×the number of SMT production lines),the proposed algorithm improves the total tardiness optimization of the main target by more than 35%compared with the traditional iterative local search algorithm,which verifies the effectiveness of the algorithm.