% !Mode:: "TeX:UTF-8"

\chapter{绪论}[Introduction]
% 25页左右生在红旗下 长在春风里研究背景及意义
\section{研究背景及意义}[Background and significance of research]
% 制造业概述

制造业是国民经济发展的支柱产业，对经济增长起着重要的推进作用。我国的“十四五”规划指出，要深入实施增强制造业核心竞争力和技术改造的专项计划，鼓励企业应用先进适用技术、加强设备更新和新产品规模化应用，培育先进制造业集群，推动集成电路、高端数控机床等产业的创新发展，推动制造业产品“增品种、提品质、创品牌”\cite{14th_five_year_plan}。“中国制造2025”进一步指出，要加快发展智能制造装备和产品，组织研发具有深度感知、智慧决策、自动执行功能的智能制造装备以及智能化生产线，提升国家制造业创新能力，实现制造强国的战略任务。 大力发展先进智能制造，促进新质生产力的形成和现代化产业体系的构建，确保我国产业体系的完整性、先进性和安全性，是实现中国式现代化的必由之路~\cite{zang_roadmap_research_2022,wang_leading_production_2024}。

% 电子制造业概述
电子制造是专注于研究、制造和生产各类电子设备和电子元件的产业，涵盖了电子产品从设计、制造到测试的全过程，作为现代制造业的重要组成部分，其在诸多领域如消费电子、通信设备、汽车电子等有着广泛的应用，具有市场规模大、技术进步快、产业关联度强等特点。电子制造业的发展对整个产业链的升级与变革起到了重要的推动作用。
现代电子制造技术包含电路设计、元件选型、表面组装和生产质量管控等多个方面。
其中，表面组装是将电子元件安装在印制电路板（Printed Circuit Board，PCB）焊盘上的板级组装技术，是现代电子组装技术的核心。
近年来，随着电子消费市场需求的持续增长，表面组装等制造自动化技术也在快速地发展进步与更新迭代。
表面组装过程优化通过调整生产工序、改进组装流程以最大化利用生产制造设备的性能，在生产效率提升方面起着关键作用，推动着生产流程向高效化转型，是现代电子制造业核心竞争力的重要体现。


% 表面组装生产线介绍
传统的表面组装生产线构成如图\ref{ch1:figure:assembly-line}所示，主要包括上板机、丝网印刷机、贴片机、回流焊炉、光学检测机以及下板机。作为生产线的前端设备，上板机内部装载有堆叠放置的电路板，通过逐级提升的方式将其传入生产线。丝网印刷机用于将锡膏印制到电路板上的焊接位置（即焊盘），贴片机则将电子元件准确地放置到涂有锡膏的电路板上。
回流焊炉将贴装好的电路板进行加热，使锡膏融化并与电子元件的引脚连接。冷却凝固后的锡膏在电子元件和焊盘间形成稳固的连接。光学检测机作为可选设备，用于检测表面组装质量。最后，下板机负责接收完成组装的电路板。


\vspace{0.25em}
\begin{figure}[htpb]
	\centering
	\includegraphics[scale=0.65]{chapter1/assembly-line.eps}
	\bicaption[ch1:figure:assembly-line]{}{表面组装生产线的构成}{Fig.$\!$}{Composition of a surface assembly line}
	\vspace{-1em}
\end{figure}

% 贴片机的发展历程

贴片机作为表面组装生产线中最关键、最重要的设备，其主要任务是完成PCB上元件的表面组装工作。贴片机的研制与表面组装元件的发展密不可分。图\ref{ch1_fig_smt_history}展示了表面组装相关技术的发展历程。自上世纪七十年代后期，日本的大型电子企业集团率先开始自动贴片机的研制工作，并逐渐将贴片机由内部专用设备改为标准化的商用设备，开始批量应用到电子设备加工生产中。经过四十余年的迅速发展，贴片机逐步向着精密、高速、模块化的方向发展，以松下、三洋、韩华等为代表的企业研发的贴片机占据了国内外主要市场。贴片机的生产制造能力是反映电子制造业发展水平的重要指标之一，表面组装生产线的生产效率更是整个电子产业链发展中的核心竞争力。我国作为制造业大国，电子制造产业起步相对较晚而发展迅速，目前已经成为世界上贴片机应用最广的国家之一，对贴片机的需求也亟待从依赖国外进口走向国内自主研发。

\begin{figure}[H]
	\centering
	\includegraphics[scale=0.975]{chapter1/surface-mount-history.eps}
	\vspace{-1em}
	\bicaption[ch1_fig_smt_history]{}{表面组装技术的发展历程}{Fig.$\!$}{The development history of surface mount technology}
\end{figure}

% 贴片机中涉及的关键性技术（引出表面组装技术）
贴片机作为光机电一体化设备，其研制过程是涉及机械设计技术、运动控制技术、组装过程优化技术、软件工程技术和机器视觉图像处理技术等多学科交叉的系统性工程。 其中，表面组装过程优化技术极大影响着贴片机的组装效率。
表面组装过程优化问题是一类特殊的复杂优化问题，启发式、数学规划和机器学习等算法常用于解决此类工业组合优化问题\cite{schlenkrich_solving_2023}。
作为一个高维度、多变量且高度耦合的非确定性问题，该问题具有较高的时间复杂度，导致现有的优化算法难以在可接受时间内找到全局最优解。同时，表面组装过程还面临着来自内外部多种因素的制约，限制了算法的适用范围。为了提升组装过程效率，制造商常采用多台贴片机协同作业的方式来完成PCB的组装任务，由此带来了生产线负载平衡问题。组装生产线的优化研究的是平衡不同贴片机之间的工作负载、最小化贴片机最长工作时间的策略。
表面组装过程优化，作为工业实际需求驱动的课题，在系统建模与算法设计时，需在满足约束条件下优化生产效率指标，以确保优化结果的高效性、可行性与可部署性。

\section{表面组装系统概述}[Overview of surface assembly system]

本文研究的是装配有并列式贴片头的贴片机（以下简称并列式贴片机），其布局如图\ref{ch1:figure:surface-mounter}所示，包括一个固定的PCB平台，两个固定的供料基座，以及带多个贴片头的移动悬臂，装载有元件的供料器安装在前后两个基座上。带式、管式、托盘式的供料器用于供给各类封装元件。并列式贴片机适用于中小批量生产，也可将多台贴片机组合用于大批量生产。悬臂在电路板和供料基座之间移动，其装配有多个贴片头用于拾取和贴装元件，贴片头上配备的飞行相机用于元件检测；对于大尺寸的元件，悬臂必须移动到固定相机上进行检测。元件组装所用的吸嘴类型和其封装的尺寸相关，自动吸嘴更换器（Auto Nozzle Changer，ANC）中装载着不同类型的吸嘴，以适应贴片机对多种元件封装的装配要求。并列式设计结构的贴片头其间隔为槽位间隔的整数倍，使多个贴片头可以同时从不同槽上的供料器中拾取元件。相较于装配有转塔式贴片头的贴片机（以下简称转塔式贴片机），并列式贴片机的机械结构简单，可靠性强，多头同时取料装配效率更高，可实现高速、高精度表面组装，适用的元件封装类型更加多样，因此也被称为多功能贴片机，其在结构上主要由以下部分组成：

\begin{figure}
	\centering
	\includegraphics[scale=0.24]{chapter1/surface-mounter-layout.eps}
	\bicaption[ch1:figure:surface-mounter]{}{贴片机组成结构图}{Fig.$\!$}{Composition and structure of surface mounter}
\end{figure}

\begin{enumerate}
	\item[1)] \emph{传动与驱动机构}:	贴片机的基本构成为一个高精密的运动控制系统。传动系统负责将电路板传送至贴装区域，伺服定位系统支撑着贴片头，保证其精确定位和精准移动。贴片机的主体包括两条相互平行的定臂和一条动臂，由三个直线导轨控制悬臂在水平面内沿X轴和Y轴方向运动。直线导轨由电机驱动，两个定臂对应的电机为Y轴方向电机，带动动臂沿Y轴方向运动，动臂对应的电机为X轴方向电机，带动悬臂实现X轴方向运动。悬臂上安装有多个并列排放的贴片头，贴片头上的吸杆均可以在电机的驱动下实现Z轴方向运动，完成对元件的拾取和贴装，另有R轴电机带动吸杆绕轴转动，实现对拾取元件的角度偏移进行补偿。
	\item[2)] \emph{元件供应与贴装机构}:	元件由供料器供应，不同封装的元件所使用的供料器类型、占用的槽位数也不相同。供料器通过机械化接口固定在供料器基座上，该接口被称为供料器槽。元件的拾取由贴片头上的吸杆完成，供应则由供料器提供。吸杆内部中空并在底部装有吸嘴，贴片头与真空泵连通，真空泵抽气在吸杆内部建立真空以吸取元件、关闭真空以贴装元件。贴片头为完成多种类型元件的组装，需移动至ANC进行吸嘴的安装与更换。
	\item[3)] \emph{视觉检测系统}:	贴片机配备视觉系统实现高精度组装，其由一个基准相机、一个固定相机和多个飞行相机构成。基准相机用以检测PCB上的基准点，对电路板位置进行校准补偿。飞行相机直接安装在悬臂上，用于校准贴片头拾取元件的位置偏移和角度偏差，其可在贴片头移动过程中同步完成检测，从而节省识别时间、提高组装效率，但飞行相机的识别范围和识别精度相对较低。 固定相机安装在贴片机内部，具有视野大、识别精度高的特点，适用于细间距和大型尺寸的元件。各类相机配合使用，可用于对各种尺寸的基准点和元件的检测识别，实现贴片机的高速高精度元件组装。
	\item[4)] \emph{计算机控制系统}：计算机控制系统记载着大量的贴片机数据参数，用于识别和处理设备及各传感器的信号，并根据预定程序控制贴片机的组装动作，控制系统内部的调度程序保证贴片机的高效运转、状态的实时监控和异常的快速处理等。
