A genetic algorithm approach to optimising component placement and retrieval sequence for chip shooter machines

A chip shooter machine in printed circuit board (PCB) assembly has three movable mechanisms: an X-Y table carrying a PCB, a feeder carrier with several feeders holding components and a rotary turret with multiple assembly heads to pick up and place components. In order to get the minimal placement or assembly time for a PCB on the machine, all the components on the board should be placed in a perfect sequence, and the components should be set up on a right feeder, or feeders since two feeders can hold the same type of components, and additionally, the assembly head should retrieve or pick up a component from a right feeder. The entire problem is very complicated, and this paper presents a genetic algorithm approach to tackle it.     

Grouping PCBs with Minimum Feeder Changes

In printed circuit board (PCB) assembly, the majority of electronic components are inserted by high-speed placement machines. Although the efficient utilization of the machinery is important for a manufacturer, it is hard to fully realize in high-mix low-volume production environments. On the machine level, the component setup strategy adopted by the manufacturer has a significant impact on the overall production efficiency. Usually, the setup strategy is formulated as a part type grouping problem or a minimum setup problem. In this article, we consider a hybridization of these two problems for the single machine case: The object function to be minimized includes a weighted sum of the number of part type groups (giving the number of setup occasions) and the number of feeder changeovers. We present algorithms for the problem and compare their efficiency.     

A genetic-based algorithm for the operational sequence of a high speed chip placement machine

Surface mount component placement machines are widely used in electronic manufacturing industry for automated placement of components on printed circuit boards. In this paper, we propose a new approach to the component placement problem using high speed turret style chip shooter machine and investigate the case of one single machine and one board type case with the objective of minimizing the assembly (cycle) time per board. The proposed method first groups the component types that can be processed at the same machine speed. Then the minimum spanning tree technique is employed to perform feeder duplications, reducing the distance effect between components of each type. Finally, a genetic-based algorithm with 2-opt local search using feeder arrangement list as solution representation is applied to determine the component placement sequence. Our experimental results indicate that the algorithm produces satisfactory solutions when a lower bound on cycle time per board is used as the evaluation criterion. It is also shown that the overuse of feeder duplication will produce a negative effect on the cycle time. Finally, the algorithm can help management to make a production plan that takes both component inventory cost and cycle time into consideration.     

The component retrieval problem in printed circuit board assembly

Minimization of the makespan of a printed circuit board assembly process is a complex problem. Decisions involved in this problem concern the specification of the order in which components are to be placed on the board and the assignment of component types to the feeder slots of the placement machine. If some component types are assigned to multiple feeder slots, an additional problem emerges: for each placement on the board, one must select the feeder slot from which the required component is to be retrieved. In this paper, we consider this component retrieval problem for placement machines of the Fuji CP type. We explain why simple forward dynamic programming schemes cannot provide a solution to this problem, invalidating the correctness of an algorithm proposed by Bard, Clayton, and Feo (1994). We then present a polynomial algorithm that solves the problem to optimality.The analysis of the component retrieval problem is facilitated by its reformulation as a PERT/CPM problem with design aspects: finding the minimal makespan of the assembly process amounts to identifying a design for which the longest path in the induced PERT/CPM network is shortest. The complexity of this network problem is analyzed, and we prove that the polynomial solvability of the component retrieval problem is caused by the specific structure it inflicts on the arc lengths of the network: in the absence of this structure, the network problem is shown to be NP-hard.     

Workload balancing in printed circuit board assembly

Line balancing of a printed circuit board (PCB) assembly line is considered in the present paper. The production line consists of a number of machines for inserting electronic components on bare PCBs. The aim is to distribute the assembly operations of a single PCB type to the different machines in such a way that the throughput (i.e., the number of finished PCBs per time unit) of the line is maximized. We suppose that the total time for placements is a linear function of the number of component insertions performed by a machine. Effective mathematical formulations of the balancing problem are then available but previous models omit several aspects having an effect on the actual placement times. In particular, we extend an existing MILP formulation of the problem to consider the usage of feeder modules, precedence constraints among the placement operations, and duplication of frequently used components in several machines. We consider production lines consisting of several gantry-type placement machines. Unlike previous research, we applied standard optimization tools for solving the balancing problems. We then observed that the CPLEX-software was able to solve MILP formulations of 2- and 3-machine problems with up to 150 different component types and relatively large number of component placements (from 400 to 6,000). On the other hand, the running time was rather unstable so that heuristics are still needed for cases where exact methods fail.     

Grouping PCB Assembly Jobs with Feeders of Several Types

