Journal Search Engine
Search Advanced Search Adode Reader(link)
Download PDF Export Citaion korean bibliography PMC previewer
ISSN : 1598-7248 (Print)
ISSN : 2234-6473 (Online)
Industrial Engineering & Management Systems Vol.12 No.4 pp.330-335
DOI : https://doi.org/10.7232/iems.2013.12.4.330

Feeder Re-assign Problem in a Surface Mount Device with a Piano-Type Multi-Headed Gantry

Byung-In Kim*, Hyunchul Tae
Department of Industrial and Management Engineering, Pohang University of Science and Technology(POSTECH), Pohang, Korea
(Received: January 28, 2013 / Revised: September 16, 2013 / Accepted: November 14, 2013)

Abstract

A surface mount device (SMD) assembles electronic components on printed circuit boards (PCB). Since a componentassembly process is a bottleneck process in a PCB assembly line, making an efficient SMD plan is critical in increasingthe PCB assembly line productivity. Feeder assignment is an important part of the SMD plan optimization. In this paper,we propose a feeder re-assign improvement algorithm for a specific type of SMD machine with a piano type multi-headgantry. Computational results on some real-world benchmark data sets show the effectiveness of our proposed algorithm.

 

1. INTRODUCTION

 Surface mount technology (SMT) is a printed circuit board (PCB) assembly technology used in many electronics manufacturing factories. A typical SMT assembly line has three main processes: solder paste, components placement (assembly), and re-flow process. The components placement process is conducted by a set of surface mount device (SMD) machines which place the components on PCB. Time studies and simulation results on SMT factories consistently show that the components placement process is a bottleneck process, thus increasing the productivity of components placement process is critical in increasing the productivity of the SMT assembly line. Increasing the number of SMD machines is a direct way of increasing the productivity of components placement process, but the expensive unit price of the SMD machine makes it difficult for factory owners to buy new SMD machines (Tirpak, 1993). Instead, developing an efficient algorithm for the SMD optimization problem is an easier option for factory owners to increase the productivity of components placement process.

 The processing time of the components placement process can be divided into pick-up, place and nozzle change. In several previous papers that attempted to minimize the processing time, some authors (Sun et al., 2005; Wilhelm et al., 2006) focus on minimizing pick-up time, others (Duman and Or, 2004; Leipala and Nevalainen, 1989) focus on place time, and still others (Ayob and Kendall, 2004, 2005) focus on nozzle change time. In this paper, we propose a feeder re-assign improvement algorithm to minimize the pick-up time.

2. SMD MACHINE DESCRIPTION

 The nature of the SMD optimization problem is highly dependent on the characteristic of target SMD machine because the problem’s formulation, size, and complexity are determined by the SMD machine’s characteristic (Duman and Or, 2004). Thus, a tailored algorithm is required for each specific SMD machine type. In the current SMD market, there are many different types of SMD machines such as the single gantry system or dual gantry system, piano type or turret type and multi-headed or single-headed (Ayob and Kendall, 2008). This paper considers a specific SMD machine with a piano-type multi-headed single-gantry. Its schematic view is described in Figure 1.

Figure 1. A multi-headed piano-type surface mount device machine with a single-gantry. PCB: printed circuit board, ANC: automatic nozzle changer.

 Our target SMD machine has one gantry (singlegantry), which can move in x, y, z directions to pick and place components or change nozzles. The gantry has six heads (multi-head) and the gap between neighboring heads is 16 mm. Each head can pick and place a component one at a time if the head is equipped with a proper nozzle for the component. The nozzles are provided by an automatic nozzle changer (ANC), and a head can change its currently equipped nozzle with another one through the ANC. A component is provided by a feeder and the feeder should be assigned into a feeder slot. The SMD machine has one feeder base and the feeder base is constituted of sixty feeder slots.

 The SMD machine uses two types of feeders: tray feeder type and tape feeder type. Since the locations of the tray feeders are assumed to be fixed by users, we consider only tape feeders in this paper, and the word ‘feeder’ refers to ‘tape feeder’ from now on. The width of a feeder slot is 8 mm and each feeder slot has its own index from 1 to 60. Feeders have different widths, such as 8, 12, 16, and 24 mm depending on their component size while they have identical height length. Figure 2 describes feeders with different widths and how the feeders with different widths can be assigned into feeder slots. The pick-up point is the place where the gantry’s head picks up the component from the feeder. Note that all the feeders have the same y-coordinate of their pickup points.