\end{enumerate}


以上系统共同协作，使得贴片机能够高效、精准地完成电子元件的组装任务。表面组装过程的流程如图\ref{ch1:figure:process}所示，具体地，其主要由以下步骤组成：

\begin{enumerate}
	\item[1)] \emph{PCB装载}：传送装置将PCB载入到预定位置，以基准相机校准其位置。
	\item[2)] \emph{工具匹配}：检查贴片头吸嘴和拾贴元件的一致性，不匹配则进行更换。
	\item[3)] \emph{元件拾取}：贴片头移动到供料器基座，从供料器中拾取元件。
	\item[4)] \emph{视觉检测}：检测已拾取元件是否存在缺陷，若是，执行步骤5；否则，校准元件的中心偏移后执行步骤6。
	\item[5)] \emph{元件废弃}：贴片头废弃有缺陷的元件在废料盒中，执行步骤7。
	\item[6)] \emph{元件贴装}：贴片头搬运检测通过的元件并将放置在PCB对应焊盘上。
	\item[7)] \emph{循环}：重复执行以上步骤2--6，直至所有焊盘均组装完成对应元件后，传出PCB。
\end{enumerate}
\vspace{0.2em}
\begin{figure}[htpb]
	\centering
	\includegraphics[scale=0.7]{chapter1/mount-process-flowchart.eps}
	\bicaption[ch1:figure:process]{}{表面组装过程流程图}{Fig.$\!$}{\centering Flowchart of surface assembly process}
\end{figure} 

% 表面组装过程优化问题解包含的环节及其同组装过程的联系

贴片机的表面组装过程由一系列复杂的工艺流程组成，本文将拾取、检测、贴装的一个周期性过程称为拾贴周期，将具有相同贴片头拾取槽位的连续拾贴周期称为周期组。
主流贴片机的元件废弃率普遍低于0.1\%，对整体组装效率的影响较小，故元件废弃过程通常不在优化的环节之内。
贴片头拾取的槽位决定了当前周期拾贴的元件类型和需要安装的吸嘴类型。
在组装过程中，贴片头的移动路径和组装动作共同决定了组装过程的效率。组装动作包括贴片头的元件拾取、吸嘴更换和元件贴装动作，元件贴装动作仅和贴装点数相关，而元件拾取和吸嘴更换动作则取决于对组装过程优化的结果。

表面组装过程优化涉及多个问题的决策优化。对于贴片机的组装过程，元件拾取和贴装动作、贴片头的吸嘴更换动作以及移动路径均会对组装时间产生影响。
其中，供料器安装的基座槽位决定了拾取过程的移动路径和能达到的最大拾取效率；
贴片头装配的吸嘴类型决定了可拾取的元件类型，其需要根据组装任务进行吸嘴更换以提高拾取效率；
贴片头的拾贴元件类型和供料器安装槽位共同决定了拾取次数，同时限制了各周期可贴装的焊盘位置，进而影响了贴装过程的路径规划。
多变量和高度耦合的决策过程增大了问题求解的难度。


表面组装生产线负载平衡问题，在贴片机组装过程优化的基础上，增加了贴片机之间元件分配的决策优化。表面组装生产线与传统生产线在元件分配层面既具相同性，又有差异性。相同之处在于，二者均涉及将元件分配至不同机器进行组装加工的决策，且允许多台机器协同装配同一类型元件，以提升整体的生产效率。同时，二者均需考虑装配的优先级要求，并可能因元件封装等限制而影响其可分配的机器。
差异性则主要体现在，组装生产线的负载均衡优化受到可用工具资源限制的影响大，不同类型元件因受限于供料器等专用工具，其可分配至贴片机的数量上限受到影响。
生产线元件分配的结果决定了贴片机的组装任务，更为关键的是，在评估贴片机的组装效率时，组装生产线的复杂性更为突出。
贴片机的组装时间还受到贴片机类型、可用工具、优化算法等多重因素的影响。由此可见，表面组装生产线的优化是一个多维度、高度集成的决策过程，必须综合考虑生产线各环节的协同工作，以实现整体效率的最大化。

\section{表面组装过程优化的研究现状}[Research review on surface assembly process optimization]

\subsection{贴片机的组装过程优化}[Assembly process optimization of surface mounters]

作为一类组合优化问题，数学规划和启发式优化是两类常用于解决贴片机的组装过程优化的方法。
其中，数学规划是用定量的数学表达式构建决策变量之间的目标和约束函数的方法，可以实现系统的解空间搜索，确保了优化结果的可靠性和准确性，而其在处理复杂优化问题时，运算效率受数据规模的影响大；
启发式优化则基于经验和直觉设计搜索规则快速寻找问题的较优解，具有适应性强、求解效率高和易于实现等特点，算法的性能取决于搜索策略的设计，复杂解空间增加了设计有效搜索规则的难度，同时可能会降低解的质量。
混合优化将复杂优化问题进行拆分，运用不同的方法分阶段地解决问题，旨在同时提高问题的求解效率和解的质量。图\ref{ch1:figure:opt-classification}展示了用于解决表面组装过程优化问题的主要方法分类。

\begin{figure}[htpb]
	\centering
	\includegraphics[scale=0.85]{chapter1/optimization-classification.eps}
	\bicaption[ch1:figure:opt-classification]{}{表面组装过程的主要优化方法分类}{Fig.$\!$}{\centering Classification of primary optimization methods for surface assembly process}
\end{figure}

\subsubsection{数学规划法}

% === 早期研究 ===
在早期的表面组装过程优化研究中，贴片机类型呈现出多样化的特点，相关研究以最小化悬臂的移动路径为目标，构建了不同类型的简化数学模型。
Ho等\cite{ho_integrated_2009}研究了单头顺序贴片机的建模问题，通过构建供料器位置分配和贴装顺序规划互为已知约束的双向模型，将两个模型整合为整数线性模型，获得了该类贴片机组装过程优化的最优解。
Altinkermer等\cite{altinkemer_optimization_2000}围绕转塔式贴片机的建模问题开展研究，其将表面组装问题归结为供料器分配和拾贴顺序决策问题，运用拉格朗日松弛定理分解数学模型到两个子问题，将组装路径优化问题转换为车辆路径规划问题（Vehicle Routing Problem，VRP），提出$\varepsilon$近似解的模型求解方法，将所得解与最优解的误差控制在了等效VRP的误差范围内。
Alkaya等\cite{alkaya_combining_2015}研究了供料器基座和电路板支撑平台可移动的转塔式贴片机的数学模型，通过将移动路径规划和供料器位置分配视为顺序相关的旅行商和二次分配问题，建立了非线性整数规划模型。
Luo等\cite{luo_milp_2014}研究了LED贴片机的贴装路径优化问题，将贴片位置的拾贴顺序问题视为具有城市批次的旅行商问题，构建了贴片头移动路径最小化的混合整数规划模型。

% === 模型分解及其子问题 ===
为应对日趋复杂的贴装任务，相关研究围绕并列式贴片机展开研究，其表面组装过程模型的构建更为困难，因而部分研究采取分解策略来进行建模。
Luo等\cite{luo_modelling_2014, luo_milp_2017}将问题分解并设计了两阶段混合整数线性规划模型：在第一阶段解决吸嘴-贴片头分配问题，在第二阶段通过优化供料器-槽位分配和元件贴装顺序最小化移动路径，适用于小规模数据的求解。
Ashayeri等\cite{ashayeri_planning_2007}提出了针对元件-贴片机分配和拾贴顺序规划的模型分解方法，从装配时间最小化和换线时间最小化两个角度，对组装过程的供料器分配和路径规划问题进行建模。 
Hsu等\cite{hsu_solving_2022}讨论了多机头贴片机吸嘴更换、拾取动作、移动路径等因素对组装效率的影响，以最小化组装时间为目标，构建了可同时解决元件顺序分配、供料器分配和吸嘴分配问题的混合整数线性规划模型。
此外，也有部分研究关注于组装过程子问题模型的构建。
Raduly-Baka等分别研究了吸嘴分配\cite{raduly-baka_selecting_2008}
和供料器模组分配\cite{raduly-baka_tool-feeder_2017}问题，前者讨论了有无成本限制的吸嘴选择问题，并以近似线性规划模型实现了在多项式时间内获得最优的吸嘴分配的解；
后者则研究了多类型电路板组装时，最小化准备供料器的换线时间优化问题，将其建模为工具分区模块分配模型。
Sun等\cite{sun_branch-and-price_2007}研究了贴装过程路径规划的整数规划模型，提出了具有高效剪枝策略的分支定价算法，运用了动态规划解决列生成中的子问题，使其在处理小规模数据时能高效地获得问题的最优解。