A variant of the classical job grouping problem (JGP) in printed circuit board (PCB) assembly is considered. Studies on JGPs have assumed a single feeder from which the components are retrieved and then placed on the PCB. Recent advances in technology have made it possible to use several different kinds (types) of feeders at the same time. In a JGP, the aim is to group the PCBs so that the cardinality of the grouping is minimal and each group can be processed without rearranging the contents of the feeder. In the job grouping problem with several feeder types (JGP-T) the goal is the same but instead of one linear feeder we have several feeders and each component is associated with a given feeder type which restricts its placement. We give a mathematical formulation for the JGP-T and show that it is hard to solve to optimality for problems of practical size. The connections of JGP-T to known problems are discussed. We also propose several efficient heuristics and compare their results against optimal solutions.     

A rule-based frame system for concurrent assembly machines

The aim of this research is to develop a rule-based frame system for printed circuit board (PCB) assembly to generate the component feeder arrangement and placement sequence for concurrent chip placement machines. A knowledge base of frames, assertions and rules are used in the methodology to solve the PCB assembly process of SMT components. The system has been implemented using an AI programming environment, GOLDWORKS^®. A heuristic approach is used to minimize placement cycle time in PCB assembly. The objective of the solution method is to reduce theX-Y table displacement, movement and component feeder translation movement. Such a system is aimed at obtaining good solutions to the problem as illustrated by an example.     

Production preparation and numerical control in PCB assembly

In this article, we analyze numerical control problems arising in a component insertion line for printed circuit board mounting. Such a line consists of a number of fully automated placement machines, connected by an automated, carrierless conveyor system. At each machine, the placement device consists of an arm equipped with a number of placement heads. Each head may serve certain component types; there is some freedom in the choice of equipment for each head. Components are supplied to each machine by tape feeders (each containing components of only one type) which are placed at certain feeder positions along the machine. Before actually operating such a line, a careful production preparation phase has to be completed, specifying for each printed circuit board type the exact way in which such a board should be mounted. Problems arising in this production preparation phase include: the choice of heads to be mounted on the placement arm of each machine, the choice of components to be placed at each machine (workload balancing), an assignment of feeders to feeder positions on each machine, clustering of components to be placed in one pick-and-place move, and the sequencing of component insertions at one machine. Formulations and solutions for all these problems are given and numerical results for some industrial examples are given. The numerical control system developed has been tested and implemented and has resulted in software, which is in use at several sites of Philips' Electronics.     

Placement sequence identification using artificial neural networks in surface mount PCB assembly

The widespread use of automation in the printed circuit board (PCB) assembly domain has been dictated by the increasing density of components on PCBs coupled with the continual decrease in component lead pitch, greater product mix, smaller volumes, quality considerations, and the increased cost of labour. However, these advances in technology have also resulted in automated systems that are complex, and solving problems related to these systems requires the efficient use of extensive specialised knowledge.Expert (or knowledge-based) systems have become a widely accepted problem solving methodology for the surface mount PCB assembly domain. Nevertheless, problems in the PCB assembly domains are frequently unstructured, ill-defined, and difficult to communicate. Artificial neural networks provide a novel approach and an advanced technology to deal with the weaknesses and problems associated with expert systems.The surface mount component (SMC) placement process plays a vital and influential part in determining the throughput time of a PCB assembly line. It is important to identify an efficient component placement sequence while considering constraints such as feeder location and tooling and nozzle optimisation. This research studied the use of artificial neural networks as a complement to expert systems in PCB assembly. A prototype decision support system that combined the use of artificial neural networks and expert system techniques to identify a near optimal solution for the surface mount placement sequence problem was designed, implemented, and validated. Artificial intelligence based technologies such as expert systems and artificial neural networks were used in a mutually supportive manner to solve a complex problem within the surface mount PCB assembly domain.     

Component Partitioning Under Demand and Capacity Uncertainty in Printed Circuit Board Assembly

This paper considers the problem of configuring a printed circuit board (PCB) assembly line experiencing uncertainty in demand and capacity. The PCB assembly process involves a single line of automatic placement machines, a variety of board types, and a number of component types. The line is set up only once, at the beginning of a production cycle, to eliminate setups between board types. Using this strategy, the line therefore can assemble all different types of PCBs without feeder changes. The problem then becomes to partition component types to the different machines in the hope of processing all boards quickly with a good workload balance. In this paper, the board demands and machine breakdowns are random but follow some probability distribution, which can be predicted from past observations of the system. We formulate this problem as a stochastic mixed-integer programming formulation with the objective of minimizing the expected makespan for assembling all PCBs during a production cycle. The results obtained indicate significant improvement over the existing methods. We hope that this research will provide more PCB assembly facilities with models and techniques to hedge against variable forecasts and capacity plans     