Figure 2. Feeders with various widths.

 Our SMD machine can pick several components simultaneously from feeders. Wilhelm et al. (2006) called this kind of pick-up as “a gang pick.” The gang pick requires specific condition to happen. The gang pick is possible when the distances between the feeders of pick-up components are the same as the distances between the pick-up heads. Thus, the feeders should be arranged carefully in order to realize efficient pick-ups.

3. SMD OPTIMIZATION PROBLEM

 A PCB has placement points P = {p1, p2, …, pn} on its surface, and each placement point has its own x-y coordinates and component type ci ∈ C = {c1, c2, …, cm}. A component of type ci is provided by a feeder fdi, and there exists at least one feeder fdi for type ci. Note that in our case, there could be more than one feeder fdi for type ci. Every placement point on PCB should be placed with the proper component by the SMD machine. Since the SMD machine’s gantry has six heads, up to six components can be picked and placed by a single trip of the gantry. We call the trip “cycle”, denoted by l and a series of such cycles that fulfills the placement requirement completely a “SMD plan”, denoted by L = {l1, …, lk}.

 A cycle consists of three sequential steps of a gantry: nozzle change, components pick-up and components placement steps. The cycle time is the time required to complete the three steps of the cycle and equals to the sum of nozzle change time, components pick-up time, and components placement time. Nozzle change time is the time required to change the nozzles of the heads of a gantry. The nozzle change step can be skipped if nozzle change is not required for the cycle. Pick-up time means the required time of a cycle to pick components from feeders. The placement time is the required time of a cycle to place components onto the placements. The SMD plan time equals to the sum of cycle times of all the cycles in the SMD plan.

 An SMD optimization problem is the problem of finding the SMD plan and its corresponding feeder assignment with the minimum SMD plan cycle time. Since the SMD optimization problem is a hard combinatorial problem, many researchers have solved it by dividing it into sub-problems (Lee et al., 2000; Van Laarhoven and Zijm, 1993; Wilhelm and Tarmy, 2003). The SMD optimization problem can be divided into two major sub-problems: a feeder assigning problem and a cycle generation problem. The two sub-problems are highly related so one should solve the two sub-problems together to get the optimal solution of the SMD optimization problem.

 However, solving the two sub-problems together have never been attempted because the SMD optimization problem and sub-problems are hard combinatorial optimization problems, and taking the problems together is too difficult (Van Laarhoven and Zijm, 1993). Instead, sequential approaches have been used to solve the SMD optimization problems (Lee et al., 2000; Van Laarhoven and Zijm, 1993). A sequential approach is a method to solve a complicated problem by solving its sub-problems sequentially. For example, a solution for SMD optimization problem can be obtained by solving the feeder assignment problem first and then the cycle generation problem.

 The sequential approach promises the reasonable computational cost but its solution may be a local optimum. To overcome the local optimality, Grunow et al. (2004) adopted an improving method to the sequential approach. We solved the SMD optimization problem with the following consequent procedures as Grunow et al. (2004) did: 1) an initial feeder assignment procedure, 2) a cycle construction procedure, and 3) an improvement procedure. The initial feeder procedure aims to find feasible feeder assignment so that every placement can be placed. In this procedure, only one feeder for one component is allowed to be assigned into a feeder base even though the component has more than one feeder. With the assumption that every head can reach every placement and feeder slot’s pick-up point, this rule (one feeder for one component) does not cause infeasibility.

 The cycle construction procedure makes a series of cycles or a SMT plan based on initially assigned feeders with the minimum possible SMT plan time. This procedure constitutes four sub-problems: a placement point assignment problem, a feeder selection problem, a pickup sequencing problem, and a placement sequencing problem. The improvement procedure tries to improve the SMD plan with two procedures: a placement exchange procedure and a feeder re-assigning procedure. The placement exchange procedure tries to change placements within a cycle or between the cycles the SMD plan, and the feeder re-assigning procedure tries to change feeder positions or to assign duplicate feeders.

 Although this paper focuses on the feeder re-assignment problem, we explain the sub-problems of the cycle construction procedure since they are highly interrelated with the feeder re-assignment procedure. The placement point assignment problem assigns all placement points to a 6-column matrix (if a gantry has 6 heads) as an example is shown in Figure 3. In Figure 3, there are three matrixes, and each matrix denotes a SMT plan. Each plan has rows, and each row means a cycle, and the order of rows is the order of cycles in descending direction. Each column corresponds to a head, and the index of a column means the index of head.

