775 lines
60 KiB
TeX
775 lines
60 KiB
TeX
\documentclass[journal,twoside,web]{ieeecolor}
|
||
\usepackage{generic}
|
||
\usepackage{cite}
|
||
\usepackage{amsmath,amssymb,amsfonts}
|
||
\usepackage[ruled,linesnumbered]{algorithm2e}
|
||
\usepackage{graphicx}
|
||
\usepackage{textcomp}
|
||
\usepackage{makecell}
|
||
\usepackage{rotating}
|
||
\usepackage{bbding}
|
||
\usepackage{wasysym}
|
||
\usepackage{amssymb}
|
||
\usepackage[normalem]{ulem}
|
||
\usepackage{multirow}
|
||
\usepackage{pifont}
|
||
\usepackage{color}
|
||
\usepackage{ulem}
|
||
\usepackage{tabularray}
|
||
\usepackage{threeparttable}
|
||
\usepackage{tabularx}
|
||
\usepackage{booktabs}
|
||
|
||
\def\BibTeX{{\rm B\kern-.05em{\sc i\kern-.025em b}\kern-.08em
|
||
T\kern-.1667em\lower.7ex\hbox{E}\kern-.125emX}}
|
||
\markboth{\journalname, VOL. XX, NO. XX, XXXX}
|
||
{Author \MakeLowercase{\textit{et al.}}: Title}
|
||
|
||
\begin{document}
|
||
\title{A Scan-based Hierarchical Heuristic Optimization Algorithm for PCB Assembly Process}
|
||
\author{
|
||
Guangyu Lu, Xinghu Yu, \emph{Member, IEEE}, Hao Sun, Zhengkai Li, \emph{Member, IEEE}, Jianbin Qiu, \emph{Senior Member, IEEE}, and Huijun Gao, \emph{Fellow, IEEE}
|
||
\thanks{Manuscript received 19 May 2023; accepted 27 August 2022. Date of publication XX XX 2023; date of current version 19 May 2023. Paper no. TII-23-1791. \emph{ (Corresponding author: Huijun Gao.)}}
|
||
\thanks{Guangyu Lu, Jianbin Qiu, and Huijun Gao are with the Research Institute of Intelligent Control and Systems, Harbin Institute of Technology, Harbin 150001, China (e-mail: 20b904007@stu.hit.edu.cn; jianbinqiu@gmail.com; hjgao@hit.edu.cn).}
|
||
\thanks{Xinghu Yu is with the College of Physics and Optoelectronic Engineering, Shenzhen University, Shenzhen 518060, China, and also with the Ningbo Institute of Intelligent Equipment Technology Co., Ltd, Ningbo 315201, China (e-mail: 17b304003@stu.hit.edu.cn).}
|
||
\thanks{Hao Sun is with the Bio-Computing Research Center, Harbin Institute of Technology, Shenzhen 518000, China, and also with the Shenzhen Key Laboratory of Visual Object Detection and Recognition, Shenzhen 518000, China (e-mail: sunhao2021@hit.edu.cn).}
|
||
\thanks{Zhengkai Li is with the Department of Mathematics and Theories, Peng Cheng Laboratory, Shenzhen 518000, China (e-mail: lizhk@pcl.ac.cn).}
|
||
}
|
||
\maketitle
|
||
\begin{abstract}
|
||
Surface mount technology is essential to the development of the electronic manufacturing industry. This paper studies optimizing the surface mount process for the beam-head placement machine. A mixed integer programming (MIP) model is proposed for this problem which is decomposed into three interconnected hierarchical parts: feeder allocation, component assignment, and pick-and-place (PAP) sequence problems. This paper proposes an efficient hierarchical framework with three elaborately designed heuristics to solve the above problem. The design of the scan-based algorithms optimizes the sub-objectives of feeder allocation and component assignment.
|
||
Firstly, the allocation heuristic arranges the feeders into slots as a prerequisite for other problems. Then the component assignment heuristic determines the component type for each head with a variety of criteria and long-short term objectives. Finally, the PAP sequence problem is solved using a modified beam search algorithm.
|
||
The proposed algorithm offers advantages in terms of effectiveness, efficiency, and extension, which can satisfy various customization demands. Experiments are conducted on our self-designed placement machine using industrial and randomly generated data. Computational experiments show that the scan-based heuristic algorithm obtains near-optimal solutions with a gap of 9.93\% averagely compared with the proposed MIP model and provides efficiency improvement over the mainstream studies.
|
||
|
||
\end{abstract}
|
||
\begin{IEEEkeywords}
|
||
PCB assembly optimization, hierarchical decomposition, mixed integer linear model, scan-based heuristic
|
||
\end{IEEEkeywords}
|
||
\section{Introduction}
|
||
\label{sec:introduction}
|
||
\IEEEPARstart{N}{owadays}, the widespread use of electronic products in modern life has raised attention to the price and quality of printed circuit boards (PCBs).
|
||
A complicated collection of production procedures makes up for manufacturing electronic products.
|
||
PCB assembly is one of the necessary but time-consuming processes among them. The placement machine is a sophisticated computer-controlled apparatus that integrates mechanical, electrical, and optical techniques~\cite{ayob_optimisation_2007}.
|
||
The factory uses automatic manufacturing lines to produce high-quality PCB, and the maximum production capacity of the placement machine is the efficiency bottleneck of the whole production line. The application benefit of an effective assembly optimization technique is enormous.
|
||
|
||
\begin{figure}
|
||
\centering
|
||
\includegraphics[scale=1]{figures/surface_mounter_layout.eps}
|
||
\caption{The layout of the beam-head placement machine.}
|
||
\vspace{-0.4cm}
|
||
\label{fig_layout}
|
||
\end{figure}
|
||
|
||
This paper focuses on the beam-head placement machine, which has a stationary PCB platform, two stationary feederbases, and a moving gantry with beam heads, as shown in Fig.~\ref{fig_layout}.
|
||
The feeders loading with components are installed on the feederbase. There are three basic types of feeders for assembling various package component parts: tape, stick, and tray. The gantry moves between the PCB and the feederbase to pick and place the components with vacuum valves. The fly camera is equipped in the heads for chip detection; for some large chips, the gantry moves to the fixed camera for inspection. An auto nozzle changer (ANC) is kept with multiple nozzle types to fulfill the assembly needs for various component shapes. The primary distinction between the beam-head placement machine and other types is its mechanical design which enables multi-heads to pick up components from feeders simultaneously.
|
||
|
||
As shown in Fig.~\ref{fig_flowchart}, the surface mount process consists of six different types of operations, and the dashed-line framed part includes a PAP cycle, which is the fundamental unit. The nozzle change, component pick-up, and component placement operations in a PAP cycle take substantial time, and the algorithm can optimize the first two operations. More specifically, by combining multiple head motions, the pick-up operation could be more effective, and the nozzle changes are connected to the sequence of component pick-up. The The component dumping operations caused by image processing errors are exceptions and are not considered in this paper.
|
||
|
||
\begin{figure}
|
||
\centering
|
||
\includegraphics[scale=1]{figures/mount_process_flowchart.eps}
|
||
\caption{The workflow chart of surface mount process.}
|
||
\vspace{-0.4cm}
|
||
\label{fig_flowchart}
|
||
\end{figure}
|
||
|
||
The surface mount optimization problem has multiple variables with significant coupling and is an NP-hard problem~\cite{van_laarhoven_production_1993}.
|
||
A general technique for this complex optimization problem is the hierarchical decomposition method~\cite{lin_modified_2017, gao_iterated_2018}.
|
||
This challenging combinatorial optimization problem is made up of the location problem, assignment problem, and route schedule problem. In the locating problem, the depots are feeders assigned for the assembling process~\cite{sun_component_2005}.
|
||
The assignment problems are concerned with determining the type of component picked up by the placement head, which must take into account the tool compatibility of the nozzle-component~\cite{ashayeri_aggregated_2011, guo_pcb_2011} and its influence on simultaneous pick-up~\cite{tsuchiya_scheduling_2007,geng_mcvrp-based_2019}, both of which are essential factors influencing assembly efficiency. The PAP route schedule is covered in studies~\cite{sun_branch-and-price_2007} and~\cite{li_heuristic_2022} utilizing heuristic and mathematical programming, respectively.
|
||
|
||
|
||
Surface mount optimization has been solved by a variety of algorithms, such as mathematical programming, evolutionary algorithms, tailored constructive heuristics, etc.
|
||
The mathematical programming method is limited by the complexity of the problem, and the subproblem is the subject of multiple studies~\cite{raduly-baka_selecting_2008, huang_applied_2020,luo_milp_2017}. Medium-size problems can be solved using mathematical programming combined with the aggregation~\cite{ashayeri_aggregated_2011} approach and the augmented technique for multi-objective~\cite{torabi_new_2013}.
|
||
Evolutionary algorithms have been widely used in surface mount optimization problems~\cite{slowik_hybrid_2022, gyorfi_efficient_2008, li_cell_2021, zhu_multi-objective_2018, hsu_solving_2017}, such as the genetic algorithm, particle swarm algorithm, shuffle leapfrog method, etc.
|
||
Complex optimization problems may have multiple sub-objectives, and research has been done to combine multi-objective optimization with evolutionary algorithms to find the Pareto fronts of the problems~\cite{cao_distributed_2017, lin_multiobjective_2017}.
|
||
Some studies provide constructive heuristics, which solve the problem based on the struct of the problem and significantly improve the quality of solutions~\cite{gao_hierarchical_2021}.
|
||
|
||
To summarize, there is still a long way to industrial deployments. Current research is flawed by irrational assumptions or inadequate examination of the factors influencing assembly efficiency. The algorithm needs to be constructed to work in various application scenarios.
|
||
In this paper, we propose a mathematical model and a novel hierarchical scan-based heuristic framework for the surface mount optimization problem. The contributions of this paper are summarized as follows.
|
||
|
||
\begin{enumerate}
|
||
\item A mixed integer model for the PCB assembly process is proposed. The model fully incorporates the factors affecting assembly efficiency and decomposes the assembly process into pick-up and placement parts. The pick-up model takes into account the impact of simultaneous pick-up on efficiency for the first time, and the placement model is modeled as a variant of the multiple traveling salesman problem (MTSP).
|
||
\item The hierarchical decomposition approach reduces the complexity of the problem. Based on the problem characteristics for each subproblem, three elaborately designed heuristics combined with the scanning concept are proposed, which can obtain a nearly optimal solution and perform better on the search efficiency compared to other approaches.
|
||
\item The proposed algorithms demonstrate substantial extensions, which are adaptable enough to satisfy the operators' various customized requirements. The algorithm optimization process simulates the pick-up process, which can be adapted to the actual situation of the feeder allocation and component pick-up operation tasks.
|
||
\end{enumerate}
|
||
|
||
The remainder of this paper is organized as follows:
|
||
Section~\ref{model_section} presents a mixed integer mathematical model, and Section~\ref{algorithm_section} proposes a scan-based hierarchical heuristic algorithm to provide a satisfying PCB assembly solution. In Section~\ref{experiment_section}, the experiment results are introduced and compared with the mainstreaming study.
|
||
|
||
\section{Mathematical model}\label{model_section}
|
||
\subsection{Problem Description}
|
||
The surface mount optimization is to solve the scheduling problem of the PCB assembly process and get an efficient solution with complicated constraints and multiple decision variables. The typical sub-problems of the assembly process are the feeder allocation problem and the head-task assignment problem. The former solves the problem of the arranged slots of feeders, while the latter determines the assembly sequence.
|
||
The component assignment problem and the PAP route schedule problem are further decompositions in this paper for the head task assignment. There is a progressive relationship between the two sub-problems, and the complexity of the problem can be reduced by determining the component type and then the placement point of each head.
|
||
|
||
The underlying sub-problems are tightly coupled. The feeder allocation affects component assignment for maximizing the number of simultaneous pick-ups, i.e., combining more pick-up operations.
|
||
The pick-up slots of the assembly process and the assembly sequence determine the overall movement distance of the gantry. There may be redundant movements for pick-up operations and nozzle changes for the consistency of the nozzle type, component type and feeder slot.
|
||
|
||
This work makes the following assumptions about the optimization problem with litter impact on the optimality of the solution.
|
||
|
||
\begin{itemize}
|
||
\item The X- and Y-axis motor movement is simplified to an independently controlled trapezoidal profile.
|
||
\item The interval distance between adjacent heads is integer times the interval distance between two adjacent feeder slots.
|
||
\item Only an appropriate type of nozzle can pick up the component.
|
||
\item The ANC configuration is predetermined, and the movement at different holes is ignored.
|
||
\item Tray and stick feeders have predetermined arrangements and are not incorporated into the optimization process.
|
||
\end{itemize}
|
||
|
||
\begin{table}
|
||
\caption{Summary of notations}
|
||
\begin{threeparttable}
|
||
\begin{tabular}{p{0.1cm}p{1.3cm}p{6.1cm}}
|
||
\toprule
|
||
& Notation \centering & Description \\
|
||
\hline
|
||
\multirow{7}*{\begin{sideways}Indexes \& Sets\end{sideways}}
|
||
& $i \in I $ \centering & index of comp. type, $I = \left\{1, 2, \cdots \right\}$\\
|
||
& $j \in J$ \centering& index of nozzle type, $J = \left\{1, 2, \cdots \right\}$\\
|
||
& $p,q \in P$ \centering& index of (placement) point, $P = \left\{1, 2, \cdots \right\}$\\
|
||
& $h, l \in H $ \centering& index of head, $H = \left\{1, 2, \cdots \right\}$\tnote{1}\\
|
||
& $a \in A$ \centering& index of arc, $A = \left\{ \left(h, l \right) | h \neq l, h, l \in H \right\}$\tnote{2} \\
|
||
& $k \in K, K^{\prime}$ \centering& index of cycle, $K = \left\{1, 2, \cdots \right\}, K^{\prime} = \left\{k| g_{k} > 0\right\} $ \\
|
||
& $s, r \in S$ \centering& index of slot, $S = \left\{1, 2, \cdots \right\}$\tnote{3} \\
|
||
|
||
\hline
|
||
\multirow{14}*{\begin{sideways}Parameters\end{sideways}}
|
||
& $t_c$ \centering& the average moving time of round trip between PCB and feederbase \\
|
||
& $t_n$ \centering& the average time of nozzle change operation \\
|
||
& $t_p$ \centering& the average time of pick-up operation \\
|
||
& $t_m$ \centering& the average moving time on the feederbase per slot \\
|
||
& $\mu_{ij}$ \centering& the compatibility of comp. type $i$ and nozzle type $j$ \\
|
||
& $\eta_{ip}$ \centering& the correspondence of comp. type $i$ and point $p$ \\
|
||
& $\psi_{i}$ \centering& the number of points of comp. type $i$ \\
|
||
& $\phi_{i}$ \centering& the feeder number of comp. type $i$ available\\
|
||
& $\zeta_{j}$ \centering& the number of nozzle type $j$ available\\
|
||
& $\lambda^{FW}_{pkh}$ \centering& the moving time from feederbase to the first point in cycle $k$ \\
|
||
& $\lambda^{PL}_{pqa}$ \centering& the moving time between point $p$ and point $q$ along with arc $a$ \\
|
||
& $\lambda^{BW}_{pkh}$ \centering& the moving time from the last point to feederbase in cycle $k$ \\
|
||
& $\rho$ \centering& the interval distacne between adjacent heads \\
|
||
& $\tau$ \centering& the interval ratio of adjacent heads and adjacent slots \\
|
||
& $M$ \centering& a sufficiently large number \\
|
||
|
||
\hline
|
||
\multirow{14}*{\begin{sideways}Decision Variables\tnote{4}\end{sideways}}
|
||
& $g_{k}$ \centering& binary var. $=1$ iff at least one point is picked up and placed in cycle $k$ \\
|
||
& $u_{k}$ \centering& integer var. the pick-up moving slot of cycle $k$ \\
|
||
& $d_{h}$ \centering& integer var. the number of nozzle changes of head $h$ \\
|
||
& $e_{sk}$ \centering& binary var. $= 1$ iff component is picked up from the equality slot $s$ in cycle $k$ \\
|
||
& $f_{si}$ \centering& binary var. $= 1$ iff comp. type $i$ is assigned to slot $s$ \\
|
||
& $x_{iskh}$ \centering& binary var. $= 1$ iff head $h$ picks up comp. type $i$ from slot $s$ in cycle $k$ \\
|
||
& $w_{pqka}$ \centering& binary var. $= 1$ iff point $p$ is placed after point $q$ along with arc $a$ in cycle $k$ \\
|
||
& $y_{pkh}$ \centering& binary var. $=1$ iff point $p$ is the first point placed with head $h$ in cycle $k$ \\
|
||
& $z_{pkh}$ \centering& binary var. $=1$ iff point $p$ is the last point placed with head $h$ in cycle $k$ \\
|
||
\bottomrule
|
||
\end{tabular}
|
||
\begin{tablenotes}
|
||
\footnotesize
|
||
\item[1] The head set $H_{s}$ is the subset $H$, which contains the heads that can pick up components from slot $s$, $H_{s} = \left\{ \max(1, -\lfloor \left( s - 1 \right) / \tau \rfloor + 1), \cdots, \right. \\ $
|
||
$\left. \min \left( \left| H \right|, \lceil \left(\left| S \right| - s + 1\right) / \tau \rceil \right) + 1 \right\}$
|
||
\item[2] The arcs of $A$ represent the placement sequence of the heads. $A_{h}$, $A_{h}^{f}$ and $A_{h}^{t}$ are subsets of $A$, where $A_{h}$ has the arcs of $A$ that pass head $h$, $A_{h}^{f}$ has the arcs of $A$ from head $h$, and $A_{h}^{t}$ has the arcs of $A$ to head $h$.
|
||
\item[3] $S^{\prime}$ is the set of equality slot index, which refers to the left-most head aligned slot, $S^{\prime} = \left\{ -\tau \cdot \left( \left| H \right| - 1 \right) + 1, \cdots, 1, 2, \cdots, \left| S \right| \right\}$
|
||
\item[4] The intermediate continuous variables $v_{pq}$, $n_{p}$, and $m_{p}$ are used to eliminate subtour.
|
||
\end{tablenotes}
|
||
\end{threeparttable}
|
||
\vspace{-0.4cm}
|
||
\label{notation_summary_table}
|
||
\end{table}
|
||
|
||
\subsection{Optimization Objective and Constraints}
|
||
The surface mount process is accomplished by a complex series of motions that work together.
|
||
The target of minimizing the assembly time depends on the distance of the gantry traveling, the number of pick-up operations, and the number of nozzle change operations which are the sub-objectives. The coupling of sub-objectives is reflected in combining the pick-ups of multiple heads may bring additional nozzle change, and the distance of the gantry traveling relies on the pick-up and nozzle change operations.
|
||
|
||
The constraints for surface mount optimization problems can be divided into four categories: job completion constraint, mechanical restriction, tool requirement, and artificial constraints. Job completion is essential for surface mount tasks, and each component must be assembled accurately on the corresponding PCB pads.
|
||
The mechanical restriction concerns the structural characteristics of the placement machine, such as each head having unreachable pick-up slots.
|
||
Another type of mechanical constraint is positional interference caused by feeders occupying multiple slots.
|
||
The restricted number of nozzles and feeders available will also impede optimizing assembly efficiency. Tool consistency is a critical assurance for the assembly process.
|
||
In terms of artificial limits, operators may want to pre-arrange feeders, prohibit some feeder slots, and set prohibited heads.
|
||
|
||
|
||
\subsection{Mixed Integer Programming Model}
|
||
Mathematical programming methods to solve the surface placement task must deal with the problems of numerous decision variables and intricate constraints.
|
||
The route scheduling of the gantry is constrained by the type of component, nozzle, and slot that corresponds to each head, which greatly increases the complexity of the model.
|
||
This paper proposes a hierarchical mixed integer programming model to solve the problem effectively by decomposing the surface mount process into two parts: the pick-up model and the placement model.
|
||
The pick-up model is a prerequisite for the solution of the placement model, which determines the movement time parameters and the placement head task in the placement model.
|
||
The notations of the proposed model are shown in Table~\ref{notation_summary_table}. The table describes the type of decision variables, all of which are non-negative.
|
||
\vspace{0.2cm}
|
||
|
||
\subsubsection{Pickup Model}
|
||
\begin{equation}
|
||
\min t_{c}\!\cdot\!\sum_{k \in K}{g}_{k} + t_{n}\!\cdot\!\sum_{h \in H} d_{h} + t_{p}\!\cdot\!\sum_{s \in S^{\prime}} \sum_{k \in K} e_{sk}+ t_{m}\!\cdot\!\sum_{k \in K} u_{k}
|
||
\label{pick_model_obj}
|
||
\end{equation}
|
||
% constraint
|
||
\begin{equation}
|
||
g_{k} \geq g_{k + 1} \quad \forall k \in K \backslash \left\{ \left| K \right| \right\}
|
||
\label{cycle_constr}
|
||
\end{equation}
|
||
\begin{equation}
|
||
\sum_{i \in I} \sum_{s \in S} x_{iskh} \leq g_{k} \quad \forall k \in K, h \in H
|
||
\label{component_cycle_constr}
|
||
\end{equation}
|
||
\begin{equation}
|
||
\sum_{j \in J} \sum_{i \in I} \sum_{s \in S} \mu_{ij} \cdot x_{iskh} \leq 1 \quad \forall k \in K, h \in H
|
||
\label{nozzle_assign_constr}
|
||
\end{equation}
|
||
\begin{equation}
|
||
\sum_{s \in S} \sum_{h \in H} \sum_{k \in K} x_{iskh} = \psi_{i} \quad \forall i \in I
|
||
\label{work_complete_constr}
|
||
\end{equation}
|
||
% nozzle change constraint
|
||
\begin{equation}
|
||
\begin{aligned}
|
||
d_{h} = \frac{1}{2}\sum_{k \in K \backslash \left\{ \left| K \right| \right\}} \Big( \sum_{j \in J} \Big| \sum_{i \in I} \sum_{s \in S} \mu_{ij} \cdot x_{iskh} - \sum_{i \in I} \sum_{s \in S} \\
|
||
\mu_{ij} \cdot x_{is\left( k + 1 \right)h} \Big| - 1 \Big)\quad \forall h \in H
|
||
\end{aligned}
|
||
\label{nozzle_change_constr}
|
||
\end{equation}
|
||
\begin{equation}
|
||
e_{sk} \leq \sum_{i \in I} \sum_{h \in H_{s}} x_{i \left[s + \left(h - 1\right) \cdot \tau \right]kh} \leq M \cdot e_{sk} \quad \forall s \in S^{\prime}, k \in K
|
||
\label{equ_slot_constr}
|
||
\end{equation}
|
||
\begin{equation}
|
||
u_{k} \geq s \cdot e_{sk} - r \cdot e_{rk} \quad \forall k \in K, s,r \in S^{\prime}
|
||
\label{pickup_moving_constr}
|
||
\end{equation}
|
||
\begin{equation}
|
||
f_{si} \leq \sum_{h \in H} \sum_{k \in K} x_{iskh} \leq M \cdot f_{si} \quad \forall s \in S, i \in I
|
||
\label{feeder_assign_constr}
|
||
\end{equation}
|
||
\begin{equation}
|
||
\sum_{i \in I} f_{si} \leq 1 \quad \forall s \in S
|
||
\label{slot_capacity_constr}
|
||
\end{equation}
|
||
\begin{equation}
|
||
\sum_{h \in H} \sum_{i \in I} \sum_{s \in S} \mu_{ij} \cdot x_{iskh} \leq \zeta_{j} \quad \forall k \in K, j \in J
|
||
\label{nozzle_available_constr}
|
||
\end{equation}
|
||
\begin{equation}
|
||
\sum_{s \in S} f_{si} \leq \phi_{i} \quad \forall i \in I
|
||
\label{feeder_available_constr}
|
||
\end{equation}
|
||
\indent The objective of the pick-up model~\eqref{pick_model_obj} consists of four terms: the number of cycles, nozzle change operations, pick-up operations, and pick-up moving distance, where the pick-up moving distance is represented by the number of slots the gantry crosses over.
|
||
Constraint~\eqref{cycle_constr} ensures that the first few cycles of the surface mount process are given top priory for completion.
|
||
The heads and work cycle are consistent with Constraint~\eqref{component_cycle_constr}.
|
||
Constraint~\eqref{nozzle_assign_constr} ensures each head is equipped with at most one nozzle type.
|
||
The completion of the surface mount process for each component type is guaranteed by constraint~\eqref{work_complete_constr}.
|
||
Constraint~\eqref{nozzle_change_constr} calculates the number of nozzle changes of each head, and constraint~\eqref{equ_slot_constr} converts the pick-up slot of each head to the left-most head to calculate the number of the pick-up operations in each cycle.
|
||
Constraint~\eqref{pickup_moving_constr} calculates the number of slots crossed over by the gantry for the pick-up process in each cycle.
|
||
Constraint~\eqref{feeder_assign_constr} ensures the consistency of head pick-up operations and feeder allocation.
|
||
Constraint~\eqref{slot_capacity_constr} ensures each slot is assigned at most one feeder.
|
||
Constraint~\eqref{nozzle_available_constr} and~\eqref{feeder_available_constr} indicate the limited number of available nozzles and feederbase, respectively.
|
||
\vspace{0.2cm}
|
||
% ======= Placement Model =======
|
||
\subsubsection{Placement Model}
|
||
\begin{equation}
|
||
\begin{aligned}
|
||
\min \sum_{k \in K^{\prime}} \Big\{ \sum_{p \in P} \sum_{h \in H} \lambda^{FW}_{pkh} \cdot y_{pkh} +
|
||
\sum_{p \in P} \sum_{q \in P} \sum_{a \in A} \lambda^{PL}_{pqa} \cdot \\
|
||
w_{pqka} + \sum_{p \in P} \sum_{h \in H} \lambda^{BW}_{pkh} \cdot z_{pkh} \Big\}
|
||
\end{aligned}
|
||
\label{place_model_obj}
|
||
\end{equation}
|
||
% constraint
|
||
\begin{equation}
|
||
\begin{aligned}
|
||
\sum_{q \in P} \sum_{a \in A_{h}} w_{pqka} = \sum_{i \in I} \sum_{s \in S} \eta_{ip} \cdot x_{iskh} \\
|
||
\forall p \in P, k \in K^{\prime}, h \in H
|
||
\end{aligned}
|
||
\label{pick_model_constr}
|
||
\end{equation}
|
||
\begin{equation}
|
||
\sum_{p \in P} \sum_{q \in P} \sum_{a \in A_{h}} w_{pqka} \leq 2 \quad \forall k \in K^{\prime}, h \in H
|
||
\label{head_point_constr1}
|
||
\end{equation}
|
||
\begin{equation}
|
||
\sum_{p \in P} \left( y_{pkh} + z_{pkh} \right) \leq 1 \quad \forall k \in K^{\prime}, h \in H
|
||
\label{head_point_constr2}
|
||
\end{equation}
|
||
\begin{equation}
|
||
\begin{aligned}
|
||
\sum_{q \in P} \sum_{a \in A^{t}_{h}} w_{qpka} + y_{pkh} = \sum_{q \in P} \sum_{a \in A^{f}_{h}} w_{pqka} + z_{pkh} \quad \\ \forall k \in K^{\prime}, h \in H, p \in P
|
||
\end{aligned}
|
||
\label{task_continuity_constr1}
|
||
\end{equation}
|
||
\begin{equation}
|
||
y_{pkh} \leq \sum_{q \in P} \sum_{a \in A^{f}_{h}} w_{pqka} \quad \forall k \in K^{\prime}, h \in H, p \in P
|
||
\label{task_continuity_constr2}
|
||
\end{equation}
|
||
\begin{equation}
|
||
z_{pkh} \leq \sum_{q \in P} \sum_{a \in A^{t}_{h}} w_{qpka} \quad \forall k \in K^{\prime}, h \in H, p \in P
|
||
\label{task_continuity_constr3}
|
||
\end{equation}
|
||
\begin{equation}
|
||
\sum_{p \in P} \sum_{h \in H} y_{pkh} = 1 \quad \forall k \in K^{\prime}
|
||
\label{start_edge_constr}
|
||
\end{equation}
|
||
\begin{equation}
|
||
\sum_{p \in P} \sum_{h \in H} z_{pkh} = 1 \quad \forall k \in K^{\prime}
|
||
\label{end_edge_constr}
|
||
\end{equation}
|
||
\begin{equation}
|
||
\sum_{k \in K^{\prime}} \left( \sum_{h \in H} y_{pkh} + \sum_{q \in P} \sum_{a \in A} w_{pqka} \right) = 1 \quad \forall p \in P
|
||
\label{enter_edge_constr}
|
||
\end{equation}
|
||
\begin{equation}
|
||
\sum_{k \in K^{\prime}} \left( \sum_{h \in H} z_{pkh} + \sum_{q \in P} \sum_{a \in A} w_{qpka} \right)= 1 \quad \forall p \in P
|
||
\label{leave_edge_constr}
|
||
\end{equation}
|
||
% subtour
|
||
\begin{equation}
|
||
m_{p} + \sum_{q \in P} v_{pq} - n_{p} - \sum_{q \in P} v_{qp} = 1 \quad \forall p \in P
|
||
\label{subtour_constr1}
|
||
\end{equation}
|
||
\begin{equation}
|
||
v_{pq} \leq \sum_{k \in K^{\prime}} \sum_{a \in A} \left(\left| P \right| - \left| K^{\prime} \right| + 1\right) \cdot w_{pqka} \quad \forall p,q \in P
|
||
\label{subtour_constr2}
|
||
\end{equation}
|
||
\begin{equation}
|
||
n_{p} \leq \sum_{k \in K^{\prime}} \sum_{h \in H} \left(\left| P \right| - \left| K^{\prime} \right| + 1 \right) \cdot y_{pkh} \quad \forall p \in P
|
||
\label{subtour_constr3}
|
||
\end{equation}
|
||
\begin{equation}
|
||
m_{p} \leq \sum_{k \in K^{\prime}} \sum_{h \in H} \left(\left| P \right| - \left| K^{\prime} \right| + 1 \right) \cdot z_{pkh} \quad \forall p \in P
|
||
\label{subtour_constr4}
|
||
\end{equation}
|
||
|
||
The objective of placement model~\eqref{place_model_obj} is the total of the moving times except for the pick-up movement, which has been solved in the pick-up model.
|
||
The parameters of moving time $\lambda$ in the objective are obtained based on the solution of the pick-up model.
|
||
Constraint~\eqref{pick_model_constr} ensures that the solutions of the pick-up model and the placement model are consistent.
|
||
Constraint~\eqref{head_point_constr1}--\eqref{head_point_constr2} ensure each head is placed at most one placement point.
|
||
Constraint~\eqref{task_continuity_constr1}--\eqref{task_continuity_constr3} ensure the continuity of the placement task, i.e., the placement head is unique for each point.
|
||
Constraint~\eqref{start_edge_constr} and~\eqref{end_edge_constr} mean that the path of the placement head from the feederbase to the PCB and from the PCB back to the feederbase is unique for each cycle. Constraint~\eqref{enter_edge_constr} and~\eqref{leave_edge_constr} ensure the entry edge and the leave edge of each point are unique, respectively.
|
||
Constraints~\eqref{subtour_constr1}--\eqref{subtour_constr4} are utilized to eliminate the subtour for each cycle.
|
||
|
||
The pick-up model~\eqref{pick_model_obj}--\eqref{feeder_available_constr} and placement model~\eqref{place_model_obj}--\eqref{subtour_constr4} involve an assignment problem and a restricted MTSP problem, which are two well-known NP-hard problems.
|
||
Therefore, the proposed model above can be solved only for small-scale data in a reasonable amount of time.
|
||
In Section~\ref{algorithm_section}, we will further decompose the problem following the optimization objective, and an efficient hierarchical framework will be proposed to solve this problem.
|
||
|
||
|
||
%% ====== Scan Heuristic Alogorithm ======
|
||
\section{HIERARCHICAL HEURISTIC OPTIMIZATION}\label{algorithm_section}
|
||
|
||
\subsection{Scan-based Heuristic Hierarchical Framework}
|
||
|
||
\begin{figure}[htbp]
|
||
\centering
|
||
\includegraphics[scale=0.8]{figures/mount_process_description.eps}
|
||
\caption{The relationship of surface mount process optimization sub-objectives, sub-problems, and constraints.}
|
||
\vspace{-0.4cm}
|
||
\label{fig_description}
|
||
\end{figure}
|
||
|
||
Hierarchical decomposition is a common method for solving complicated optimization problems. A direct solution to the whole problem may bring on a dimensionality disaster because of the numerous constraints and decision variables. It makes sense to design the algorithm by the relevance of the sub-objective. The constructive scan heuristic algorithm~\cite{sun_component_2005} is the basis of the proposed method in this paper, which overcomes the shortcomings of the lengthy solving time and greedily maximizes the pick-up efficiency.
|
||
|
||
This paper decomposes the surface mount optimization problem into feeder allocation problem, component assignment problem, and PAP sequence problem.
|
||
We prioritize feeders since ignoring them will significantly increase pick-up operations and longer moving routes.
|
||
Furthermore, if the feeder arrangement must be changed each time the PCB changes, the labor cost associated with re-optimizing the algorithm could increase.
|
||
PAP route schedule is the final subproblem to be solved since the moving distance of the placement heads has less impact on assembly efficiency than other factors.
|
||
|
||
\begin{algorithm}
|
||
\small
|
||
\caption{Feeder Allocation Heuristic}
|
||
\label{allocation_algorithm}
|
||
\SetKwInOut{Input}{Input}\SetKwInOut{Output}{Output}
|
||
\SetKwProg{Fn}{function}{}{end}
|
||
|
||
\Input{PCB data, component data, feeder data, nozzle pattern $\mathcal{N}$}
|
||
\Output{feeder assignment $\mathcal{F}^{CP} $ and $\mathcal{F}^{PT}$}
|
||
Initialize $\mathcal{F}^{CP} $ as the component type pre-arranged on the feederbase (-1 for empty), $\mathcal{F}^{PT} $ as the number of the placement points, and $\mathcal{S}$ as an empty stack\;
|
||
\While{$\sum_{i \in I} \psi_{i} \neq 0$}
|
||
{
|
||
Initialize $V_{b} \leftarrow 0$ as the best allocation value\;
|
||
\For{$s \leftarrow 1$ to $\left| S \right| - \left( \left| H \right| - 1 \right) \cdot \tau $}
|
||
{
|
||
\lForEach{$s^{\prime} = s + \left( h - 1 \right) \cdot \tau, h \in H$}{$\mathcal{H}^{CP} \left( h \right) \leftarrow \mathcal{F}^{CP}\left( s^{\prime} \right), \mathcal{H}^{PT} \left( h \right) \leftarrow \mathcal{F}^{PT}\left( s^{\prime} \right) $}
|
||
$I^{\prime} \leftarrow I$ \;
|
||
\For{$j \leftarrow \mathcal{N} \left( h \right), h \in \left\lbrace h^{\prime} \big| \mathcal{H}^{CP} \left( h^{\prime} \right) > 0\right\rbrace$}
|
||
{
|
||
\uIf {$\psi_{i} = 0, \forall i \in \left\lbrace i^{\prime} \big| \xi_{i^{\prime}j} \neq 0, i^{\prime} \in I^{\prime} \right\rbrace$}
|
||
{
|
||
\textbf{push} $i \leftarrow {\rm argmax}_{i^{\prime} \in I^{\prime}} \left\lbrace \psi_{i^{\prime}} \right\rbrace $ into $\mathcal{S}$ \;
|
||
}
|
||
\Else
|
||
{
|
||
$i \leftarrow {\rm argmax}_{i^{\prime} \in I^{\prime}} \left\{ \psi_{i^{\prime}} \big| j \cdot \xi_{i^{\prime}j} > 0 \right\}$
|
||
$\mathcal{H}^{CP} \left( h \right) \leftarrow i$, $\mathcal{H}^{PT} \left( h \right) \leftarrow \psi_{i}$ \;
|
||
}
|
||
$I^{\prime} \leftarrow I^{\prime} \backslash \left\{ i \right\}$ \;
|
||
}
|
||
|
||
\textbf{Pop} components from $\mathcal{S}$ and assign them to the heads $h \in \left\{ h^{\prime} \big| \mathcal{H}^{PT} \left( h^{\prime} \right) = 0\right\}$ \;
|
||
\If{$\sum_{h \in H} \mathcal{H}^{PT} \left( h \right) > V_{b}$}
|
||
{
|
||
$V_{b} \leftarrow \sum_{h \in H} \mathcal{H}^{PT} $, $\mathcal{H}_b^{PT} \leftarrow \mathcal{H}^{PT}$, $\mathcal{H}_b^{CP} \leftarrow \mathcal{H}^{CP}$, $s_b \leftarrow s$
|
||
}
|
||
}
|
||
$\delta = \min\left\lbrace \mathcal{H}^{PT}_{b} \left( h \right) \big| \mathcal{H}^{PT}_{b} \left( h \right) \neq 0, h \in H \right\rbrace$ \;
|
||
\For {$s^{\prime} \leftarrow s_{b} + \left( h - 1\right) \cdot \tau $, $h \in H$}
|
||
{
|
||
\If{$\mathcal{F}^{PT} \left( s^{\prime} \right) = -1$}
|
||
{
|
||
$\mathcal{F}^{CP} \left( s^{\prime} \right) \leftarrow \mathcal{H}^{CP}_{b} \left( h \right)$ \;
|
||
}
|
||
$\mathcal{F}^{PT} \left( s^{\prime} \right) \leftarrow \mathcal{F}^{PT}_{b} \left( s^{\prime} \right) - \delta$ \;
|
||
$\mathcal{N} \left( h \right) \leftarrow j, \psi_{i} \leftarrow \psi_{i} - \delta$ where $i = \mathcal{H}^{CP}_{b} \left( h \right)$, $ j = \sum_{j^{\prime} \in J} j^{\prime} \cdot \xi_{ij^{\prime}}$\;
|
||
}
|
||
}
|
||
% \vspace{-1cm}
|
||
\end{algorithm}
|
||
|
||
The relationship among sub-problems, sub-objectives, and constraints is shown in Fig.~\ref{fig_description}. The feeder allocation and component assignment problems impact the nozzle changes and simultaneous pick-ups, while the route schedule problem is relatively independent. It can be expected that there are certain similarities in the algorithm design of feeder allocation and component assignment. The superscript NZ, CP, and PT of the notations in the algorithm description are the abbreviation of nozzle type, component type, and the number of placement points, respectively.
|
||
|
||
\subsection{Feeder Allocation Heuristic Algorithm}\label{subsection_allocation}
|
||
|
||
Feeder allocation is a prerequisite for other subproblems, and an appropriate arrangement will significantly enhance pick-up efficiency, which determines the component pick-up slot. The basic idea of feeder allocation heuristic described in Algorithm~\ref{allocation_algorithm} is assigning the feeders while scanning the feederbase under the constraint of the nozzle pattern, which can maximize the number of pick-up points allocated in a round and avoid nozzle change. The algorithm assigns feeders to the empty slots in the different rounds, reserving the component types already arranged in the head-aligned slots. The component types that can be allocated in the head-aligned slots are determined by the nozzle pattern. The nozzle pattern helps to reduce the number of nozzle changes for subsequent pick-up operations. The type of component with more placement points that do not meet the nozzle pattern restriction is stored in component stacks to guarantee a comparably concentrated position of the feeder allocation. At the end of the assignment, the algorithm assigns components in the stack to slots.
|
||
|
||
\subsection{Component Assignment Heuristic Algorithm}\label{subsection_scan}
|
||
|
||
The algorithmic framework for feeder allocation and component assignment is similar, and both are based on heuristic scanning.
|
||
The feeder allocation solves the problem of component pick-up position, and the component assignment solves the problem of pick-up sequence.
|
||
The scanning heuristic efficiently optimizes the simultaneous pick-ups, which significantly reduces the overall pick-up operations by integrating the pick-up operations of multi-heads.
|
||
Similar to feeder allocation produces, each head aligns to a slot starting from different pick-up slots,
|
||
the component assigned to the head should satisfy the following criteria:
|
||
|
||
\begin{algorithm}
|
||
\small
|
||
\caption{Component Assignment Heuristic}
|
||
\label{component_assign_algorithm}
|
||
\SetKwInOut{Input}{Input}\SetKwInOut{Output}{Output}
|
||
\SetKwProg{Fn}{function}{}{end}
|
||
|
||
\Input{PCB data, feeder allocation $\mathcal{F}^{CP}$ and $\mathcal{F}^{PT} $}
|
||
\Output{component assignment $\mathcal{C}$ and cycle group $\mathcal{K}$}
|
||
Initialize a $1 \times \left| H \right| $ matrix $ \mathcal{M}$ of \textbf{\textit{None}} as the initial nozzle assignment\;
|
||
\While{$\sum_{s \in S}\mathcal{F}^{PT} \left( s \right) \neq 0$}
|
||
{
|
||
Initialize $V_{b} \leftarrow 0$ as the best assignment value\;
|
||
\For {$\mathcal{N} \in \mathcal{M}$, $s \leftarrow 1$ to $\left| S \right| - \left( \left| H \right| - 1\right) \tau$}
|
||
{
|
||
\For {$h \in H$}
|
||
{
|
||
$s^{\prime} \leftarrow s + \left( h - 1\right) \tau$, $i \leftarrow \mathcal{F}^{CP} \left( s^{\prime} \right)$ \;
|
||
|
||
Calculate $v \leftarrow e_{1} \cdot v_{1} - e_{2} \cdot v_{2} $ where
|
||
$v_{1} = \min_{h^{\prime} \in H} \left\lbrace \mathcal{H}^{PT} \left( h^{\prime} \right) > 0 \right\rbrace \cup \left\lbrace \mathcal{F}^{PT} \left( s^{\prime} \right)\right\rbrace$,
|
||
$v_{2} = \sum_{h^{\prime} \in H} \left| \mathcal{N} \left( h^{\prime} \right) - \sum_{j} \xi_{\mathcal{H}^{PT} \left( h^{\prime} \right) \cdot j} \right|$\;
|
||
\If { $\mathcal{F}^{PT} \left( s^{\prime} \right) > 0$ \textbf{and} $v > 0$}
|
||
{
|
||
$\mathcal{H}^{CP} \left( h \right) \leftarrow \mathcal{F}^{CP} \left( s^{\prime} \right), \mathcal{H}^{PT} \left( h \right) \leftarrow \mathcal{F}^{PT} \left( s^{\prime} \right) $\;
|
||
}
|
||
}
|
||
|
||
Calculate short-term objective $V_{s}$ and long-term objective $V_{l}$ with Algorithm~\ref{objective_algorithm}\;
|
||
|
||
\If {$ e \cdot V_{l} + \left( 1 - e\right) \cdot V_{s} > V_{b}$}
|
||
{
|
||
$V_{b} \leftarrow e \cdot V_{l} + \left( 1 - e\right) \cdot V_{s}, s_{b} \leftarrow s $ \;
|
||
$\left( \mathcal{H}^{PT}_{b}, \mathcal{H}^{CP}_{b}, \mathcal{H}^{NZ}_{b} \right) \leftarrow \left( \mathcal{H}^{PT}, \mathcal{H}^{CP}, \mathcal{H}^{NZ} \right)$
|
||
}
|
||
}
|
||
$k \leftarrow \min_{h \in H} \left\{ \mathcal{H}^{PT}_{b} \left(h \right) > 0 \right\}$ \;
|
||
|
||
\lForEach{$h \in H$}
|
||
{
|
||
$s^{\prime} \leftarrow s_{b} + \left( h - 1\right) \cdot \tau, \mathcal{F}^{PT} \left( s^{\prime} \right) \leftarrow \mathcal{F}^{PT} \left( s^{\prime} \right) - k $
|
||
}
|
||
|
||
\If {$\mathcal{H}_{b}^{PT} \left( h \right)> 0$ \textbf{or} $\mathcal{F}^{PT} \left( s \right) = 0, \forall h \in H, s \in S$}
|
||
{
|
||
Attach $\mathcal{H}_{b}^{CP}$ to $\mathcal{C}$, $\mathcal{H}^{NZ}_{b}$ to $\mathcal{M}$, $k$ to $\mathcal{K}$ along with column direction \;
|
||
}
|
||
}
|
||
\end{algorithm}
|
||
|
||
\begin{enumerate}
|
||
\item \emph{Pick-up Feasibility}: The head-aligned slot contains unpicked placement points.
|
||
\item \emph{Pick-up Constraint}: The head-equipped number of nozzles does not exceed the number available.
|
||
\item \emph{Pick-up Prejudgment}: The component being picked up does not lessen the number of subsequent simultaneous pick-ups of the prejudgment.
|
||
\item \emph{Pick-up Objective}: The efficiency gain from pick-up outweighs the efficiency loss from nozzle change.
|
||
\end{enumerate}
|
||
|
||
Algorithm~\ref{component_assign_algorithm} describes the implementation of the component assignment. Each round determines the type of component assigned to heads with unpicked placement points and the related cycle groups. A "cycle group" is a set of consecutive PAP cycles with the same component assignments. It should be mentioned that the scanning-based pick-up procedure tries to maximize the number of simultaneous pick-ups while minimizing the expense of nozzle changes. The component assignment heuristic is forward-looking, which means that the single-head component assignment prejudges its impact on subsequent assignments. This is principally reflected in the following two aspects: the first is to assign just those components that improve the overall objective, and the second is the long-short term objectives. As for long-short term objectives implemented in Algorithm~\ref{objective_algorithm}, the long-term objective is to simultaneously pick up components from all aligned slots until one is empty, while the short-term goal is to pick up all components from the aligned slots greedily. The current component assignment result is the short-term objective, and its effect on pick-up efficiency as a whole is the long-term objective. The long-short term objective is the weighted sum of these two.
|
||
\begin{algorithm}
|
||
\small
|
||
\caption{Long-short Term Objective Calculation}
|
||
\label{objective_algorithm}
|
||
\SetKwInOut{Input}{Input}\SetKwInOut{Output}{Output}
|
||
\SetKwProg{Fn}{function}{}{end}
|
||
|
||
\Input{Head Component Assignment $\mathcal{H}^{PT}$}
|
||
\Output{short-term objective $V_{s}$ and long-term objective $V_{l}$}
|
||
|
||
Initialize short-term objective $V_{s} \leftarrow 0$ and long-term objective $V_{l} \leftarrow - e_{2} \cdot \sigma$ \;
|
||
|
||
$V_{s} \leftarrow e_{1} \cdot \omega \cdot \min_{h^{\prime} \in H} \left\lbrace \mathcal{H}^{PT} \left( h^{\prime} \right) > 0 \right\rbrace - e_{2} \cdot \sigma$ where
|
||
$\omega = \left| H \right| - \left| \left\lbrace h^{\prime} \big| \mathcal{H}^{PT} \left( h^{\prime}\right) > 0, h^{\prime} \in H \right\rbrace \right| - 1 $ and
|
||
$\sigma = \sum_{h^{\prime} \in H} \left| \mathcal{N} \left( h^{\prime} \right) - \sum_{j \in J} j \cdot \xi_{\mathcal{H}^{CP} \left( h^{\prime} \right) \cdot j} \right|$ \;
|
||
|
||
\While {$\mathcal{H}^{PT} \left( h \right) > 0, \exists h \in H$}
|
||
{
|
||
$V_{l} \leftarrow V_{l} + e_{1} \cdot \omega \cdot \min_{h^{\prime} \in H} \left\lbrace \mathcal{H}^{PT} \left( h^{\prime} \right) > 0 \right\rbrace$ where
|
||
$\omega \leftarrow \left| H \right| - \left| \left\lbrace h^{\prime} \big| \mathcal{H}^{PT} \left( h^{\prime}\right) > 0, h^{\prime} \in H \right\rbrace \right| - 1 $ \;
|
||
$\mathcal{H}^{PT} \leftarrow \mathcal{H}^{PT} - \min_{h^{\prime} \in H} \left\lbrace \mathcal{H}^{PT} \left( h^{\prime} \right) > 0 \right\rbrace$ \;
|
||
\lForEach{$h^{\prime} \in H$}
|
||
{
|
||
$\mathcal{H}^{NZ} \left( h^{\prime} \right) \leftarrow \sum_{j \in J} j \cdot \xi_{\mathcal{H}^{CP} \left( h^{\prime} \right) \cdot j } $
|
||
}
|
||
}
|
||
\end{algorithm}
|
||
\subsection{PAP Sequence Heuristic Algorithm} \label{subsection_route}
|
||
The pick and placement routes schedule make up the PAP route schedule problem. In the case of the feeder allocation and component assignment are determined, the pick-up procedure calls for picking up components from each preset slot in a single direction on the feederbase. Algorithm~\ref{pap_seq_algorithm} shows the process of beam search, which is utilized to solve the placement route schedule problem by retaining multiple potentially optimal solutions based on greedy search. The placement process can be thought of as a constrained vehicle route schedule problem with capacity constraints and candidate placement points constraints imposed by the component assignment. The dynamic programming is employed to determine the placement sequence in each cycle, which is efficient with a limited number of placement points.
|
||
|
||
\subsection{Extension of the Proposed Algorithm}
|
||
The proposed algorithms show significant applicability expansion. First, the algorithm may balance the nozzle change and pick-up operations cost by modifying the parameter weights. Second, regardless of the number of linear-aligned heads, the technique may be utilized to achieve simultaneous pick-up. Even though the adjacent interval distance ratio between heads and slots is not always an integer, the approximate value also improves productivity by shortening the pick-up distance of the gantry. Finally, since the algorithm implementation is essentially a simulation of the picking process, it can be fine-tuned to offer a tailored solution, including but not limited to pre-assign feeders, assigning nozzle to head, and prohibiting feeder slots.
|
||
\begin{algorithm}
|
||
\small
|
||
\caption{PAP Sequence Heuristic}
|
||
\label{pap_seq_algorithm}
|
||
\SetKwInOut{Input}{Input}\SetKwInOut{Output}{Output}
|
||
\SetKwProg{Fn}{function}{}{end}
|
||
|
||
\Input{PCB data with coordinate $\left( X_{p}, Y_{p} \right)$ of point $p$, component assignment $\mathcal{C}$ and $\mathcal{K}$}
|
||
\Output{PAP sequence $\mathcal{P}$}
|
||
|
||
Initialize $B = \left\{ 1, 2, \cdots, \beta \right\}$ as beam set where $\beta$ is the beam width \;
|
||
Initialize $\mathcal{P}, \mathcal{P}_{b}$ as empty matrix and $\mathcal{T}_{b}$ as $1 \times \left| H \right|$ matrix, $\forall b \in B$\;
|
||
|
||
\For {$\mathcal{H}^{CP} \in \mathcal{C}$, $k \in \mathcal{K}$}
|
||
{
|
||
\While{$k \neq 0$}
|
||
{
|
||
Initialize $\beta \times 2$ matrix $\mathcal{W}$ as the coordinates of the $\beta$ leftmost unplaced points \;
|
||
\For {$h \in H$}
|
||
{
|
||
Select $\beta$ points which nearest to $\mathcal{W} \! \left( b \right)$, $\forall b \in B$ with component type $\mathcal{H}^{CP} \! \left( h \right)$ \;
|
||
|
||
Select $\beta$ points among $\beta^{2}$ candidates with minimal Chebyshev distance as $p_{1}, \! \cdots \!, p_{b}$ ;\
|
||
}
|
||
|
||
$k \leftarrow k - 1, \mathcal{W}_{b} \! \leftarrow \! \left[ X_{p_{b}}, Y_{p_{b}} \! - \! \left( h \! - \! 1 \right) \!\cdot \! \rho \right]$, $\mathcal{T}_{b} \left( h \right) \leftarrow p_{b}, \forall b \in B$ \;
|
||
|
||
PAP sequence schedule for $\mathcal{T}_{b}$ using dynamic programming and attach $\mathcal{T}_{b}$ to $\mathcal{P}_{b}$ with column direction, $\forall b \in B$\;
|
||
|
||
}
|
||
}
|
||
$\mathcal{P} \leftarrow \mathcal{P}_{b}$ with minimal Chebyshev distance $\forall b \in B$ \;
|
||
\end{algorithm}
|
||
|
||
\section{Experiment result analysis}\label{experiment_section}
|
||
|
||
%% === algorithms description %%
|
||
The algorithms proposed in this paper are implemented in Python 3.8 by a desktop computer with Intel Core i7 1.8-GHz CPU and compared with aggregation mix integer programming (AMIP)~\cite{ashayeri_aggregated_2011}, hybrid genetic algorithm (HGA)~\cite{geng_mcvrp-based_2019}, cell division genetic algorithm (CDGA)~\cite{li_cell_2021}, and optimizer integrated with an industrial software (ISO). Both HGA and CDGA are representatives of evolutionary algorithms for assembly optimization. AMIP, a mathematical programming technique combined with an aggregation technique, could optimize medium-sized data in an acceptable amount of time. All mathematical models mentioned in this paper are solved using the optimizer Gurobi~\cite{gurobi}.
|
||
|
||
%% === CMP1: with MIP model ===
|
||
Firstly, we compare the proposed algorithm with the optimal solution of the mixed integer model, as shown in Table~\ref{mip_comparsion}. Based on the production result, the coefficients $t_c$, $t_n$, $t_p$, and $t_m$ of the MIP model are set to 2, 6, 1, and 0.1, respectively. As the size of the problem increases, the model becomes less capable of solving the small-scale data in Table~\ref{mip_comparsion}. However, the solving efficiency of the proposed heuristic algorithms is substantially better than mathematical planning methods with an optimality gap of 9.93\% average.
|
||
|
||
%% === CMP2: with other studies ===
|
||
Secondly, we use several industrial PCB data, including a randomly generated complex one as representatives, to compare the result of different methods. The latter can be equated to a multi-batch PCB assembly scenario without feeder setup change. The comparative PCB data parameters are shown in Table~\ref{data_para_table}.
|
||
According to the machine parameters, we set $e = 0.5$, $e_{1} = 4$ and $e_{2} = 0.6$ in the implementation of the heuristic algorithms. We set the size of the beam in the beam search to half the number of placement heads. This research investigates the effects of the optimization technique without feeder pre-arrangement since AMIP, HGA, and CDGA cannot deal with pre-arrangement conditions, and
|
||
AMIP and HGA can only optimize single feeder type. The experiment findings indicate the suggested approach, ISO, AMIP, HGA, and CDGA, respectively, as $E^{i} \left(i =1,2,3,4,5\right)$. The performance improvement of the suggested approach over other methods is represented by the $\Delta E^{i}$, which is computed as
|
||
$ \Delta E^{i} = \left( E^{1} - E^{i} \right) / E^{1} \times 100 \%,i = 2,3,4,5 $.
|
||
|
||
\begin{figure}
|
||
\centering
|
||
\includegraphics[scale=1]{figures/platform.eps}
|
||
\caption{Experimental platform of the placement machine.}
|
||
\vspace{-0.2cm}
|
||
\label{experiment_platform}
|
||
\end{figure}
|
||
|
||
\begin{table}
|
||
\centering
|
||
\caption{The comparison of the proposed algorithms and the MIP model}
|
||
\label{mip_comparsion}
|
||
\begin{tblr}{
|
||
cells = {c},
|
||
cell{1}{4} = {c=2}{},
|
||
cell{1}{7} = {c=2}{},
|
||
hline{1,3,9,10} = {-}{},
|
||
hline{2} = {2,4-5,7-8}{},
|
||
}
|
||
& Scale & & Objective value & & & Comput. time & \\
|
||
PCB &$\left(N, C, P\right)$ & & $T_{{\rm scan}}$ & $T_{{\rm mip}}$ & Gap (\%) & $t_{{\rm scan}}$ & $t_{{\rm mip}}$ \\
|
||
1-1 & $\left(1, 1, 14\right)$ & & 4.735 & 4.408 & 7.42 & 0.29 & 323.60 \\
|
||
1-2 & $\left(2, 1, 14\right)$ & & 4.314 & 3.833 & 12.55 & 0.34 & 34.03 \\
|
||
1-3 & $\left(3, 2, 16\right)$ & & 4.095 & 3.886 & 5.83 & 0.20 & 984.10 \\
|
||
1-4 & $\left(4, 2, 20\right)$ & & 4.720 & 4.165 & 13.33 & 0.27 & 1117.84 \\
|
||
1-5 & $\left(5, 3, 24\right)$ & & 5.793 & 5.170 & 12.05 & 0.48 & 718.44 \\
|
||
1-6 & $\left(6, 3, 26\right)$ & & 6.257 & 5.773 & 8.38 & 0.59 & 5445.63 \\
|
||
AVG & & & & & 9.93 & &
|
||
\end{tblr}
|
||
\vspace{-0.2cm}
|
||
\end{table}
|
||
|
||
%% === main objectives comparison ===
|
||
This paper compares the main sub-objective values of optimization methods results with each other as shown in Table~\ref{objective_compare_table}.
|
||
The number of PAP cycles is one of the overall performance sub-objectives since, in some cases, it may affect the distance of the moving route. The method proposed in this paper exhibits more effective search capabilities when dealing with complex data.
|
||
|
||
Algorithm verification is done on our placement machine platform, which is shown in Fig.~\ref{experiment_platform}. We convert the assembly time into the standard time-chip per hour (CPH) to provide a straightforward comparison independent of the number of placement points. A batch of PCBs is subjected to each procedure three times, and Table~\ref{cph_compare_table} shows the average assembly time. Even though the proposed algorithm does not significantly outperform the industrial customize optimizer results for small and medium-sized data, its advantages become more evident as the size of the problem increases. The assembly efficiency distribution shown in Fig.~\ref{mounting_time_comparison} shows that the proposed algorithm is more stable than others.
|
||
|
||
\begin{table}
|
||
\centering
|
||
\setlength{\tabcolsep}{2.3mm}
|
||
\caption{PCB data parameters}
|
||
\begin{tabular}{ccccccccc}
|
||
\hline
|
||
PCB & 2-1 & 2-2 & 2-3 & 2-4 & 2-5 & 2-6 & 2-7 & 2-8 \\
|
||
\hline
|
||
$N$ & 1 & 1 & 2 & 3 & 3 & 3 & 3 & 4 \\
|
||
$C$ & 7 & 18 & 6 & 7 & 16 & 20 & 24 & 41 \\
|
||
$P$ & 564 & 176 & 72 & 192 & 114 & 150 & 236 & 1510 \\
|
||
\hline
|
||
\end{tabular}
|
||
\vspace{-0.2cm}
|
||
\label{data_para_table}
|
||
\end{table}
|
||
|
||
\begin{table}
|
||
\centering
|
||
\caption{sub-objective comparison}
|
||
\setlength{\tabcolsep}{1.5mm}
|
||
\renewcommand\arraystretch{1.1}
|
||
\begin{threeparttable}
|
||
\begin{tabular}{cccccc}
|
||
\hline
|
||
PCB & ISO & AMIP & HGA & CDGA & OUR \\
|
||
\hline
|
||
2-1 & 94,0,444\tnote{1} & 95,0,490 & 420,0,444 & 94,0,432 & 95,0,490\\
|
||
2-2 & 30,0,56 & 30,0,115 & 36,0,54 & 40,0,86 & 30,0,52\\
|
||
2-3 & 16,0,22 & 16,0,48 & 16,0,16 & 16,0,24 & 16,0,22\\
|
||
2-4 & 32,1,74 & 38,0,122 & 64,0,80 & 48,0,80 & 32,1,64\\
|
||
2-5 & 20,0,37 & 20,0,78 & 24,0,30 & 24,0,30 & 20,0,30\\
|
||
2-6 & 26,2,98 & 32,2,94 & 33,0,108 & 81,3,84 & 32,0,96\\
|
||
2-7 & 42,1,68 & - & 46,0,62 & 44,4,102 & 45,0,64\\
|
||
2-8 & 290,9,552 & - & 370,0,425 & 280,9,812 & 288,2,440\\
|
||
\hline
|
||
\end{tabular}
|
||
\begin{tablenotes}
|
||
\footnotesize
|
||
\item[1] The comma-separated values represent the sub-objectives of the number of cycles, nozzle changes, and pick-ups, respectively.
|
||
\end{tablenotes}
|
||
\end{threeparttable}
|
||
\vspace{-0.4cm}
|
||
\label{objective_compare_table}
|
||
\end{table}
|
||
|
||
\begin{table}
|
||
\centering
|
||
\caption{Chip per hour for different methods}
|
||
\setlength{\tabcolsep}{0.9mm}
|
||
\renewcommand\arraystretch{1.1}
|
||
\begin{tabular}{cccccccccc}
|
||
\hline
|
||
& OUR & \multicolumn{2}{c}{ISO} & \multicolumn{2}{c}{AMIP} & \multicolumn{2}{c}{HGA} & \multicolumn{2}{c}{CDGA} \\
|
||
PCB & $E^{1}$ & $ E^{2}$ & $\Delta E^{2} $ & $E^{3}$ & $\Delta E^{3} $ & $E^{4}$ & $\Delta E^{4}$ & $ E^{5} $ & $\Delta E^{5} $ \\
|
||
\hline
|
||
2-1 & 11297 & 11255 & 0.37 & 6991 & 61.60 & 7035 & 60.35 & 10673 & 5.84 \\
|
||
2-2 & 16058 & 16003 & 0.35 & 11460 & 40.21 & 14958 & 7.36 & 12462 & 28.86 \\
|
||
2-3 & 12451 & 11998 & 3.78 & 9231 & 34.88 & 12191 & 2.13 & 11759 & 5.88 \\
|
||
2-4 & 13658 & 12869 & 6.13 & 11404 & 19.76 & 9795 & 39.43 & 10423 & 31.03 \\
|
||
2-5 & 13375 & 13022 & 2.72 & 9932 & 34.67 & 12346 & 8.34 & 11372 & 17.62 \\
|
||
2-6 & 12903 & 11627 & 10.97 & 8843 & 45.91 & 10457 & 23.39 & 7556 & 70.76 \\
|
||
2-7 & 13043 & 12087 & 7.92 & - & - & 12087 & 7.92 & 9830 & 32.69 \\
|
||
2-8 & 13557 & 11835 & 14.55 & - & - & 11781 & 15.08 & 10477 & 29.40 \\
|
||
\hline
|
||
AVG & & & 5.85 & & 39.49 & & 20.50 & & 27.76 \\
|
||
\hline
|
||
\end{tabular}
|
||
% \vspace{-0.4cm}
|
||
\label{cph_compare_table}
|
||
\end{table}
|
||
|
||
The search efficiency is compared with other methods in Table~\ref{mounting_time_comparison} except for the built-in industrial customize optimizer. It can be seen that evolutionary-based algorithms take a longer time to find a solution, and the results are usually unstable due to their random exploration. AMIP is still intractable for large scale PCB-data, despite the efficient aggregate-based technique incorporated.
|
||
|
||
The feeder allocation has a pivotal impact on the overall assembly efficiency, but only some researchers elaborate on the solution to the feeder types with different widths. We conduct comparative tests with PCB data using different width feeders to compare the suggested approach with the ISO method. According to Table~\ref{cph_comparison_different_feeder}, the proposed method provides a 7.60\% overall efficiency gain over the industrial customize optimizer.
|
||
|
||
\begin{figure}
|
||
\centering
|
||
\includegraphics[scale=0.3]{figures/cph_trend_comparison.eps}
|
||
\caption{Mounting time(CPH) distribution.}
|
||
\vspace{-0.4cm}
|
||
\label{mounting_time_comparison}
|
||
\end{figure}
|
||
|
||
\begin{table}
|
||
\centering
|
||
\caption{Time-consuming of different methods}
|
||
\setlength{\tabcolsep}{3.2mm}
|
||
\renewcommand\arraystretch{1.1}
|
||
\begin{tabular}{ccccc}
|
||
\hline
|
||
PCB & AMIP & HGA & CDGA & OUR \\
|
||
\hline
|
||
2-1 & 1.54 & 646.96 & 221.27 & 3.93 \\
|
||
2-2 & 0.83 & 159.27 & 23.61 & 2.31 \\
|
||
2-3 & 0.66 & 29.93 & 4.37 & 0.73 \\
|
||
2-4 & 1.26 & 136.48 & 6.30 & 1.05 \\
|
||
2-5 & 2.83 & 82.18 & 13.97 & 1.17 \\
|
||
2-6 & 13.92 & 129.21 & 20.74 & 3.47 \\
|
||
2-7 & - & 215.43 & 40.06 & 5.20 \\
|
||
2-8 & - & 635.00 & 171.89 & 23.25 \\
|
||
\hline
|
||
AVG & - & 94.21 & 204.65 & 11.93 \\
|
||
\hline
|
||
\end{tabular}
|
||
\vspace{-0.4cm}
|
||
\label{time_compare_table}
|
||
\end{table}
|
||
|
||
|
||
\begin{table}
|
||
\centering
|
||
\caption{Chip Per Hour for Different Methods With Multi-width feeders}
|
||
\renewcommand\arraystretch{1.1}
|
||
\setlength{\tabcolsep}{3.2mm}
|
||
\label{cph_comparison_different_feeder}
|
||
\begin{tblr}{
|
||
cells = {c},
|
||
cell{1}{2} = {c=3}{},
|
||
cell{1}{6} = {c=3}{},
|
||
hline{1,3,8-9} = {-}{},
|
||
hline{2} = {2-4,6-8}{},
|
||
}
|
||
& Parameter & & & & Objective value & & \\
|
||
PCB & $P$ & $C$ & $N$ & & $E^1$ & $E^2$ & $\Delta E^2$ \\
|
||
3-1 & 78 & 16 & 3 & & 10912 & 10688 & 2.06 \\
|
||
3-2 & 150 & 20 & 3 & & 8493 & 8229 & 3.11 \\
|
||
3-3 & 110 & 23 & 3 & & 13001 & 12811 & 1.46 \\
|
||
3-4 & 161 & 38 & 3 & & 11143 & 8798 & 21.04 \\
|
||
3-5 & 540 & 10 & 4 & & 8416 & 7548 & 10.31 \\
|
||
AVG & & & & & & & 7.60
|
||
\end{tblr}
|
||
\vspace{-0.4cm}
|
||
\end{table}
|
||
|
||
\section{Conclusion}
|
||
The scan-based hierarchical heuristic algorithm demonstrates excellent performance and efficient search in solving the complex surface mount optimization problem. We propose a mixed integer mathematical model and elaborately designed heuristic algorithms.
|
||
The component pick-up procedure inspires the techniques of feeder allocation and component assignment with linear-aligned heads. While the component assignment heuristic algorithm concentrates on multi-head pick-up, the heuristic feeder allocation approach emphasizes feeder allocation, increasing simultaneous pick-up numbers.
|
||
The ultimate goals of both algorithms are to improve pick-up efficiency and decrease nozzle change. In this work, beam search is used to improve the search quality of the PAP route schedule.
|
||
In terms of extension, the algorithm analyzes the requirements in various application scenarios and gives supporting solutions to be indeed applied to industrial production environments.
|
||
The experiments compare several previous research and an industrial optimizer, and the findings demonstrate that the suggested technique considerably increases the efficiency of placement machine assembly.
|
||
|
||
\bibliographystyle{IEEEtran}
|
||
\bibliography{Bibliography/BIB_xx-TII-xxxx}
|
||
|
||
\begin{IEEEbiography}[{\includegraphics[width=1in,height=1.25in,keepaspectratio]{author/Guangyu_Lu.jpg}}]{Guangyu Lu} was born in Taiyuan, China, in 1996. He received the B.E. degree in automation from Dalian Maritime University, Da’lian, China, in 2019. He is currently pursuing the Ph.D. degree in control science and engineering with the Harbin Institute of Technology, Harbin, China. His current research interests include production scheduling and combinatorial optimization.
|
||
\end{IEEEbiography}
|
||
|
||
\begin{IEEEbiography}[{\includegraphics[width=1in,height=1.25in,keepaspectratio]{author/Xinghu_Yu.eps}}]{Xinghu Yu} (Member, IEEE) was born in Yantai, China, in 1988. He received the M.M. degree in osteopathic medicine from Jinzhou Medical University, Jinzhou, China, in 2016, and Ph.D. degree in control science and engineering from the Harbin Institute of Technology, Harbin, China, in 2020. He is currently the Chief Executive Officer with the Ningbo Institute of Intelligent Equipment Technology Company, Ltd., Ningbo, China. He has authored more than 30 technical papers for refereed international journals and conference proceedings, including IEEE Transactions journals, and holds more than 20 invention patents. His research interests include advanced control, intelligent systems, and biomedical image processing.
|
||
\end{IEEEbiography}
|
||
|
||
\begin{IEEEbiography}[{\includegraphics[width=1in,height=1.25in,keepaspectratio]{author/Hao_Sun.eps}}]{Hao Sun} received the B.E. degree in automation from the Shandong University of Science and Technology, Qingdao, China, in 2011, and the M.S. degree in control theory and engineering and the Ph.D. degree from the Harbin Institute of Technology, Harbin, China, in 2013 and 2020, respectively. His research interests include image processing, computer vision, pattern recognition, machine learning, and visual servo. Dr. Sun is currently carrying out his postdoctoral research with the School of Computer Science and Technology, Harbin Institute of Technology, Shenzhen, China.
|
||
\end{IEEEbiography}
|
||
|
||
\begin{IEEEbiography}[{\includegraphics[width=1in,height=1.25in,keepaspectratio]{author/Zhengkai_Li.eps}}]{Zhengkai Li} (Member, IEEE) was born in Jinan, China, in 1991. He received the B.E. degree in detection, guidance, and control technology and the M.E. degree in control engineering from Northwestern Polytechnical University, Xi’an, China, in 2013 and 2016, respectively. He also received the Ph.D. degree in control science and engineering from the Harbin Institute of Technology, Harbin, China, in 2022. His current research interests include scheduling and systems optimization. Dr. Li is currently carrying out his postdoctoral research with the Department of Mathematics and Theories, Peng Cheng Laboratory, Shenzhen, China.
|
||
\end{IEEEbiography}
|
||
|
||
\begin{IEEEbiography}[{\includegraphics[width=1in,height=1.25in,keepaspectratio]{author/Jianbin_Qiu.eps}}]{Jianbin Qiu} (Senior Member, IEEE) received the B.Eng. and Ph.D. degrees in mechanical and electrical engineering from the University of Science and Technology of China, Hefei, China, in 2004 and 2009, respectively, and the Ph.D. degree in mechatronics engineering from the City University of Hong Kong, Kowloon, Hong Kong, in 2009, He is currently a Full Professor with the School of Astronautics, Harbin Institute of Technology, Harbin, China. He was an Alexander von Humboldt Research Fellow with the Institute for Automatic Control and Complex Systems, University of Duisburg-Essen, Duisburg, Germany. His current research interests include intelligent and hybrid control systems, signal processing, and robotics. Dr. Qiu is the Chairman of the IEEE Industrial Electronics Society Harbin Chapter, China. He is an Associate Editor for IEEE Transactions on Cybernetics.
|
||
\end{IEEEbiography}
|
||
|
||
|
||
\begin{IEEEbiography}[{\includegraphics[width=1in,height=1.25in,keepaspectratio]{author/Huijun_Gao.eps}}]{Huijun Gao} (Fellow, IEEE) received the Ph.D. degree in control science and engineering from the Harbin Institute of Technology, Harbin, China, in 2005. From 2005 to 2007, he was Postdoctoral Researcher with the Department of Electrical and Computer Engineering, University of Alberta, Edmonton, AB, Canada. Since 2004, he has been with the Harbin Institute of Technology, where he is currently a Chair Professor and the Director of the Research Institute of Intelligent Control and Systems. His research interests include intelligent and robust control, robotics, mechatronics, and their engineering applications. Dr. Gao is currently a Member of Academia Europaea and a Distinguished Lecturer of the IEEE Systems, Man and Cybernetics Society. He is also the Vice President of the IEEE Industrial Electronics Society and a Council Member of the International Federation of Automatic Control (IFAC). He is or was the Editor-in-Chief of the IEEE/ASME TRANSACTIONS ON MECHATRONICS, the Co-Editor-in-Chief of the IEEE TRANSACTIONS ON INDUSTRIAL ELECTRONICS, and an Associate Editor for the Automatica, IEEE TRANSACTIONS ON CYBERNETICS, and IEEE TRANSACTIONS ON INDUSTRIAL INFORMATICS.
|
||
\end{IEEEbiography}
|
||
|
||
\end{document}
|