Collision-free insertion of components on PCBs using spatial representation technique

This paper presents the technique for checking collision of through-hole components during the machine insertion process on a printed circuit board (PCB). The spatial representation technique is used to represent the components and the mounting head of an insertion machine. An algorithm that simulates the insertion process is written to detect any collision of component and mounting head during the insertion process. When a collision is detected, the algorithm will attempt to avoid the collision by re-sequencing the components concerned. If resequencing does not avoid the collision, the algorithm will compute a minimum safe distance for the affected component. The algorithm can also detect component collision due to components' space overlapping each other and subsequently can provide the minimum safe distance. The required safe spacing is based on the type of mounting head or machine used. The algorithm is a useful and efficient tool that could be used during the PCB design stage. The effectiveness of the spatial representation technique has been demonstrated using the TDK VC-544R/AR insertion machine.     

Setup reduction in printed circuit board assembly by efficient sequencing

Component setup time in printed circuit board (PCB) assembly makes up a significant part of the total production time in PCB manufacturing. The sequence in which PCBs are assembled is one of the fundamental factors determining the number of component switches that are needed. group technology techniques have been used to group PCB boards into similar groups to determine the assembly sequence. The measure of similarity is the key to the grouping problem. In PCB assembly, the similarity must be considered not only amongst different PCBs but must also taking into account the varying contents of the feeder rack on which the components are mounted in an incremental mode. In this paper, a new grouping strategy that combines the feeder rack contents into the similarity measure for efficient grouping is proposed. The groups of PCBs are then sequenced efficiently using a heuristic that resembles greedy tree traversal. The new grouping and group sequencing strategy outperforms existing methods of grouping particularly for large PCB component incidence matrices.     

Optimization of PCB component placements for the collect-and-place machines

This paper presents two hybrid genetic algorithms (HGAs) to optimize the component placement operation for the collect-and-place machines in printed circuit board (PCB) assembly. The component placement problem is to optimize (i) the assignment of components to a movable revolver head or assembly tour, (ii) the sequence of component placements on a stationary PCB in each tour, and (iii) the arrangement of component types to stationary feeders simultaneously. The objective of the problem is to minimize the total traveling time spent by the revolver head for assembling all components on the PCB. The major difference between the HGAs is that the initial solutions are generated randomly in HGA1. The Clarke and Wright saving method, the nearest neighbor heuristic, and the neighborhood frequency heuristic are incorporated into HGA2 for the initialization procedure. A computational study is carried out to compare the algorithms with different population sizes. It is proved that the performance of HGA2 is superior to HGA1 in terms of the total assembly time.     

A particle swarm optimization approach to optimize component placement in printed circuit board assembly

The particle swarm optimization (PSO) approach has been successfully applied in continuous problems in practice. However, its application on the combinatorial search space is relatively new. The component assignment/sequencing problem in printed circuit board (PCB) has been verified as NP-hard (non-deterministic polynomial time). This paper presents an adaptive particle swarm optimization (APSO) approach to optimize the sequence of component placements on a PCB and the assignment of component types to feeders simultaneously for a pick-and-place machine with multiple heads. The objective of the problem is to minimize the total traveling distance (the traveling time) and the total change time of head nozzle. The APSO proposed in the paper incorporates three heuristics, namely, head assignment algorithm, reel grouping optimization and adaptive particle swarm optimization. Compared with the results obtained by other research, the performance of APSO is not worse than the performance of genetic algorithms (GA) in terms of the distance traveled by the placement head.     

Simulation of mixed-model PCB assembly lines with group setup and bypass conveyors

Recent technological innovations, namely the development of new solder pastes with increased tack life and the introduction of bypass conveyors, facilitate the use of mixed-model lines in printed circuit board (PCB) assembly. This paper presents a simulation study comparing PCB assembly lines operating in conventional batch and in mixed-model assembly mode. For the latter case, a novel group setup strategy is developed. In the first stage, component types and placement operations for each type of PCB are assigned to the machines in the assembly line with the objective of balancing the workload. In the second stage, PCB types with similar component requirements are clustered into setup families. In addition, the feeder-slot assignment for each setup family and the sequence of placement operations for each PCB type are determined. In the final stage, a cyclical mixed-model production schedule is established. The performance of the proposed solution approach is evaluated by means of a simulation study. Two alternative material flow systems are investigated: a serial conveyor which directly links one machine to the other and a flexible one that allows to bypass downstream machines in the line.     