Figure 3. Placement point assignment problem example.

 In Figure 3, there are three plans {L1, L2, L3} for two placement points P = {p1, p2}. The difference between plan L1 = {l1} and L2 = {l2, l3} is that L1 places P with one cycle {l1} while L2 does with two cycles {l2, l3}. Generally, L1 is more efficient than L2 . L3 = {l4, l5, l6} is infeasible plan because of its second row l2 has no placement point.

 The feeder selection problem selects a feeder for each placement point in the matrix. If a feeder base has only one feeder for one component, then this problem is trivial. But in reality, there might be several feeders for a component type, and in those cases, it is important to decide which feeder should be selected. The feeders in the upper right corner of the cells show the selected feeders in Figure 4.

Figure 4. Extended row with feeder selection, pick-up sequence and place sequence.

 The pick-up sequencing problem decides the pickup order of components from the selected feeders, and the placement sequencing problem decides the order of components placing onto the placement points. Both problems can be viewed as a travelling salesman problem with at most six stops, and the problems could be solved easily since they are small size problems. Note that our target SMD machine automatically decides both sequences. The numbers in the bottom left and bottom right corners of the cells in Figure 4 show the pick-up sequence and the placement sequence within a cycle, respectively.

4. PROPOSED ALGORITHM

 This paper aims to propose a feeder re-assignment algorithm. The feeder re-assignment algorithm of Grunow et al. (2004) tries to swap two feeders, and if the swap brings lower SMT plan time, it is accepted. They reported significant time reduction in SMT plan time by their simple 2-opt based improving algorithm. However, their approach has some limitations to be applied for our problem as explained below, so we propose a new feeder re-assignment algorithm.

 · Gang pick: Our target SMD machine can pick components simultaneously from a set of feeders while this is not allowed in Grunow et al. (2004). Sun et al. (2005) stated that the gang pick is critical in minimizing pick-up time. The gang pick requires specific condition to happen. Feeders need to be reassigned in proper distance in order to increase the number of gang picks.

 · Duplicate feeder: In the initial assignment procedure, only one feeder for one component is allowed to be assigned to feeder base as in Grunow et al. (2004). However, in our case, more than one feeder can be assigned if the additional feeders can reduce the pick-up time. Assigning duplicate feeders may decrease the gantry’s moving distance on the feeder base and increase the possibility of gang pick.

 A feeder assignment can be denoted by (s, F), where s is feeder start index or the lowest index of the feeder slot which has a feeder and F is a feeder arrangement. Feeder assignment in Figure 5 would be described as (25, {fd1, fd2, fd0, fd3, fd4, fd2, fd0, fd3}), where fdk means a feeder of component k or ck(k > 0) and fd0 means an empty feeder. A SMT plan L = {l1, l2, … , lm} is a series of cycles, where li means i-th cycle of plan L. Each cycle li = (li1, li2, li3, li4, li5, li6) is a set of head operations, where lij denotes an operation of j-th head in cycle li. Each head operation lij constitutes with four parts, such as chosen placement, chosen feeder, determined placement sequence, and pick-up sequence as shown in Figure 4. Our proposed algorithm is an improving algorithm so that an initial solution x0 = (s0, F0, L0) is assumed to be given where (s0, F0) is the initial feeder assignment and L0 is the initial SMD plan.