% === 求解技术 ===
数学规划法在解决复杂组合优化问题时有较高的计算复杂度，因而部分研究在构建模型的过程中应用了一系列技术降低问题的规模，进而提升模型的可解性。
Torabi等\cite{torabi_new_2013}将表面组装过程优化问题视为多目标优化问题，提出最小化周期和最大化吸嘴-元件适配度两个目标，建立最大最小化整数规划模型，并设计增广$\varepsilon$方法实现了对中小规模问题的求解。
Ashayeri等\cite{ashayeri_aggregated_2011}引入了批处理的方法，将单个贴片头组装的一批同类贴装点的元件类型作为决策变量，建立了决策变量数更少、模型复杂度更低的混合整数规划模型，能有效平衡贴片头工作量、减少吸嘴更换和提升悬臂移动速度，适用于元件类型有限而贴装点较多的数据优化。
Guo等\cite{geng_mcvrp-based_2019}将并列式贴片机的组装过程优化等价为多车厢车辆路径规划问题（Multi-Compartment Vehicle Routing Problem，MCVRP），通过将问题拆解为拾取组合和贴装排序问题，从提升拾取效率的角度出发，以不同类型元件构成同步拾取组，建立了相应的混合整数规划模型。

综上所述，现有研究对表面组装过程模型的模型构建展开了详细的分析，并取得了一定的进展，相关分类如表\ref{ch1:table:model-summay}所示。全过程的模型主要围绕简单类型贴片机的模型展开，而并列式贴片机的数学模型通常采用分阶段构建的方式，并有部分研究专门对其中的子问题进行建模。不同角度的构造式建模方式降低了模型的复杂度，但尚未完全解决模型求解效率受数据规模限制大的局限性。
\begin{table}[H]
	\centering
	\small
	\bicaption[ch1:table:model-summay]{}{主流研究中数学规划模型的构建方法}{Table $\!$}{\centering Construction method of mathematical programming model in mainstream research}
	\begin{tabular}{m{2cm}<{\centering}p{2cm}<{\centering}p{10cm}<{\centering}}
	\toprule
	类别 & \multicolumn{2}{c}{相关研究}  \\
	\midrule
	\multirow{3}{*}{全过程模型} & \multicolumn{2}{c}{双向约束整数线性规划\cite{ho_integrated_2009}} \\
	& \multicolumn{2}{c}{等效转换\cite{altinkemer_optimization_2000,luo_milp_2014}}	\\
	& \multicolumn{2}{c}{非线性整数规划\cite{alkaya_combining_2015}} \\
	\cmidrule(lr){1-3}

	\multirow{2}{*}{分阶段模型} & 两阶段： & 吸嘴分配-拾贴顺序\cite{luo_modelling_2014, luo_milp_2017}，供料器分配-拾贴路径规划\cite{ashayeri_planning_2007}  \\
	& 三阶段： & 元件顺序-供料器分配-吸嘴分配\cite{hsu_solving_2022} \\
	\cmidrule(lr){1-3}

	子问题模型 & \multicolumn{2}{c}{吸嘴分配\cite{raduly-baka_selecting_2008}
	，供料器模组分配\cite{raduly-baka_tool-feeder_2017}，贴装过程路径规划\cite{sun_branch-and-price_2007}} \\
	\cmidrule(lr){1-3}

	\multirow{3}{*}{构造式模型} & \multicolumn{2}{c}{多目标最大-最小整数规划\cite{torabi_new_2013}} \\
	& \multicolumn{2}{c}{元件组批处理整数规划\cite{ashayeri_aggregated_2011}} \\
	& \multicolumn{2}{c}{基于同步拾取组的MCVRP模型\cite{geng_mcvrp-based_2019}} \\
	\bottomrule
	\end{tabular}
\end{table}

\subsubsection{启发式优化方法}

% === 遗传算法 ===
多种元启发式优化技术已被成功运用在表面组装过程的优化领域，遗传算法作为其中最具代表性的优化方法，其编码方式是相关元启发式优化方法设计的基础，主要可分为以下几类：

1）\emph{子过程的一维顺序编码}

表面组装的子过程优化主要可分为供料器-槽位分配和元件贴装顺序优化两部分。
在供料器-槽位分配编码中，主要通过迭代不同的供料器排列顺序，确定元件的拾贴顺序。Sun等\cite{sun_component_2005}提出了贪心的供料器基座扫描策略，
以最大化同步取料的贴片头数作为评价编码结果的指标；
Xing等\cite{xing_high_speed_mounter_2018}提出了改进的单亲遗传算法，根据个体适应度大小，合理划分个体在子代出现的次数，减少种群迭代次数。
在元件贴装顺序编码中，Hardas等\cite{hardas_development_2008}以贴装路径和运算效率为比较指标，通过实验分析路径、顺序、邻接的基因表示形式，以及部分映射、有序交叉、交替边搜索算子对优化结果的影响；Peng等\cite{peng_gantry_2021}以贴片头移动距离最小为目标，通过分析不同取料方式下的贴装路径差异，优化了贴片头的取贴顺序和取料方向。

2）\emph{全过程的一维顺序编码}

全过程的顺序编码是对表面组装过程中多个子问题的同时编码，具有并行搜索的优势。
Kulak等\cite{kulak_pcb_2007}提出了供料器分配和贴装顺序相关的局部关联染色体编码方式，运用分布密度导向构建法对贴装点顺序进行分组聚类，有效地限制了问题规模、提升了搜索效率。
Gyorfi等\cite{gyorfi_efficient_2008}在供料器-贴装顺序编码的基础上，提出一种支持多贴片头的供料器拾取和元件贴装顺序相互独立的关联链接评估方法，研究在迭代过程中平衡父链接样本空间和搜索多样性的方法。
Wu等\cite{wu_improved_genetic_2014}设计了元件拾取序列、贴装序列、供料器排列序列的三链染色体，在同时优化贴装顺序和供料器分配槽位基础上，结合贪心解决元件拾取顺序问题。
Wu等\cite{wu_minimum_criterion_2020}提出适用于贴装顺序、拾取顺序、贴片头元件以及供料槽元件分配相结合的个体编码与解码方式，将最小准则原则运用在个体的筛选过程中，维持搜索过程的多样性。

3）\emph{全过程的二维实数编码}

二维实数的编码同时对分配顺序和分配类型进行编码，具有收敛速度快、输出结果稳定等优势。
在对元件贴装顺序和供料器安装槽位同时优化的相关研究中，
Du等\cite{du_hybrid_genetic_2014}将问题拆分为元件分组、元件组拾取和元件组贴装子问题，提出一种二维实数编码的混合遗传算法，设计了元件分组启发式算法；
Yin等\cite{yin_cell_genetic_2015}结合元胞自动机增强算法全局搜索能力，提出二维分段式编码方式。
此外，Li等\cite{li_cell_2022}从贴片头的元件分配出发，通过同类元件的贴装点组的拆分和重组，按元件组在贴片头上的分配顺序进行编码，以平衡拾贴周期、吸嘴更换、同步拾取等性能指标为目标，提出一种基于元胞分裂的贴片头元件分配算法，并设计启发式算法用于供料器的槽位分配。

基于上述的编码方式，在表面组装过程优化问题中，相关的元启发式算法也得到了广泛的研究和应用，主要可分为以下几类：

% === 进化算法 ===
1）\emph{进化搜索优化方法}

进化算法受自然选择和生物进化机制启发，通过不同的基因表达方式代表优化问题的解，适用于解决包括组装过程优化在内的复杂问题。
Tsuchiya等\cite{tsuchiya_scheduling_2007}为解决贴片头同步拾取优化问题，提出一种启发式多起点的局部搜索算法，对随机生成的供料器分配结果增加解的可行性、贴片头的工作效率和同步拾取可行性等判断，并采用拾取模式匹配确定了取料顺序。
Zhu等\cite{zhu_improved_2014}提出改进的混合蛙跳算法解决组装过程中的拾贴顺序优化问题，建立了针对整数编码的跃迁步进、二元步进以及适用于离散数据的跃迁运算符，结合个体记忆化搜索模式，运用方差分析法确定了算法的最优参数，使其收敛速度更快、精度更高。
Luo等\cite{luo_rls_2012}研究将禁忌搜索运用到贴装路径规划问题解决中，采用双禁忌表避免迂回搜索，根据问题特性设计了插入移动的参考解局部搜索策略，有利于算法跳出局部最优解。
Liu等\cite{liu_optimization_2017}提出分散搜索法分别解决表面组装过程中的元件-供料器、供料器-槽位和拾贴元件顺序子问题，通过最小化拾贴周期、构建同步拾取和优化元件拾贴顺序来减少组装时间。
Xu等\cite{xu_immune_2017}在免疫算法中运用了供料器槽位分配-贴片顺序编码方式，通过改进免疫算子以及调整参数，对多头贴片机的贴装过程进行优化求解，独特性免疫网络使得搜索群体呈现多样化的特点，有利于算法的全局优化。


% === 群体智能算法 ===

2）\emph{群体智能优化方法}

