Optimizing the Operation Sequence of a Multihead Surface Mounting Machine Using a Discrete Particle Swarm Optimization Algorithm

1. Introduction

The optimization of feeder setup and component placement sequences is very important to the efficiency of a surface mount machine (SMM). The increase of the number of components to be placed on a single board has made the reduction of assembly time probably the most important issue to further cut down production costs and increase productivity. The assembly of printed circuit board (PCB) on a production line can be divided into four process-planning subproblems: grouping (i.e., assigning PCB types to product families and to machines), allocation (i.e., assigning nozzles to the heads), arrangement (i.e., assigning reels to slots on the feeder rack), and sequencing (i.e., the components′ pick-and-place operations). Many publications have been devoted to these complex optimization subproblems, and various models and techniques have been presented, for example, by Ball and Magazine [1] and Brad et al. [2]. These subproblems are tightly intertwined, and each of them is very difficult to solve to optimality. For example, the quality of a component pick-and-place sequence is dependent on the feeder setup and vice versa [2]. Various approaches have been proposed to improve sequence of placement points and/or feeder assignment for the PCB assembly process [3]. Egbelu et al. [4] investigated assigning components to feeder slots and sequencing component placement onto the PCB in order to minimize the total assembly cycle time. They classified machines depending upon whether the PCB table and the feeder carrier were stationary or not. They developed rules such as the centroid rule, the proportion rule, the partition rule, and the weighted rule to initially assign components to feeder slots. To obtain the component insertion sequence, they modeled the problem as a traveling salesman problem (TSP). Finally, by having the component insertion sequence and the initial feeder setup, Egbelu et al. [4] converted the component slot assignment into a quadratic assignment problem (QAP) where the cutting plane and exchange heuristic were used. Results showed that the assembly cycle times were minimized when both the feeder rack and PCB table were able to move (Egbelu et al. [4]). Some researchers (see, e.g., [5]) have tackled the subproblems independently but also have some researchers (see, e.g., Ho and Ji [6] ) preferred to solve these subproblems in an integrated way. The literature is rich with work that has tackled this subject, especially investigating how to improve the efficiency of SMM [7, 8]. The technological characteristics of the SMM can also influence the nature of some of the subproblems to be solved and the formulation of the associated models [9]. As a result, many researchers solved the problem as a unique problem since the problem relies heavily on the machine characteristics (Ho and Ji, 2003). This causes difficulties in applying or comparing the various approaches from the literature.

In the recent years, a heuristic approach was developed to solve the subproblems. Genetic algorithms (GAs) have been applied successfully to a wide variety of optimization arrangement/sequencing problems [10]. The GA and its many versions have been popular in academia and the industry mainly because of their intuitiveness, ease of implementation, and the ability to effectively solve highly nonlinear, mixed integer optimization problems that are typical of complex engineering systems. The drawback of the GA is its expensive computational cost. Particle swarm optimization (PSO), introduced by [11] is a relatively recent heuristic search method whose mechanics are inspired by the swarming or collaborative behavior of biological populations. PSO is similar to the GA in the sense that these two heuristics are population-based search methods. In other words, PSO and the GA move from a set of points (population) to another set of points in a single iteration with likely improvement using a combination of deterministic and probabilistic rules. Critical ingredients for the success of PSO are simplicity, ease of operation, and great flexibility.

When the SMM has more than one nozzle per head (or even a single nozzle per head), choosing an effective nozzle group (or a nozzle) is important since a nozzle change operation is time consuming. Optimizing the pick and place operations without considering the nozzles changing operations may not be efficient since it may cause many unnecessary nozzle changes that will significantly reduce the machine throughput. However, to date, only a few researchers [3] have tackled the nozzle optimization problem. Due to its global and local exploration abilities, simplicity in coding and consistency in performance, PSO has been widely applied in many fields beyond its original applications to the solution of continuous optimization problems. In our research, we mainly use discrete data to process SMM problems. Therefore, developing a mechanism to realize discrete optimization problem is attractive. Hence, in this paper, we develop a discrete particle swarm optimization (DPSO) algorithm for nozzles selection and sequencing components pick and place operations in a SMM equipped with multiple placement heads. The objective of the algorithm is to minimize the nozzle selection for sequencing component pick and place operations so as to increase the machines throughput.