Figure 5. Feeder assignment example.

 The initial SMD plan L0 is the best plan under the feeder assignment (s0, F0). If we change feeder assignment from (s0, F0) to (s’, F’), then we need to change the initial plan L0 to L’, as fitted to (s’, F’). Procedure feederSelectOpt does this job, it changes a plan L to be fitted to a feeder assignment (s, F) considering feeder selection, pick-up and placement sequencing. Note that placement points are not re-assigned here even though it promises better result because solving placement point assignment problem requires expensive computational cost. Function feeders(lij) returns a set of feeder slot indices I = {3, 6, …} which have feeders with the same component type with a placement in lij. If lij has no placement then it returns {Ø}. Function setPick&Place Seq(li, s, F) optimally sets pick and placement sequence of head operations in cycle li based on the feeder arrangement (s, F). Function T(li, s, F) returns the time of cycle li based on (s, F) and T(L, s, F) returns the L’s SMD plan time based on (s, F).

 procedure feederSelectOpt(L, s, F)
   for i = 1 to |C| // |C| is the number of cycles in C
      for j = 1 to 6
           I = feeders(lij)
            for k = 1 to |I|
                 li’ = li;
                 let lij’ use feeder in feeder slot Ik;
                 setPick&PlaceSeq (li’, s, F);
                  if (T (li’, s, F) < T (li, s, F))
                     li = li’;

 Our proposed algorithm feederReAssignemntAlgorithm receives an initial solution (L0, s0, F0) and returns improved solution (L, s, F) with decreased SMT plan time. The proposed algorithm uses four sub-algorithms: feeder2Opt, emptyFeederInsertion, moveFeeders, feederAddition.

 procedure feederReAssignmentAlgorithm (L0, s0, F0)
    (L, S, F) = feederAddition (L0, s0, F0);
                                                //duplicate feeder addition
    (C, s, F) = feeder2Opt (C0, s0, F0);
    Repeat // Empty Feeder Insertion
        (C’, s’, F’) = (C, s, F);
        (C’, s’, F’) = emptyFeederInsertion (C’, s, F’);
        (C’, s’, F’) = moveFeeders (C’, s, F’);
        (C’, s’, F’) = feeder2Opt (C’, s, F’);
         if T(C, s, F) < T (C’, s’, F’)
               (C, s, F) = (C’, s’, F’);
   until T(C, s, F) == T (C’, s’, F’)
return (L, S, F);

 Procedure feeder2Opt is a simple 2-opt based algorithm which tries to change two different feeders, and if the change results in a lower plan time, it accepts the change. Note that changing empty feeder with non-empty feeder is possible. N2(F) denotes a set of feeder arrangement candidates by swapping two different feeders of F. The function feasiFd (s, F) return true if feeder assignment (s, F) is possible or false otherwise.

 procedure feeder2Opt (L, s, F)
     for each F’∈N2(F)
         if feasiFd (s, F’) is true
              L’= L;
              feederSelectOpt (L’, s, F’);
              if T(L’, s, F’) < T (L, s, F)
                  F = F’; L = L’;
            Restart for each loop;
         return (L, s, F);

 Procedure emptyFeederIinsertion tries to insert an empty feeder into the feeder arrangement to increase the possibility of gang picks. For example, if two 8-mm feeders are arranged right next to each other, then two feeders cannot be picked simultaneously because the feeders’ distance between pick-up points (8 mm) is smaller than the distance between heads (16 mm). However, by inserting an empty feeder between the feeders, the feeders can be picked simultaneously. Function insertFd( fd, F, i) inserts the feeder fd into i-th position of F and returns the inserted feeder arrangement.

 procedure emptyFeederInsertion (L, s, F)
     L* = L; F* = F;
     for i = 1 to |F| // |F| is the number of feeders in F
         F’= insertFd (fd0, F, i) 
      if feasiFd (s, F’) is true
         L’= L;
             feederSelectOpt (L’, s, F’);
             if T(L*, s, F*) > T(L’, s, F’)
                 L* = L’; F* = F’;
        return (L*, s, F*);

 Procedure moveFeeders attempts to find the best start point of the first feeder of the feeder arrangement F’ by moving feeders. Pseudo-codes of the proposed procedures are as follows.

 procedure moveFeeders (L, s, F)
     L* = L; s* = s;
     for s’ = 0 to 60
         if feasiFd (s’, F) is true
             L’= L;
     feederSelectOpt (L’, s’, F);
                   if T (L*, s*, F) > T (L, s’, F)
                       L* = L’; s* = s’;
     return (L*, s*, F);

 Procedure feederAddition tries to assign duplicate feeders into the feeder base. Assigning a duplicate feeder into the feeder base always promises less pick-up time. However, due to the limited number of feeder slots, not all feeders can be assigned. It is important to decide what kind of feeder to be added and where it is added. Let Csort be a sorted component types by the number of placements in descending order and Csort,i be a component which has i-th number of placements. Let x-avecord (c1) be a function which returns the average xcoordinate of placements with component type c1. Function idealIdx (x, fd) returns a feeder slot index to which feeder fd can be assigned and which is the closest to the coordinate of x. If there is no feeder slot to which the feeder can be assigned then it returns -1 as a sign of infeasibility.

 procedure feederAddition(L, s, F)
         Csort = a sorted C with the placement number
         Repeat
              for i = 0 to |Csort
      if there remains feeder of Csort, i 
         x-cord = x-avecord (ci);
         idx = idealIdx (x-cord, fdi);
         if idx is not -1
            F’= insertFd (fd0, L,)
            if feasiFd (s, F’) is true
               L’= L;
                   feederSelectOpt(L’, s, F’);
                     L = L’; F = F’;
     until impossible to add a feeder
 return (L, s, F);