群体智能通过模拟社会性生物的群体行为进行优化，具有鲁棒性强、搜索速度快的优点，被广泛应用到表面组装过程优化中。
Castellani等\cite{castellani_printed_2019}将定制的蜂群算法用于解决供料器槽位分配和贴装顺序问题，提出了五种新的搜索算子，使算法不依赖于初始解且有较好的收敛性。
Hsu等\cite{hsu_printed_2020}提出了改进的多种群离散蜂群算法，同时优化元件取贴顺序和供料器分配槽位，在全局探索-开发策略的基础上，运用多蜂群以及自适应、离散移动步长等新特性，有助于算法找到问题的较优解。
Wang等\cite{wang_application_2019}提出基于自适应蜘蛛猴算法优化表面组装过程，通过分层次的算法结构与表面组装过程结合，实现了在全局领导者环节解决供料器槽位分配问题，并在局部领导者环节解决贴装顺序问题，提升了组装过程效率。
Fu等\cite{fu_modified_ant_2017}研究了转塔式贴片机的优化问题，将表面组装过程拆分为拾贴周期内和周期间规划的子问题，在改进的蚁群算法中引入精英蚂蚁，并采用全局和局部相结合的信息更新策略，具有全局搜索能力、较好的求解精度和较快的收敛速度。
基于此，Yu等\cite{yu_dual_gantry_2019}提出了基于拾贴周期内部路径优化和周期间路径的蚁群算法，对双悬臂双旋转头路径规划进行研究，克服传统算法中约束条件较多的局限性。
Hsu等研究了运用粒子群算法\cite{hsu_solving_2017}和改进的混合蛙跳算法\cite{hsu_optimization_2020}同时解决供料器槽位分配和元件拾贴顺序规划问题，其在粒子群算法中提出了离散问题向连续空间转化的编码机制，并引入了自适应跳跃、自适应变体等智能算子，通过迭代减少记忆体数量，实现了探索到开发的过渡，有助于算法搜索高质量解。
Griffiths等\cite{griffiths_comparison_2022}研究了新型离散混合蝙蝠启发算法，重新定义了搜索过程的位置和速度等参数，用于解决六轴机械臂组装元件规划时的供料器槽位分配和拾贴顺序规划问题。
Lu等\cite{lu_cell_bat_2017}研究了复合式双悬臂转塔式贴片机的优化过程，根据种群的交流结构和信息传递机制，将元胞自动机理论融入蝙蝠算法中，引入多交叉算子自适应的策略提升鲁棒性，设置精英归档提高迭代速度和种群位置多样性，提出迭代互换操作来执行局部搜索，以提高算法的收敛精度。


% === 多目标优化 ===
3）\emph{多目标启发式优化方法}