The organization of this paper is as follows. Section 2 is a description of the SMM problem and its assumptions. In Section 3, we propose a DPSO algorithm for multihead SMM which is used to minimizing the nozzle changes and minimizing the pick and place operations. The fourth section discusses the experiment results we have gained for the heuristics described in this paper applied to 10 test print circuit boards of SMM. The last section covers the conclusions we have drawn from this research and gives a brief overview of planned future research.

2. SMM Description and Assumptions

3. Discrete Particle Swarm Optimization Algorithms

PSO is inherently continuous but recently the discrete particle swarm optimization algorithm has been proposed to solve discrete problems successfully. Ucar and Tasgetiren [12] proposed a discrete particle swarm optimization algorithm to determine a sequence of n jobs to be processed through m machines that minimizes the number of tardy jobs. Other papers proposing discrete particle swarm optimization algorithms can be found in Shen et al. [13], Tasgetiren et al. [14], Onwubolu [15], and Clerc [16].

Since, for each printed circuit board, the location of each component has been decided, the critical decisions left for optimization are where the different reel groups should be placed in feeder slots. Moreover, in the multihead case, the optimal solution does not only require the local optimization of a single head but also the global optimization of the head group. In addition, there is only a finite number of feeder slots, and each feeder slot can only contain one reel of component(s). These properties match the properties of particle swarm optimization that is why we propose the DPSO algorithms to solve the SMM′s arrangement/sequencing problems.

Considering the characteristics of the multihead case, we decompose the component arrangement/sequencing problem into three phases: assignment of reels to heads, construction of reel-groups, and the assignment of component placement. In phase I, heads assignment algorithm, the most critical decision is to assign jobs to each head with a balanced loading simultaneously. Therefore, in order to balance the loading of each head, first, we construct a head-nozzle relative matrix; then, an algorithm is developed to minimize the variance of component loadings on each head based on the component types and their associated nozzle types to produce an optimal solution of head assignment.

3.3. Phase III: DPSO for Assignment of Component Placement

In Phase III, the assignment of component placement based on particle swarm optimization approach is developed in order to minimize the total time of pick-and-place calculated by the traveling distances, one dimension Euclidean distance times the unit assembly time in the entire process. The discrete particle swarm optimization (DPSO) approach is used to search the optimal locations for the reel group. Since the number of feeder slots in each surface mounting machine is finite and discrete, each particle cannot fly outside the range of feeder rack, that is, the position of each particle is constrained. In order to satisfy these constrains, the V _max velocity update equation is used in this case, and the maximum velocity which each particle can fly is calculated as the half of the number of feeder slots. Furthermore, Zhang et al. [17] proposed a new boundary handling method, which is called as “periodic mode.” It provides an infinite search space for the flying of particles, which is composed of periodic copies of original search space with same fitness landscape. Since each feeder slot can only contain one reel, some modification on the position update equation with boundary constraints handling should be made to protect against infeasibility.

In this phase, assignment of component placement, the fitness is determined as follows.

$$ ()