5. COMPUTATIONAL RESULTS AND CONCLUSION

 Table 1 shows computational results of the proposed feeder re-assignment algorithm. The proposed algorithm was programmed in C++ language, and the computational test was performed on an Intel Dual Core E7300 2.66 GHZ 2.67 GHZ/4 GB RAM PC. Initial SMD plan (C0, s0, F0) is provided by the given construction algorithm of Tae and Kim (2013). The benchmark data were obtained from an anonymous SMD company in Korea. The computational results show that our proposed algorithm could improve the initial SMT plan by 1.68% on average.

Table 1. Computational result of proposed algorithm

 In this paper, we described an SMD optimization problem for a piano-type multi-head SMD machine. We briefly introduced its specific characteristics of the SMD, such as gang-pick. We proposed a feeder re-assign improvement algorithm based on feeder-move and feederchange. Our Computational results show the effectiveness of our proposed algorithm on some real-world benchmark data set.

iems_12-4_330_f1.jpg12.7KB

Reference

1.Ayob, M. and Kendall, G. (2004), A nozzle selection heuristic to optimise the hybrid pick and place machine, Proceedings of IEEE Conference on Cybernetics and Intelligent Systems, Singapore, 1260-1265.
2.Ayob, M. and Kendall, G. (2005), An on-line constructive heuristic to optimise the hybrid pick and place machine, School of CSIT, The University Of Nottingham, Nottingham, UK.
3.Ayob, M. and Kendall, G. (2008), A survey of surface mount device placement machine optimisation: machine classification, European Journal of Operational Research, 186(3), 893-914.
4.Duman, E. and Or, I. (2004), Precedence constrained TSP arising in printed circuit board assembly, International Journal of Production Research, 42(1), 67-78.
5.Grunow, M., Gunther, H. O., Schleusener, M., and Yilmaz, I. O. (2004), Operations planning for collectand- place machines in PCB assembly, Computers & Industrial Engineering, 47(4), 409-429.
6.Lee, S. H., Lee, B. H., and Park, T. H. (2000), A hierarchical method to improve the productivity of multihead surface mounting machines, Intelligent Automation and Soft Computing, 6(4), 291-301.
7.Leipala, T. and Nevalainen, O. (1989), Optimization of the movements of a component placement machine, European Journal of Operational Research, 38(2), 167-177.
8.Sun, D. S., Lee, T. E., and Kim, K. H. (2005), Component allocation and feeder arrangement for a dualgantry multi-head surface mounting placement tool, International Journal of Production Economics, 95(2), 245-264.
9.Tirpak, T. M. (1993), Simulation software for surface mount assembly, Proceedings of the 25th Conference on Winter Simulation, Los Angeles, CA, 796- 803.
10.Van Laarhoven, P. J. and Zijm, W. H. M. (1993), Production preparation and numerical control in PCB assembly, International Journal of Flexible Manufacturing Systems, 5(3), 187-207.
11.Wilhelm, W. E. and Tarmy, P. K. (2003), Circuit card assembly on tandem turret-type placement machines, IIE Transactions, 35(7), 627-645.
12.Wilhelm, W. E., Arambula, I., and Choudhry, N. N. D. (2006), Optimizing picking operations on dual-head placement machines, IEEE Transactions on Automation Science and Engineering, 3(1), 1-15.