An integrated allocation method for the PCB assembly line balancing problem with nozzle changes

There are several placement machines connected by a conveyor in a printed circuit board assembly line. The objective of the line balancing problem is to minimize the cycle time of the assembly line, which is the maximum production time of the placement machines. In this paper, the nozzle factor, which is often ignored, is considered in estimating the production time of the placement machine, and the nozzle change is also allowed. The production time of a machine is a linear function of the number of components, the number of turns and the number of nozzle changes performed by the machine, which are determined by the component allocation problem, the nozzle set allocation problem and the head allocation problem. These three allocation problems compose the line balancing problem and are solved iteratively. First, the component allocation problem is solved by proposed genetic algorithms (GAs), which generate feasible allocation solutions directly. To search efficiently, non-selective and selective allocation strategies are proposed to solve the component allocation problem. A greedy heuristic (GH) is proposed to solve the nozzle set allocation problem and the head allocation problem simultaneously. Then, the GAs for the component allocation and the GH for the nozzle set and head allocation are integrated according to their interactive relations. Finally, the efficiency of the composite algorithm is illustrated by numerical analysis.     

Component Grouping for Automatic Printed Circuit Board Assembly

This paper addresses a component grouping problem in an automatic printed circuit board (PCB) assembly line with several non-identical placement machines. After the problem is defined, an integer linear programming model is formulated with the objective of minimising the cycle time of the assembly line. The integer linear programming model can be solved by the general branch-and-bound (B&B) algorithm; however, it is not efficient. So, the integer linear programming model is relaxed as a linear programming formulation because a near-optimal solution is acceptable in the real situation. A new algorithm is developed for the dual of the linear programming model. To demonstrate the efficiency of this algorithm, an example is presented and compared with its integer solution from a commercial package, CPLEX.     

Organizing the nozzle magazine of a gantry-type PCB assembly machine

The present work studies the operation control of so-called collect-and-place component placement machines. These kinds of machines are suited for the flexible manufacturing of various printed circuit board products. These machines operate in cycles where a set of components is first collected from the component feeders to the vacuum nozzles of the component placement head. The head then moves on the circuit board and places the components to their appropriate locations. Different component types require the use of different nozzle types, but the placement head has only a limited capacity for nozzles. Hence, the ability to change nozzles every now and then allows the manipulation of a great variety of component types with the same machine. This is accomplished by storing a larger selection of nozzles in a separate nozzle magazine from where the nozzle collection of the placement head can be updated. The cost of changing the nozzle setup is, however, relatively large compared to the time costs of other operations in the placement cycle. What complicates things more is that the nozzle change cost is affected by the organization of nozzles in the magazine, too. The aim of this work is to determine the contents of the nozzle magazine in such a way that the change operation times are as small as possible. We develop two heuristics (a genetic algorithm and a swarm optimization algorithm) for this purpose and evaluate their performance on sample problems. Both heuristic approaches are capable of processing realistic production problems, in particular the genetic algorithm finds near-optimal results for small problem instances and outperforms clearly our other approaches for larger problems.     

基于差分算法的贴装顺序优化问题求解

元器件取料、贴放顺序是影响印刷电路板(PCB)贴片机工作效率的关键因素之一.针对拱架型多头贴片机建立以时间为研究对象的取料、贴放顺序优化数学模型.给定解的整数编码形式,利用差分算法解决此优化问题.将迁徙操作思想引入差分算法,建立带迁徙操作的差分算法,并给出算法流程及实现方式.通过实验选择差分算法的较佳参数,用两组实验将差分算法、带迁徙操作的差分算法与遗传算法进行比较,实验表明差分算法、带迁徙操作的差分算法能够有效地解决拱架型多头贴片机元器件的取料、贴放优化问题,且优化结果较遗传算法好.     

Automated inspection of PCB components using a genetic algorithm template-matching approach

Automated inspection of surface mount PCB boards is a requirement to assure quality and to reduce manufacturing scrap costs and rework. This paper investigates methodologies for locating and identifying multiple objects in images used for surface mount device inspection. One of the main challenges for surface mount device inspection is component placement inspection. Component placement errors such as missing, misaligned or incorrectly rotated components are a major cause of defects and need to be detected before and after the solder reflow process. This paper focuses on automated object-recognition techniques for locating multiple objects using grey-model fitting for producing a generalised template for a set of components. The work uses the normalised cross correlation (NCC) template-matching approach and examines a method for constraining the search space to reduce computational calculations. The search for template positions has been performed exhaustively and by using a genetic algorithm. Experimental results using a typical PCB image are reported.