where P(N(the last change for this pick-up) denotes the last position of associated nozzle type needed to changed in this pickup sequence.

$$ ()

where P(reel_group_i(j, 1)) denotes the position of component assigned to head 1 in the reel group i of jth row on the print board.

$$ ()

$$ ()

$$ ()

$$ ()

$$ ()

where P(N(i)) denotes the position of nozzle type i.

$$ ()

The algorithm for component placement is given below.

Step 1.1. An individual particle of reel groups is randomly assigned to a feeder rack, and an initial solution based on the optimal assignment of reel groups from Algorithm II is generated according to the fitness function:

$$ ()

where 1 ≤ i ≤ Opt_No_Reel_Group,  1 ≤ j ≤ Row(i), and Row(i) denotes the number of rows in reel group i, 1 ≤ k ≤ No_of_Heads.

Step 2.2. Run the iterations of population with the following update equation.

• (i)

  Update the velocity with maximum velocity, V _max , constrained within the range of feeder rack. The velocity update equation is influenced simultaneously by the individual′s experience and neighbor′s experience as follows:

  $$ ()
  $$
  $$
  where w is the inertia weight in the range [0, 1], the cognitive parameter c₁ ∈ [0.5, 2], and the social parameter c₂ ∈ [1, 3].

• (ii)

  Update the particle′s position using the new velocity:

  $$ ()

• (iii)

  If the reel allocation is out of boundary, then a boundary constraint handling modification on position updating is made as the follows:

  $$ ()
  If the reel allocation is infeasible, then go to (i) again.

Step 3.3. Based on the fitness function, update P_id and P_gd.

Step 4.4. Repeat Steps 2 and 3 until the stopping criterion is met.

Figure 2 shows the flowchart of the DPSO for optimization of the operation sequence placement in multiheaded SMM.

4. Experiment Results

According to the DPSO approach proposed in Section 3, even though we only considered one machine to one printed circuit board, there are many possibilities of combination of processing procedures. Depending on what nozzle is assigned to what head or what component is assigned to what reel of each head different solutions will emerge. In this section, we consider a practical SMM that has 3 heads for a 300 × 250  mm² board. In order to emphasize the effectiveness of DPSO, we made a comparison of the standard PSO approach with our DPSO approach according to the quality of solution found. This is measured by the optimal solution found, the average traveling time (unit assembly time), the improvement percentage, and paired t-test for significance. The computer simulation is performed in the operating environment of Window XP Professional with Pentium III CPU, 846 MHz, 1 GB RAM. The software was coded in MATLAB 7.0.

Since the exhaustive examination of the quality of solutions requires a large number of problems, the algorithm is tested on a set of randomly generated problems. The component locations on the print board are randomly determined. In these simulations, both DPSO and the standard PSO use the same parameters. Namely, the population size is 10, and the relative parameters of velocity update equation, the cognition parameter c₁, and the social parameter c₂ are set equal to 2 to result in the most effective search of the problem domain [11]. Furthermore, a linear decreasing inertia weight w is used in this simulation.

To illustrate the performance of this meta-heuristic approach, the number of placements and component types ranged between 21 and 210 components to be placed and of up to 34 different component types. Tables 1 and 2 show the results of 10 different PCB boards with 20 runs with a different random seed for each problem case.

From Table 1, it is easy to see that the DPSO outperforms the standard PSO in every case; particularly, as the number of components increased, the difference in performance is more significant. Moreover, with the reversed modification of boundary handling in (15), the CPU time needed to search the optimal solution through DPSO is a little shorter than the time taken by the standard PSO, as shown in Table 2.

It shows that DPSO outperforms the standard PSO on the ability to find the optimal solutions, and the performance improvement is shown in Table 2. From the significance t-paired test, we also can see that the performance of DPSO is better than the performance of standard PSO in PCB component assignment/sequencing problems.

5. Conclusion

In this paper, we proposed a DPSO approach to solve the problem of minimizing the PCB assembly time and simultaneously optimizing assignment/sequencing problems for multiheaded SMM. We decomposed the DPSO approach into three phases: heads assignment algorithm, reel grouping optimization, and the assignment of component placement. These results lead to minimize the total assembly time of assignment/sequencing time of the placement of component on PCB board. From the experiment results, the DPSO outperforms the standard PSO in the quality of the solution found and in the time taken to search for the optimal solution.

In this paper, we only discuss the application of DPSO in a SMM. But, it is easy to modify the DPSO approach for different applications including the consideration of component placement for multiple printed circuit boards operation simultaneously and with time limitation on operations. In addition, the different parameter selection for the DPSO and different velocity updating equation selection applied in DPSO can be compared and considered.