Restrictions of placement machine

To generate an efficient schedule for the placement machine in this study, the following restrictions were considered:

1. (1) Component height: The component heights are different. To avoid collisions with already installed components, components with lower heights should be placed with higher priority.

2. (2) Nozzle setup: Components with different shapes require nozzles with the corresponding shapes, but changing the nozzles increases production time and cost.

3. (3) Picking restrictions: The moving distance of each head is practically limited. For example, in Figure 2a, b, heads 3–8 cannot reach components in slot c, and heads 1–2 cannot pick components in slot d, respectively.

4. (4) Placing restrictions: Not all heads can place components in all slots. For example, in Figure 3a, heads 7–8 cannot place components at position a, and in Figure 3b, heads 1–2 cannot place components at position b.

5. (5) Simultaneous pickup restrictions: Simultaneous pickup is essential for reducing the number of pickups and therefore production time. The following conditions are necessary for simultaneous pickup:

   1. a. Components are stored in the tape feeder.

   2. b. One feeder slot between component feeders.

   3. c. Picking angles for all components are the same.

   4. d. The same camera is used for fly vision.

In the first run, eight heads, excluding heads #5 and #6, can simultaneously pick components R6, H2, M2, H3, M3, and H5 (Fig. 4a). In the second run, components H2 and M2 can be picked by heads #5 and #6 (Fig. 4b). The increased number of simultaneously picked components reduces the number of pickups required.

1. (6) Component shape restrictions: When a component is larger than 15 mm, it requires the space of more than one head. In such cases, the adjacent head cannot be used. In our example in Figure 5, the sizes for components V1 and V2 are 36 and 45 mm, respectively; therefore, heads #2, #4, and #6 are idle when heads #3 and #5 are used (Fig. 5).

Fig. 2.

Picking restrictions

Fig. 3.

Placing restrictions

Fig. 4.

Simultaneous pickups

Fig. 5.

Component shape restrictions

Problem statement

This study aimed to provide efficient scheduling with minimum production time for assembling PCBs. An interview with the site engineer responsible for the placement machine revealed that although the component positions in the feeders are not fixed, the arrangement seldom varies in practice. If the same components are used in different PCBs, their positions in the feeders are generally retained. The following three interacting problems are discussed herein:

1. (1) ANC assignment: component pick-and-place sequences interact with each other to enable determination of the optimal ANC.

2. (2) Nozzle assignment: The nozzle must be assigned by considering the pick, place, component height, and simultaneous pickup restrictions to reduce the number of pickups and nozzle changes, thereby reducing the total assembly time.

3. (3) Component pick-and-place sequence: The component pick-and-place sequence must be optimized so that head movement for pick-and-place operations uses the shortest path.

Problem formulation

Considering limitations in the practical operation of a multihead placement machine, a mathematical model is proposed for optimizing the total assembly time, which includes pick time, place time, and ANC time. Eq. (1) can be applied to minimize the total assembly time for PCB production.

(1)$$T_{{\rm total}} = \mathop \sum \limits_{c = 1}^{NC} (T_{{\rm pick}}(c))( + T_{{\rm place}} + T_{{\rm change}})$$

where T _total, T _pick, T _place, and T _change are the total production time for PCB assembly, total pick time, total placing time, and total nozzle change time, respectively. T _pick, T _place, and T _changeare given as follows:

(2)$$\eqalign{&T_{{\rm pick}} \cr &= \left\{ {\matrix{ {\mathop \sum \limits_{i = 1}^{NP-1} (T{\rm (}d{\rm (}S_i\comma \,S_{i + 1}{\rm )}) + T_z({\rm i} + 1) + {\rm T}{\rm D}_{i + 1} + {\rm T}{\rm P}_{i + 1})\;\comma \, \; \; c = 1} \cr {T(d({\rm P}{\rm C}_N\comma \,S_1)) + T_z(1) + {\rm T}{\rm D}_1 + {\rm T}{\rm P}_1 + } \cr {\mathop \sum \limits_{i = 1}^{NP-1} (T(d(S_i\comma \,S_{i + 1})) \!+\1 T_z(i + 1) \!+\! {\rm T}{\rm D}_{i + 1} \!+\! {\rm T}{\rm P}_{i + 1})\comma \,{\rm \;\ otherwise}} \cr}} \right.} $$

(3)$$\eqalign{T_{{\rm place}} & = T(d{\rm (}S_N\comma \,{\rm P}{\rm C}_1{\rm )}) + T_z(1) + {\rm T}{\rm B}_1 + {\rm T}{\rm L}_1 + \cr & \quad \mathop \sum \limits_{\,j = 2}^N (T{\rm (}d{\rm (P}{\rm C}_{\,j-1}\comma \,{\rm P}{\rm C}_j{\rm ))} + T_z({\rm j}) + {\rm T}{\rm B}_j + {\rm T}{\rm L}_j)} $$

(4)$$\eqalign{T_{{\rm change}} & = T({\rm d(}PC_N\comma \,A_1{\rm )}) + T(d(A_{CN}\comma \,S_1)) \cr & \quad + \mathop \sum \limits_{k = 1}^{{\rm CN}} ' {T(d{\rm (}A_k\comma \,A_{k + 1}{\rm )}) + {\rm T}{\rm N}_k} \rsqb } $$

where Min(T _total) indicates that the objective is to minimize the total assembly time; NC, N, and NP are the total number of cycles in the assembly, heads in the placement machine, and pickups in the assembly, respectively; and TD, TP, TB, and TN are the vacuum on delay time, total waiting time for picking components, total waiting time for placing components, load wait time, and total time for changing nozzles, respectively. Furthermore, CN is the total number of nozzle changes; PC is the component picking position; S is the position of the active slot; A is the position of nozzle change in the ANC; d() is the movement distance of the head; T() is the time required for head movement; andT _z(c) is the movement time in both directions along the Z axis.

Proportional distribution of nozzles to the ANC

During production, any head in the placement machine may require nozzle change to pick the subsequent component. The ANC has 20 cells, with 16 small and 4 large cells (Table 1). PCBs are different with different numbers of components. For efficient production, the nozzles must be assigned to the ANC before commencing operation. In this study, the nozzles were distributed to the ANC according to the number of pickups by each nozzle. Table 1 presents nozzle arrangement involving one large nozzle (ANV1) and four small nozzles (AN3, AN5, AN6, and AN7).

• Step 1: Ensure that at least one nozzle is assigned in the ANC to each component in Table 2, namely ANV1, AN3, AN5, AN6, and AN7.

• Step 2: Subtract the number of cells that have been occupied in step 1 (i.e., 20−5 = 15). Compute the number of nozzles required for each nozzle type (Table 3) according to the components to be picked up (Table 6).

• Step 3: Ensure that the number of nozzles assigned for each type is not higher than the number of heads. For example, if the number of nozzles assigned for type AN3 exceeds the number of heads, reduce the number of nozzles to the maximum number of heads (Table 4).

• Step 4: Repeat steps 2 and 3 until all cells in the ANC are occupied (Tables 5 and 6, Fig. 7).

Fig. 7.

Proportion of small nozzles

Table 1.

Nozzle arrangement in ANC

Table 2.

ANC arrangement step 1

Table 3.

Number of nozzles per type

Table 4.

Nozzle arrangement checklist

Table 5.

Final nozzle arrangement

Table 6.

Components per nozzle type

HGSO algorithm

To avoid collision during component placement, shorter components must be placed earlier. In the following example, components with a height of 0.6–2.6 mm (see Table 7) are grouped together and can be arbitrarily placed if height restriction is 2 mm.

Table 7.

Component information

A random number between 0 and 1 is generated and assigned to each member for executing the GSO algorithm (Table 8). N and x _i are the total number of components and the i ^th member in the GSO, respectively. Each member represents a scheduling solution.

Table 8.

Coding method for GSO members

The traditional GSO cannot be employed to schedule placement machines because this problem is a type of integer optimization. In this study, an MGSO with an added random key (Snyder and Daskin, Reference Snyder and Daskin2006) was proposed for scheduling optimization of PCB assembly. Tables 9–11 illustrates the procedure. The first random number in Table 9 is 0.95. Component 6 is assigned to the first cell after considering component height, component shape, nozzle assignment, and picking restrictions. In Table 10, the initial solution with random numbers in Table 9 is adjusted by placing the elements in an ascending order: 0.12, 0.15, 0.75, 0.76, 0.88, 0.93, 0.95, and 0.99. Element 0 is assigned to the lowest random number (0.12), element 1 is assigned to the subsequent number (0.15), and so on (Table 11). Table 12 presents the solutions for the large components, where head #3 and #5 are idle in the first cycle because component 9 occupies the space beneath them.

Table 9.

Initial solution: random numbers

Table 10.

Members arranged in ascending order

Table 11.

Final solution of members

Table 12.

MGSO of large components

The 2-opt method is employed to the solution of the initial path derived from Table 12. Table 13 presents the improved solution. A mathematical model that calculates the total assembly time is then applied to evaluate the performance of the probable solutions. Table 14 presents the final result.

Table 13.

The 2-opt method

Table 14.

Final scheduling results

Chaos local search

Chaos local search (Liu et al., Reference Liu, Wang, Jin, Tang and Huang2005), which is a new optimization technique, is applied to improve MGSO evolution performance. Chaos local search has several advantages for obtaining the initial solution, such as sensitivity and dependence, which ensure the diversity and appropriate search behavior of the entire space. The chaos search formula is as follows:

(5)$$x_{n + 1} = \mu \times x_n(1-x_n)\comma \,\; 0 \le x_0 \le 1$$

where μ and x are a control parameter and a random variable, respectively, with n = 0, 1, 2, … However, when μ = 4, x ₀{0, 0.25, 0.5, 0.75, 1} can be applied to Eq. (5). Chaos is sensitive and dependent on initial conditions, and a slight initial difference can generate considerable variances given a long enough timeframe. The MGSO searches the entire space by using particular characteristics of chaos [Eq. (6)]:

(6)$$cx_i^{(k + 1)} = 4cx_i^{(k)} (1-cx_i^{(k)} )\comma \,\; i = 1\comma \,\; 2\comma \,\; \ldots \ldots\comma \, N$$

where cx _i and k are a chaos variable and the number of iterations, respectively. $cx_i^{\lpar k \rpar } \; $ has a range of [0, 1] and satisfies${\rm \;} cx_i^{(0)} \in (0\comma \,1)$, $cx_i^{(0)} \not\subset \lcub {0.25\comma \,{\rm \;} 0.5\comma \,{\rm \;} 0.75} \rcub $. The procedure of chaos search is as follows:

1. Step 1: Use Eq. (6) to produce chaos variables for the subsequent generation.

   (7)$$cx_i^{(k + 1)}\comma \,cx_i^{(k)} = x_i$$

2. Step 2: Compare the new solution $cx_i^{(k + 1)} $ with the original solution $cx_i^{(k)} $. Use the more favorable solution.

   (8)$$x_i = cx_i^{(k + 1)} $$

3. Step 3: Repeat steps 1 and 2 until i = N.

Population manager

Because similar subjects have similar fitness values and converge to likely positions, the worse subjects must be eliminated to improve efficiency and reduce computation. Similarity is evaluated as follows (Liang and Lee, Reference Liang and Lee2015):

(9)$$\left \vert {\displaystyle{{\,f\,(x_i)-f\,(x_j)} \over {\,f\,(x_j)}}} \right \vert \lt \delta _{\rm m}{\rm \;\comma \,} \,{\rm \;} x_{\rm i}-x_{\rm j} \lt r_{\rm m}$$

where δ _m and r _m are threshold values, representing the average fitness value and average distance of the entire space, respectively; ${\left\Vert \cdot \right\Vert} $ denotes the distance betweenx _i and x _j. Figure 8 illustrates this concept. Subjects Q3 and Q4 have similar fitness values (less than δ _m); however, the distance is larger than r _m. The positions for Q5 and Q6 are close (less than r _m); however, the fitness values are considerably different. The fitness values and positions for Q1 and Q2 are similar, which satisfy Eq. (9), and the lower value (Q1) can be deleted.

Fig. 8.

Fitness value and position