多目标优化也被应用到具有多个效率相关子目标的表面组装过程优化问题中，且常与元启发式算法结合解决问题\cite{meng_application_2023}。
Torabi等\cite{torabi_new_2013}将表面组装过程的优化目标拆分为最小化瓶颈贴片头负载和最大化元件-吸嘴匹配度两部分，以Taguchi方法调整了算法参数，研究了优化贴装过程的粒子群算法。
Zhu等\cite{zhu_multi-objective_2018}将表面组装优化任务视为最小化元件贴装移动路径、供料器拾取移动路径和吸嘴更换的多目标优化问题，通过最佳参考点和比较点之间的关系，提出了一种基于Fr{\'e}chet距离曲线匹配的组装过程多目标优化遗传算法。
Lu等\cite{lu_grey_entropy_2013}基于灰熵关联分析建立表面组装中拾取顺序、贴装顺序和吸嘴更换顺序子目标相关的灰熵关联度函数，提出的多目标差分算法保证至少两个子目标优于传统遗传算法，且解集分布更均匀。
Gao等\cite{gao_hierarchical_2021}运用分层序列法，分析影响组装效率的子目标之间的耦合关系，根据优化子目标将问题拆分为了吸嘴分配、元件分配、供料器分配和拾贴顺序规划问题，提出了分层次启发式的表面组装过程优化方法。

4）\emph{其他启发式优化方法}

% 启发式算法 - 子问题
构造启发式等优化方法也被应用到了表面组装过程子问题的优化中。
吸嘴分配限制了贴片头可分配的元件类型，影响了表面组装过程的拾取次数和吸嘴更换次数。
Knuutila等\cite{knuutila_minimizing_2007}研究了拾取次数最小化的吸嘴分配问题，在给定吸嘴拾贴顺序的前提下，贪心的吸嘴分配策略在单次拾取中尽可能多地拾取元件以提升效率。
Raduly-Baka等\cite{raduly-baka_selecting_2008}研究了贴片头的吸嘴类型的选取问题，讨论了在可用贴片头数量限制下的吸嘴分配问题，而后提出了在增加吸嘴预算限制下的最优吸嘴分配的高效的贪心搜索算法。
在此基础上，Knuutila等\cite{knuutila_organizing_2013}研究了以最小化拾贴次数为优化目标的吸嘴配置问题，分别运用遗传算法和粒子群算法启发式方法对吸嘴库配置进行了优化，并在求解小规模问题实例时取得了接近最优的结果。
Py{\"o}tti{\"a}l{\"a}等\cite{pyottiala_minimizing_2013}研究了以多近邻搜索解决供料器位置分配问题，并同随机分配、最小生成树、基于频次的平衡算法进行比较，提出了基于随机/周期空闲优先启发式、随机/周期下一空闲启发式规则的算法对拾取贴装路径进行优化。
Han等\cite{han_mechanism_2017}研究了一种供料器分配算法，该算法以基座最左侧槽位为起点，贪心地将距离当前贴装点最近的元件分配到槽位，并不断更新基准点进行连续分配，通过自定义距离函数进行全局优化。
Chen等\cite{chen_ant_frog_2011}研究了供料器分配已知的元件拾贴顺序优化，通过混合蛙跳-蚁群算法对贴装顺序进行路径寻优，提出了适用于贴装过程的分段启发函数、信息素分段编码和更新等改进方法，有效地提升了算法的求解精度和全局搜索能力。
Li等\cite{li_heuristic_2022}将贴装路径问题和供料器分配问题被转化为启发式排序优化问题，以索引序列对的能量矩阵优化拾贴周期序列，提出了基于Hopfield神经网络的路径相关序列优化方法。
% Ayob等\cite{ayob_real-time_2003}研究了表面组装过程的在线优化算法，通过快速确定PCB加工任务的可行解，在生产过程中拾贴路径规划解进行在线迭代优化，不断改进解的质量。
Wang等\cite{wang_enhancing_2024}运用发明问题解决（Theory of Inventive Problem Solving，TIPS）理论，研究了表面组装中时间延迟、元件供料、拾取和贴装过程之间的协同优化问题，提出一种基于蚁群优化算法的仿真精简装配路径策略，减少装配时间的同时保持组装过程的高精度和低能耗。

\subsubsection{混合优化}

混合优化算法是指将多种不同的优化方法和策略进行组合，用来解决复杂优化问题的算法。
其中，将进化算法常与构造启发算法相结合的混合优化方法，可以明显提高优化的效果，适用于多模态、高维、带约束和多目标的优化问题，在工业界有着广泛的应用\cite{slowik_hybrid_2022}。

1）\emph{两阶段混合优化}

两阶段优化法通常从拾贴-贴装的角度对表面组装过程优化问题进行拆分，并以不同的策略分别求解。
Grunow等\cite{grunow_operations_2004}通过改进最小生成树并结合贪心法分配供料器至槽位中，将贴装顺序问题视为VRP通过改进Clarke-Wright节约里程法进行求解，并结合了局部搜索规则改进供料器分配和拾贴顺序规划结果。
Park等\cite{park_dynamic_2007}采用动态规划法分别解决供料器分配和贴装顺序规划问题，通过启发式算法从贴片头元件分配结果中构造供料器组合，确定了供料器的安装槽位和拾贴路径，以2-opt交换拾贴周期间的已分配贴装点，从而改进解的质量。
Chen等\cite{chen_component_2011}研究了供料器分配和贴装顺序规划子问题的独立性和关联性，采用分治法在两个问题中分别运用改进的蛙跳算法和禁忌搜索算法，通过二者迭代优化改进搜索解的质量。
Gao等\cite{gao_iterated_2018}提出了一种结合局部搜索和整数规划模型的混合优化算法，通过引入自定义距离权重矩阵并采用贪心法确定了拾贴顺序的初始解，研究了凸包调整策略优化拾贴顺序和整数规划模型求解供料器分配问题。
此外，部分研究在两阶段优化中将元件对应多类吸嘴的情形作为优化的环节进行了讨论。
Huang等\cite{huang_applied_2020}提出了最小化吸嘴-元件适配度和吸嘴更换次数的整数规划模型解决吸嘴分配问题，结合了混合蛙跳算法同时对贴装顺序、供料器分配、拾取顺序进行优化。
Hsu等\cite{hsu_solving_2022}提出了改进的萤火虫算法与动态规划结合的优化算法，采用秩序值技术进行整数编码和自适应搜索，同时优化了供料器安装槽位和拾贴顺序，最后运用动态规划解决了元件-吸嘴适配度最小化的吸嘴分配问题。


2）\emph{多阶段混合优化}

更多的研究致力于将表面组装过程的优化问题进一步拆分，分阶段地解决一系列更小的子问题。
其中代表性的工作为Lee等\cite{lee_dynamic_1998, lee_hierarchical_1999}提出的分层启发式优化算法，其通过平衡各贴片头的工作负载并从中提取供料器组合，以启发式动态规划的方法确定供料器组的最优安装槽位，运用启发式的吸嘴对排序算法和元件组构造算法确定贴片头分配任务，最后采用最近邻算法求解贴装过程路径规划问题，给出了一套完整的解决方案。
类似地，多阶段的混合优化算法被广泛应用于并列式贴片机的组装过程优化。
Xing等\cite{xing_online_2017}在平衡贴片头负载的基础上，运用启发式的选择策略为贴片头分配吸嘴，减少拾取过程中的吸嘴更换和元件拾取次数，在贴装过程中则以最近邻算法确定周期间和周期内的元件贴装顺序。
Luo等\cite{luo_milp_2017}将优化问题拆分为吸嘴-贴片头、元件-贴片头、供料器-槽位、拾取顺序和贴装顺序五个相互关联的子问题，研究了最小化周期的构造启发式算法确定贴片头分配的吸嘴类型，将带有两个算子的进化算法和多邻域禁忌搜索结合，同时解决元件分配、供料器分配和拾贴顺序等问题。
Guo等\cite{guo_pcb_2011, geng_mcvrp-based_2019}将组装优化过程拆分为吸嘴分配、元件拾取组生成、元件拾取组拆分-合并和贴装顺序规划四个子问题，研究了单一类型元件对应多类吸嘴的编码方式，以贪心启发式分配吸嘴至贴片头，并为元件的同步拾取构造了拾取组，进而提出了基于拾取组拆分-重组的改进混合遗传算法和贪心启发式的路径规划算法。

部分研究在同步拾取研究的基础上，进一步考虑了实际应用中约束条件对组装过程的限制。
Lin等\cite{lin_modified_2017, lin_component_2021}将组装过程分解为吸嘴-ANC分配、贴片头-吸嘴分配和元件拾贴顺序规划问题，其在ANC分配阶段采用比例分配法确定了最优的吸嘴-ANC分配结果。基于给定的ANC配置，在拾贴拾取、元件高度等约束下，Lin等分别提出了基于人工蜂群\cite{lin_modified_2017}和混合优化\cite{lin_component_2021}的方法解决其余子问题：前者以改进人工蜂群算法先同时解决吸嘴分配和拾取顺序问题，再解决贴装顺序问题；后者则以轮盘赌解决吸嘴分配和拾取顺序问题，再运用最近邻与2-opt结合优化贴装顺序。
更进一步地，Lin等\cite{lin_efficient_2019}研究了群搜索优化在组装过程优化中的应用，提出了改进群搜索与随机整数规划结合的方法，通过融入混沌局部搜索策略，消除了种群相似个体中的不良解，增强了搜索效率与解的多样性，优化了元件的拾取顺序。


迭代式的多阶段混合优化在表面组装过程优化中也得到了应用。
Li等\cite{li_pcb_2017}将组装过程拆分为了吸嘴分配、供料器分配和拾贴顺序规划问题，采用启发式确定吸嘴分配和供料器分配的初始解，以自适应最近邻搜索优化拾贴顺序，并结合受限的禁忌搜索算法搜索供料器分配的邻域解，迭代改进其他子问题的解。根据贴装点的分布特性，Li等\cite{li_clustering-based_2019}提出了均值Chebyshev联动定向搜索算法，以自适应聚类启发式的贴装点分组策略优化吸嘴和供料器分配，通过受限的禁忌搜索迭代改进供料器分配和拾贴顺序。

多阶段混合优化同样被运用到了双悬臂贴片机的组装过程优化中。
He等\cite{he_multi-phase_2017}在吸嘴准备、供料器分配和拾贴顺序分解的基础上增加了负载平衡和周期规划的研究，其在双臂吸嘴准备阶段运用分段交换算法，基于此，提出了分层受限的平衡算法解决元件分配问题，并以爬山算法优化供料器槽位分配和拾贴顺序，在悬臂周期规划阶段则采用受限的邻域搜索算法。为解决双悬臂的吸嘴准备问题，He等\cite{he_adaptive_2018}提出了基于不确定参数搜索启发式的线性模型分支定界优化方法，研究了具有单臂吸嘴配置、供料器配置和拾贴顺序编码的自适应聚类遗传算法，用于规划双臂拾贴周期和元件分配结果，缩小了问题的搜索空间、提高了算法的搜索效率。


\subsection{生产线的负载平衡优化}[Workload balancing optimization of assembly lines]

%% === 概述 ===
表面组装过程优化是表面组装生产线负载平衡的基础，组装线优化可分为单模态、混合模态和多模态生产线模式\cite{toth_machine_2018}。其中，单模态和混合模态生产分别是在固定配置下组装单一类型和多种类型电路板的生产模式，多模态生产则是具有生产线配置切换的多种类型电路板的生产模式。平衡不同机器之间的工作负载可以有效缩短组装线上贴片机的最长处理时间，提升整线装配效率。生产线任务分配包含元件分配和组装顺序优化两个子问题，前者指元件的贴片机分配优化，后者指贴片机的组装过程规划。图\ref{ch1:figure:line-classification}演示了表面组装过程优化的研究路线。

\begin{figure}[htbp]
	\centering
	\includegraphics[scale=0.75]{chapter1/research-route.eps}
	\bicaption[ch1:figure:line-classification]{}{表面组装过程优化问题的研究路线}{Fig.$\!$}{Research route of surface assembly process optimization problem}
\end{figure} 

\subsubsection{生产线负载平衡}

1）\emph{数学规划法}

%% === 数学规划 ===
对于单贴片头和转塔式贴片机组成的生产线，相关研究\cite{kodek_optimal_2004,emet_workload_2010,rong_modeling_2011,jin_printed_board_2008}假定贴装点数和组装用时为线性关系，建立了组装生产线整数规划模型，实现了在可接受的时间内最优地解决元件分配问题。
Kodek等\cite{kodek_optimal_2004}提出了最小-最大近似整数规划模型，以产线配置用时和不同元件的拾贴用时之和作为模型的优化目标，提出了一种高效的分支定界搜索策略，使其适用于变量数中等规模的问题求解，并给出大规模数据的近似最优解和理论下界值。
基于此，Emet等\cite{emet_workload_2010}对模型做了进一步改进，根据贴片机的作业过程，增加了供料器模块、拾贴优先级和元件可重复分配等约束条件。 
Rong等\cite{rong_modeling_2011}研究了模组贴片机的贴片头配置和组装生产线的负载平衡问题，建立了非线性数学模型，研究了模型的线性化与松弛化方法以加快搜索速度，适用于中小规模问题的求解。
Jin等\cite{jin_printed_board_2008}研究了高速贴片机和多功能贴片机组成的生产线的优化，在满足异型元件分配给多功能贴片机、细间距元件分配给高速贴片机的约束条件下，以悬臂的移动路径为工作负载的评价指标，分配元件到各模组贴片机的工作台，使工作负载和吸嘴更换次数最小。

2）\emph{启发式优化方法}

%% === 元启发式 ===
元启发式算法常用于表面组装生产线的优化，以解决贴片机共同组装单一类型电路板的优化问题。
Kulak等\cite{kulak_ga-based_2008}将组装线优化问题拆分为贴片头元件分配、供料器槽位分配、拾贴顺序优化三个子问题，提出了基于遗传算法的两阶段生产线负载平衡算法，
在第一阶段平衡贴片机的工作负载并提供多个高质量的候选解，在第二阶段则对候选解进一步执行贴片机的组装过程优化算法，确定供料器的安装槽位和元件的拾贴顺序。
Wu等\cite{wu_solution_2010}将元启发元件分配算法和线性回归时间估计模型相结合，建立了贴装点数、贴装点间距、元件类型数等数据参数和组装时间的关系模型，以此为适应度函数并将元件分配作为遗传算法的染色体编码方式，利用贴装点分布的聚类特性，获得高质量的解决方案。
Guo等\cite{guo_integrated_2012}研究了适用于同类型元件可分配多贴片机的混合遗传算法，以贴装点数、拾贴周期数和吸嘴更换数线性拟合组装时间，迭代式地解决元件分配、吸嘴组分配和贴片头分配三个子问题，将元件分配转换为多元件的弱分组问题进行编码，设计了选择式和非选择式的初始化和交叉策略，用贪心启发式解决吸嘴组分配和贴片头分配问题。
Liu等\cite{liu_surface_assembly_2013}研究了分散搜索法解决生产线负荷平衡，以统计数据评估各类元件的贴装时间，将元件分配的贴片机进行编码构建初始解集，运用2-opt改良初始解、修复不可行解，从可行解中选择若干最好解用于参考解集的合并和更新，保持了搜索过程中解的多样性，避免过早收敛以提升生产线的组装效率。
Mumtaz等\cite{mumtaz_hybrid_2020, zhong_multi-objective_2022}将提出离散化的混合蜘蛛猴算法用于同时解决组装线中的元件分配问题和单机拾贴顺序问题，其中，元件分配用于平衡贴片机的工作负载，算法设计中融入了新的分类食物来源和基因操作算子，较传统智能优化算法提升了求解效率和解的质量。
Chen等\cite{chen_improved_2023}在生产线的元件分配和贴片机的拾贴顺序基础上增加了周期性维护的考虑，以同时优化最大完工时间、总能量消耗和总维护时间，并将改进的蜘蛛猴算法作为基本框架，设计启发式算子生成初始解，根据Pareto熵变化的演化状态平衡搜索过程中探索和开发，提出了基于存档的Q学习策略自适应调整参数，实现了优化子目标的Pareto最优。
Yan等\cite{yan_load_2023}提出了结合自适应遗传算法与改进蚁群的混合优化算法，利用其全局搜索与快速收敛的优势，在过程中动态调整交叉和变异算子，以解决组装线负载平衡问题。

构造启发式也被应用于解决表面组装生产线优化问题。
T\'{o}th等\cite{toth_reconfiguring_2010}研究了模块化贴片机的配置和生产线的负载平衡问题，将组线问题拆分为模块-贴片头分配、贴片头-吸嘴分配和元件-供料器分配三个子问题，设计了定制启发式解决各子问题，研究了暴力搜索、随机搜索、贪心搜索和启发式算法在求解组装线优化问题中的实际效果。
He等\cite{he_heuristic_2017}提出了确定性分层启发式分阶段地解决组装线生产优化中的子问题，在吸嘴分配阶段以最小化周期为目标按比例将同类型元件分配给贴片机，在元件分配阶段则以最小化供料器数为目标平衡贴片机负载，以贪心算法迭代解决供料器安装槽位和拾贴顺序规划问题。
Choudhury等\cite{choudhury_process_2007}研究了双悬臂贴片机组装线的优化问题，通过将决策过程拆分供料器槽位分配、元件拾取组合、元件贴装分配和拾贴顺序规划四个相关的子问题，采用列表处理启发式分配元件的供料器和贴片头，将拾贴顺序规划问题转换为非对称旅行商问题，在考虑贴片头的吸嘴更换前提下，提出一种贪心启发式规划近似最优的拾贴路径。

3）\emph{其他优化方法}

% === 其它角度 ===
部分研究将随机优化、模糊优化、多目标优化等新理论运用到表面组装生产线及生产车间的优化中。
Lin等\cite{lin_component_1999}研究了表面组装生产线的混合模态优化，将组装生产线优化问题转换为元件分组问题，为应对组装过程的订单更变和机器故障等不确定性因素，以最小化组装全部电路板的用时为目标，建立了随机混合整数规划，平衡解的最优性和环境的不确定性。
Hu等\cite{hu_fuzzy_2017}将组装生产线优化转换为分配问题和传输问题模型，提出了基于非线性隶属度函数的模糊目标规划模型，分析了模糊、不精确和不确定的环境中目标或约束条件可能出现偏差，同时优化组装线生产成本、故障次数和操作时间等多个目标，通过调整区间目标值的上下界给出最优的折中方案。
Zhang等\cite{zhang_reinforcement_2024}研究了不确定需求下提升生产线效率和鲁棒性的优化方法，设计了基于强化学习的多目标进化算法，通过基于解决方案优先级的编码方式和新的任务-人工-序列的解码方式，提出了适用于鲁棒性处理和空闲时间减少处理的交叉和突变算子，运用基于Q学习和时间概率的自适应策略协调迭代过程中的算子，从而有效地获得Pareto解决方案集。
Wang等\cite{wang_discrete_2022}研究了拆装生产线的负载平衡问题，以最大限度地提高工人的效率、增加利润、降低能耗和平衡工人的负荷为目标，开发了一种离散多目标人工蜂群算法，综合考虑了优先级等约束和拆装过程的特性，获得了Pareto最优的解决方案。
Zhang等\cite{zhang_multiobjective_2021}提出了一种基于直觉模糊集相似度的电路板组装车间的调度优化算法，通过聚合作业完成时间、总延迟成本、投资仓储成本和电力消耗等多个优化子目标映射至直觉模糊相似集，集合适应度函数分配策略和最优觅食算法，设计了改进的表面组装多目标进化算法。

\subsubsection{多层次生产规划}
% === 非单一订单 ===
多品种小批量的表面组装生产线负载平衡是典型的多模态组装线优化问题，相关研究主要围绕生产线的配置切换和负载平衡展开。 
Jin等\cite{jin_changeover_2011}建立了包含切换时间在内的最小化组装时间的表面组装生产线调度优化模型，提出针对电路板组装特有的切换后效性的主动禁忌搜索算法，研究了组间搜索和组内搜索的分层排序优化策略，并与理论下界值比较说明了算法的有效性。
Liu等\cite{liu_hmlv_2012}研究了两条生产线的多品种小批量生产线优化问题，以最小化生产线的最大流程时间为目标，根据相同品种子集的相对相似系数进行分组，采用主动禁忌搜索算法对电路板进行排序，并利用预置即需工具（Keep Tool Needed Soonest，KTNS）策略切换供料器的配置，实现柔性生产线的负载均衡优化。
Guo等\cite{guo_nozzle_change_2016}研究了吸嘴切换和供料车在组线生产线优化中带来的瓶颈问题，设计了混合遗传算法优化多品种小批量订单的总完工时间，以遗传算法解决电路板的分组问题，提出改进的解决席位公平分配问题的增量算法进行组内分配，并采用改进的KTNS算法进行元件排序使切换次数最小。


% === 关于多条产线的整线优化 ===
表面组装线优化也可作为多层次生产规划的一部分，包括电路板-生产线分配、元件-贴片机分配和贴片机拾贴顺序优化等多个环节。
T\'{o}th等\cite{toth_machine_2018}研究了固定贴片机配置下多种不同批次类型电路板的整线优化问题，提出了一种迭代式的两阶段优化算法，将进化算法与整数规划结合，运用遗传算法解决生产线的重配置问题，并以整数规划模型优化整线负载平衡。
更进一步，T\'{o}th等\cite{toth_divide_2022}研究了整线贴装多种电路板的多模态负载均衡问题，提出了基于图论的电路板拆分组合启发式算法，将多种电路板组装问题拆分为独立的生产问题、并配置模块的公共子配置，有效地缩减了问题的规模。
Mumtaz等\cite{mumtaz_multi-level_2019}将多模态组线优化问题转换为生产线-电路板分配、元件-贴片机分配和贴片机元件拾贴顺序三个子问题，在预定交期和不同的产线容量条件下，提出了混合蜘蛛猴算法来同时解决多层次规划问题。
Koskinen等\cite{koskinen_rolling_2019}研究了分层启发式解决作业分区、选择、分组、负载平衡和调度问题，以最小化多周期生产计划中工作的总延误时间为目标，提出了包括生产线任务分配初始化和生产计划步骤改进的两阶段启发式，用以优化多条组装线下的多种类型电路板的滚动水平生产计划。
Pan等\cite{pan_knowledge_2022}研究了分布式并行的生产规划问题，以最小化总能耗和总延时为目标，提出了基于知识的双种群优化算法，通过分析问题特性，在种群初始化中使用了两种基于特定问题知识的启发式算法和一种随机启发式算法，运用非有序排序遗传算法和差分进化算法在种群上并行执行，以基于知识的局部搜索算子迭代，提升了机器的利用率。
Chen等\cite{chen_optimal_2024}分层设计分别对生产线配置、贴片机分配和元件分配进行优化，提出了进化算法和数学规划结合的数学启发式算法，在进化算法迭代过程中以数学模型评价个体的性能指标，确定了生产线中贴装机类型的最优配置。


\subsubsection{组装过程时间估计}

% 表面组装生产时间估计

组装时间估计是表面组装生产线中优化元件分配、实现贴片机工作负载均衡的重要依据。组装过程的时间受贴片机类型、优化算法及生产数据特性的影响。相关研究通常采用（线性）拟合的方法进行时间估计。
Wu等\cite{wu_solution_2010}以元件类型数、贴装点数、覆盖全部贴装点的最小区域面积及其乘积项的平方根为拟合项的线性回归估计组装时间。
Vainio等\cite{vainio_estimating_2015}分别研究了基于制造商参数和回归模型的组装时间估计方法，前者采用最近邻启发式快速优化组装过程，以给定参数模拟组装过程估计组装时间，后者则以元件类型、吸嘴类型及其数量等参数构成特征集，在训练阶段通过贪心的特征选择算法，通过正则化最小二乘回归对组装时间快速估计。
进一步地，Vainio等\cite{vainio_estimating_2010}研究了不同类型贴片机的非线性拟合方法，以元件类型数、贴装点数、电路板尺寸、元件形状及其周围的最小矩形面积等为训练特征，提出了基于多层感知器网络的组装时间估计器，采用交叉验证和Bayesian正则化等技术避免模型的过拟合，提高准确度。
监督学习具有较强的非线性拟合能力，在时间估计中有更高的准确度。
Li等\cite{li_predicting_2020}提出了基于共生生物搜索的支持向量回归组装时间估计方法，分析了装配过程中反映电路板和组装线生产时间不确定性的特征，通过特征选择、正则化编码、数据缩放和异常值去除等技术，结合集成学习等技术对组装时间进行估计。
Chen等\cite{chen_optimised_2024}将学习算法与启发式算法相结合，以随机森林算法预处理数据的特征，结合了电路板特征、操作员习惯和程序设置等，以差分进化算法为基础，提出了基于决策树的改进轻量级梯度提升机算法，用于估计表面组装的生产准备时间。
 


\section{现有研究存在的问题}[Problems of current research]

表面组装过程优化任务，作为一类典型的非确定性多项式（Non-deterministic Polynomial，NP）难组合优化问题\cite{ji_genetic_2001}，直接对其整体进行求解的算法搜索效率低下，且容易陷入局部最优解。
现有的主流研究将贴片机的表面组装过程优化分解为供料器槽位分配问题和元件贴装顺序问题。前者可以被视为二次分配问题，后者则可被转换为路径规划问题。
对于更高层次的表面组装生产线优化问题，已有研究对负载平衡算法展开了初步的讨论与分析。然而，由于该问题解空间庞大，加之准确获取贴片机的组装时间困难，制约了生产线效率的进一步提升。
目前关于表面组装过程优化方法的研究尚存在诸多问题，主要有：

1）\emph{组装过程数学模型的目标和约束不完备、或不具备可解性}

% 约束、目标不完备
% 模型非线性或不可解
% 过高的复杂度，工程实践不可部署

相关研究已经探讨了表面组装过程数学模型的构建策略。然而，目前已有研究中构建的模型普遍存在优化目标不全面、约束条件不完备或模型自身非线性不可解等问题。影响并列式贴片机组装效率的因素较多，在相关研究中，文献\inlinecite{ho_integrated_2009, altinkemer_optimization_2000}在构建模型时，仅将贴片头的移动路径长度作为评价指标，却忽视了拾取动作、吸嘴更换动作等关键因素对组装效率产生的影响。文献\inlinecite{ashayeri_aggregated_2011,geng_mcvrp-based_2019,torabi_new_2013}分别从拾贴周期规划、吸嘴更换策略以及同步拾取机制等角度对模型构建进行了讨论。其中，文献\inlinecite{torabi_new_2013}以周期数和悬臂移动速度为优化目标；文献\inlinecite{ashayeri_aggregated_2011}进一步优化了周期数、悬臂移动速度和吸嘴更换次数；文献\inlinecite{geng_mcvrp-based_2019}通过构建同时拾取组，规避了吸嘴更换动作。
上述研究中对组装效率影响因素考虑仍不全面，导致大幅降低了模型解的组装效率。
文献\inlinecite{hsu_solving_2022,altinkemer_optimization_2000,li_cell_2022, gao_hierarchical_2021}虽然为表面组装全过程模型建立了相对完备的约束条件和优化目标，适用于描述复杂问题和验证解的可行性，但模型本身的非线性特性却使其无法直接求解，也无法根据模型的解来定量分析启发式算法的效果。文献\inlinecite{luo_milp_2017, sun_branch-and-price_2007}讨论了贴装过程的路径规划建模，但由于模型复杂度过高，其适用范围仅限于极小规模的数据，在工程中难以部署和应用。此外，部分研究仅针对特定应用场景\inlinecite{luo_milp_2014}或其中的子问题\inlinecite{raduly-baka_selecting_2008,raduly-baka_tool-feeder_2017,luo_milp_2017,sun_branch-and-price_2007}进行了模型构建，缺少了从整体上对组装过程效率指标进行优化的综合考量。

2）\emph{贴片机组装过程优化解的生产效率不高、适用场景有限}

% 元启发式输出不稳定
% 优化目标和约束研究不充分
% 不满足供料器已分配等多样性优化要求

表面组装过程的优化任务，因其多模态、高维度和复杂约束的特性，促使当前主流研究普遍倾向于采用启发式作为算法设计的主体框架。
文献\inlinecite{geng_mcvrp-based_2019, li_cell_2022,hsu_solving_2017,hsu_optimization_2020,liu_optimization_2017,zhu_improved_2014,wang_application_2019,wu_minimum_criterion_2020,huang_applied_2020}均是在元启发式框架下，对表面组装过程优化进行了研究。
元启发式算法在处理大规模组装优化任务时，其收敛速度可能会因问题规模的增大而减缓，进而影响了优化解的质量。
算法中的随机搜索策略虽然有助于拓宽搜索范围、增强算法的适应性，但同时也带来了优化结果的不确定性，易使结果陷入局部最优解，从而降低了组装效率。
在并列式贴片机组装过程的优化研究中，当前研究通常关注于优化目标和约束条件的某个或某些方面，而对于整个组装过程中关键优化目标的综合分析并不全面。
特别是在决定组装效率的关键因素——同步元件拾取方面，仅有文献\inlinecite{tsuchiya_scheduling_2007, geng_mcvrp-based_2019, guo_pcb_2011, gao_hierarchical_2021, lin_modified_2017,sun_component_2005,li_cell_2022}对此进行了研究。
同步拾取动作受到贴片头上所安装吸嘴类型的限制，为实现同步拾取而更换吸嘴，或为满足元件与吸嘴类型的兼容而进行多次拾取，均会直接导致组装效率的降低。
上述研究中，
文献\inlinecite{geng_mcvrp-based_2019, lin_modified_2017}未对影响效率的供料器分配槽位予以讨论；
文献\inlinecite{sun_component_2005}采用的贪心同步拾取策略会增加吸嘴更换的次数；
文献\inlinecite{li_cell_2022}以最小化拾贴周期数为主要优化目标，在处理包含较多类型元件的优化问题时，会导致频繁的吸嘴更换，进而降低整体效率；
文献\inlinecite{guo_pcb_2011, geng_mcvrp-based_2019}在设计同时拾取组时禁止了吸嘴更换动作，限制了组装效率解的质量；
文献\inlinecite{tsuchiya_scheduling_2007}在构造同步拾取供料器分配时，未充分考虑元件对应的吸嘴类型，导致实际组装效率下降。
相关研究中，文献\inlinecite{gao_hierarchical_2021}在算法设计过程中较为全面地讨论了约束条件和优化目标，但其对贴片头上分配的元件、拾取的槽位以及吸嘴类型排列顺序的研究仍显不足，限制了算法效率的进一步提升。


在表面组装过程优化搜索解的过程中，机械约束与工具约束等限制了解的可行性。
其中，机械约束包括各贴片头存在物理上无法到达的拾取槽位，
为解决此问题，文献\inlinecite{geng_mcvrp-based_2019}与文献\inlinecite{sun_component_2005}分别采用了构造同步拾取组与贪心扫描算法的策略；
而在文献\inlinecite{tsuchiya_scheduling_2007,gao_hierarchical_2021}等关于供料器位置分配的研究中，若贴片头无法达到所分配的槽位拾取元件，则必须调整其拾取的槽位或所用贴片头，均会降低组装效率。
在工具约束层面，文献\inlinecite{lee_hierarchical_1999}假定各类元件仅有1个供料器，且供料器仅能由指定贴片头拾取元件，限制了组装效率的提升。
此外，不同型号的供料器被设计用于供应不同尺寸的元件，文献\inlinecite{lee_hierarchical_1999,geng_mcvrp-based_2019}中供料器仅占用一个槽位的设定，无法满足大尺寸元件的拾贴作业需求。
文献\inlinecite{gao_hierarchical_2021, li_cell_2022}中提出的算法需要对供料器的安装槽位重新进行分配，在小批量多品种、且供料器更换频率较低的生产场景下，增加了生产准备的时间成本。
对于可用吸嘴工具的约束，文献\inlinecite{guo_pcb_2011,guo_nozzle_2011,guo_integrated_2012, geng_mcvrp-based_2019}的研究中不进行吸嘴更换的设定，使其在处理吸嘴类型较多的组装数据优化时，可能导致所得解的不合理甚至无解的情况出现。文献\inlinecite{huang_applied_2020, ashayeri_aggregated_2011}将元件与吸嘴的匹配问题转化为代价函数进行优化，由于在实际组装过程中，不合理的贴片头吸嘴配置对拾取稳定性和贴装准确性均会产生不利影响，因此其所得解的无法保证可部署到实际的生产环境中。

3）\emph{生产线的组装用时评估不准确、负载分配不平衡导致组装效率低}

% 整线优化解决方案不完整
% 元件可重复等特性研究较少
% 组装时间估计不准确


为提高电路板组装流程的效率，制造商通常以多台贴片机构成的表面组装生产线来执行组装作业，此过程中涉及到生产线的负载平衡问题。
表面组装生产线的负载平衡优化需要综合考虑供料器配置、吸嘴分配、以及元件分配等多个子问题，以提供更全面的组装生产线优化解决方案。多层次的决策规划和子问题之间的相互耦合等多方面因素的共同作用导致现有优化算法对组装效率的提升有限。
表面组装生产线优化研究中，元件分配作为核心任务，其负载平衡算法已成为主流研究的重点。
文献\inlinecite{kodek_optimal_2004,emet_workload_2010,rong_modeling_2011}研究了数学规划法解决中小规模数据的元件分配策略，文献 \inlinecite{toth_reconfiguring_2010,he_heuristic_2017,kulak_ga-based_2008,mumtaz_hybrid_2020,guo_integrated_2012,chen_improved_2023,mumtaz_hybrid_2020}则研究了基于启发式的元件分配算法，以满足更大规模数据的优化需求。
组装生产线优化还需解决同类元件在多台贴片机间的分配问题以及可用工具的约束条件。
文献\inlinecite{kulak_ga-based_2008}等限制各类元件仅能分配至单一贴片机，未能充分利用元件的可重复分配性以提升组装效率；文献\inlinecite{emet_workload_2010, rong_modeling_2011, he_heuristic_2017,mumtaz_hybrid_2020,guo_integrated_2012}研究了将同类元件分配至不同贴片机进行组装的优化策略，但仅确定了各类型元件在不同机器上的分配数量，未涉及吸嘴、供料器等组装工具的分配问题，也未明确贴装点与贴片机的分配关系。
解决方案不完整将导致组装线的效率过度依赖于贴片机的优化效果，可能造成贴片机间工作负载分配的不均衡。
文献\inlinecite{chen_improved_2023,mumtaz_hybrid_2020}运用元启发式算法同时对组装线的元件分配和贴片机的拾贴顺序进行优化，较大的复杂解空间使得算法难以在可接受的时间内获得高质量的解。
负载平衡优化相关研究主要围绕转塔式贴片机展开，直接推广到并列式贴片机构成的生产线中将会导致组装效率的下降。

为降低因引入贴片机优化所导致的组装线负载均衡问题复杂程度和求解时间的增加，文献\inlinecite{wu_solution_2010,liu_surface_assembly_2013, vainio_estimating_2015,li_predicting_2020,vainio_estimating_2010,chen_optimised_2024}等围绕表面组装时间估计开展研究。
其中，
文献\inlinecite{wu_solution_2010,liu_surface_assembly_2013}将贴装点数和组装时间建立关联，其估计结果与实际组装时间之间存在较大的偏差；
文献\inlinecite{vainio_estimating_2015}研究了基于线性回归的时间估计模型，同样无法准确估计并列式贴片机复杂组装过程的用时；
文献\inlinecite{li_predicting_2020,vainio_estimating_2010,chen_optimised_2024}研究了基于机器学习的非线性组装时间估计方法，此类研究较线性拟合在准确度上有了显著的提升。
对于时间估计模型，特征的选择是决定估计准确度的关键因素，有效的特征能够减少估计模型的训练时间和计算成本，提高模型的泛化能力。
总体而言，当前关于组装时间的估计主要集中于转塔式贴片机，而对于以平衡工作负载为目标的并列式贴片机生产线优化问题，现有研究在分配过程和组装时间估计时未能全面考虑影响组装时间的多种因素，进而引发了负载分配的不平衡，降低了组装线的整体效率。


\section{本文主要研究内容及安排}[Major research contents and organization of this thesis]

本文致力于解决表面组装过程中生产调度优化问题，包括贴片机的组装过程优化和组装生产线的负载平衡优化。针对现有研究中模型建立不完备、组装优化算法适用场景受限、组装过程生产效率低等诸多问题展开研究，旨在提高优化算法的可应用性、可部署性和可拓展性，提升表面组装生产过程的效率。
对于复杂的表面组装过程优化，全局直接优化方法易受问题的高维计算复杂性制约，并可能陷入局部最优。本文采用分层优化策略，基于从局部到整体的分阶段降维框架：聚焦核心贴片头任务分配问题的优先求解，再逐层优化贴装过程路径规划和生产线负载平衡，通过降维有效压缩解空间维度，以提升求解效率、逐步逼近最优解。
% 贴片机的组装过程优化被拆分为贴片头任务分配和贴装过程路径规划两个子任务，前者决定了贴片机组装的关键子目标，后者则在其约束下进一步给出了完整组装过程优化方案。生产线负载平衡任务则是在贴片机组装过程优化基础上，对贴片机组装任务等进行分配的优化。
% 贴片头任务分配作为基础层，决定贴片机组装动作的整体调度与资源分配，是效率优化的主导因素。路径规划作为细节层，在贴片头任务分配的框架内优化其贴装过程的移动路径，完善组装过程方案。生产线作为全局层，整合贴片头任务分配和贴装过程路径规划的结果，实现生产线的整体性能优化。
论文的基本组成结构如图\ref{ch1:figure:structure}所示，各章节的组织安排如下：

\begin{figure}[htpb]
	\centering
	\includegraphics[scale=0.825]{chapter1/structure-organization.eps}
	\bicaption[ch1:figure:structure]{}{论文主要研究内容结构框图}{Fig.$\!$}{Structural block diagram of main research contents of this dissertation}
\end{figure}


第2章是全文研究的基础性工作，通过分析影响表面组装过程效率的主要因素，对组装过程的约束条件和优化目标进行了研究。贴片机的组装过程优化问题可以被拆解为拾取过程和贴装过程的规划问题，表面组装生产线是以此为基础的进一步研究。结合实际应用场景，对问题进行了适当简化并提出假设条件，将组装过程优化问题拆分为贴片头任务分配、贴装过程路径规划和组装生产线负载平衡问题，并以此作为本文研究的主线任务。
以（混合）整数线性规划为基础分阶段地建立了准确反映研究对象特性的数学模型，提出了适用于拾取过程的基于关键目标分解的贴片头任务分配模型、适用于贴装过程的多拾贴周期路径规划模型、以及适用于表面组装生产线的负载平衡模型。
数学模型可用于验证表面组装过程解的可行性，定量分析解的质量，为优化算法的设计提供参考。
最后，给出了具体的实例进行分析说明，分析了模型参数的灵敏度和复杂度。


第3章从数学规划和启发式优化算法的角度，研究了表面组装过程中的贴片头任务分配的优化方法，将问题进行进一步拆分为供料器-槽位和贴片头-元件分配优化两部分，通过保证组装过程关键性能指标的高质量，提升了表面组装过程的整体效率。
两类算法适用于不同规模的数据，数学规划法适用于小规模解空间的系统化搜索，启发式优化则适用于大规模解空间的高效搜索。
在基于数学规划的算法设计中，为降低贴片头任务分配模型的复杂度、提高模型的求解效率，提出了基于周期任务集成的模型增强策略，根据问题特征设计了模型的初始解构造算法，提出了一种带有路径预判的模型解的评估策略，用于降低其与后续路径规划问题之间耦合性；
在基于启发式的算法设计中，进一步提出了基于前瞻扫描启发式的贴片头任务分配算法，研究了基于长短期收益评估的元件分配策略，围绕吸嘴分配模式、供料器槽位分配和贴片头元件分配，分阶段地设计启发式算法，结合实际应用中的生产配置，对算法的实现细节进行了详细的讨论。
最后，对比分析了不同模型设计的收敛效果，并将所提出算法和主流研究在组装性能指标等方面进行了比较，通过在不同应用场景下的对比验证，证明了所提算法结果的高效性、可行性和可扩展性。

第4章在第3章研究的基础上，分析了贴装过程的问题特性和分阶段优化方法，研究了基于给定的贴片头任务分配约束下贴装过程路径规划算法，将其拆分为周期内和周期间的优化算法。其中，前者是对周期内有限贴装点的移动路径进行规划，后者则是对贴装点分配的拾贴周期和贴片头进行优化。
在周期内规划阶段，结合贴装过程多轴协同作业的特性，建立了拾贴周期路径规划的状态转移方程，提出了基于动态规划的拾贴周期最优路径规划算法；
在周期间规划阶段，以贪心式贴装点分配为基础，结合多源贪心和动态导向的集束搜索算法，提出了周期间的贴装点分配算法。
周期内和周期间相结合的路径规划算法保证了解的高质量，为进一步优化贴装过程的移动路径，提出了自适应大邻域搜索的聚合路径重构算法，根据贴装点的分布和拾贴周期的移动路径，对已有路径进行破坏和修复，克服了贪心式路径规划导致的拾贴周期间路径移动长度不均衡的问题，实现了对解的持续迭代优化。最后，将提出的路径规划方法和主流研究在相同及不同贴片头任务分配约束下进行了对比，对路径规划算法的关键组成部分的作用进行了分析验证，比较了不同初始解对自适应大邻域搜索结果的影响，证明了提出算法结果的高质量。


第5章在第3--4章研究的基础上，将贴片机组装过程的优化进一步拓展至表面组装生产线的负载平衡优化领域，旨在通过整合多台贴片机提升表面组装流程的整体效率。
为优化由并列式贴片机构成的表面组装生产线，探讨了运用多特征融合集成组装时间估计器的超启发式负载平衡方法，设计了基于数据驱动与目标驱动的底层启发式算子，并提出了不同算子快速比较贴片机之间相关性能指标的方案。此外，为了以可重复分配元件提升组装效率，提出了元件分组搜索策略与聚合聚类元件贴装点分配算法。
在评估解的质量方面，研究了组装时间估计模型的训练数据的生成流程和处理方法、特征提取算法以及设计架构；在此基础上，提出了基于集成学习的组装时间估算器，该估算器以神经网络为基模型，融合了组装数据的基本参数、估算子目标等多维度特征进行编码，实现了对组装时间的准确估计。最后，将所提出的组装时间估计器与其他方法进行了对比，验证了其在准确度方面的提升；围绕解的组装效率、结果稳定性以及算法运行效率等指标，将提出的超启发式负载平衡算法同主流研究进行对比验证，证明了提出算法的高效性、优化结果的高质量和稳定性。