Balancing printed circuit board assembly line systems

This paper considers the placement of components onto printed circuit boards (PCBs) using surface mount technology. Multiple automatic placement machines, a variety of PCB types and a large volume for each PCB type characterize the environment studied. The problem addressed is that of allocating and arranging the components on several placement machines, organized into one or several assembly lines, while considering a different assembly time if components are located at different feeder locations. The one assembly line problem is equivalent to balancing a multi-model assembly line where models are assembled in small batches without component rearrangement between model changes. The objective is tominimize the weighted sum of each assembly PCBcycle time, which is defined as the maximum time a PCB has to spend on each machine. We solve this problem with Lagrangian relaxation techniques. Industrial case study results are presented. We also compare the global performance of five placement machines if they are organized as a single assembly line or broken down into two or more assembly lines.     

Mixed integer programming for scheduling surface mount technology lines

This paper presents new mixed integer programming formulations for blocking scheduling of SMT (Surface Mount Technology) lines for printed wiring board assembly. The SMT line consists of several processing stages in series, separated by finite intermediate buffers, where each stage has one or more identical parallel machines. A board that has completed processing on a machine may remain there and block the machine until a downstream machine becomes available for processing. The objective is to determine an assembly schedule for a mix of board types so as to complete the boards in a minimum time. Scheduling with continuous or with limited machine availability is considered. Numerical examples and some computational results are presented to illustrate applications of the models proposed.     

Optimal versus heuristic scheduling of surface mount technology lines

This paper presents and compares an exact and a heuristic approach for scheduling of printed wiring board assembly in surface mount technology (SMT) lines. A typical SMT line consists of several assembly stations in series and/or in parallel, separated by finite intermediate buffers. The objective of the scheduling problem is to determine the detailed sequencing and timing of all assembly tasks for each individual board, so as to maximize the line's productivity, which is defined in terms of makespan for a mix of board types. The limited intermediate buffers between stations result in a scheduling problem with machine blocking, where a completed board may remain on a machine and block it until a downstream machine becomes available. In addition, limited machine availability due to scheduled downtimes is considered. The exact approach is based on a mixed integer programming formulation that can be used for optimization of assembly schedules by using commercially available software for integer programming, whereas the heuristic approach is designed as a combination of tabu search and a set of dispatching rules. Numerical examples modelled after real-world SMT lines and some computational results are provided to illustrate and compare the two approaches.     

Mechanism to minimise the assembly time with feeder assignment for a multi-headed gantry and high-speed SMT machine

This paper proposes the development of a mechanism to minimise the assembly time for a multi-headed gantry and high-speed surface mounting technology machine by determining the component assignment to feeder slots. Since a gantry moves long distances in order to pick components, place them on the board and then return them to the feeder slots, we classified the overall assembly time according to the different movements of a gantry. The overall assembly time is then minimised by presenting a new heuristic for the feeder assignment, consisting of Nearest Component Allocation (NCA) and Globally Updated Assignment (GUA). NCA contains information about how each component type locates closely to others on the board. Using the solution from NCA, the component distance function calculates the most representative distance between component types. Then, GUA is applied to improve the NCA solution. The experiments consist of several printed circuit boards with numbers of component types and points to be placed. Highlights of this paper are that: a classification of the gantry movements is proposed based on the average speed; a heuristic NCA-GUA for feeder assignment is developed by considering the placements on the board; the computational time is greatly reduced by NCA-GUA without degrading the solution quality; and a decision process for nozzle assignment is proposed to minimise the overall assembly time. The results show how NCA and GUA affect the final results, and how this mechanism leads to better performance than a genetic algorithms or 2-opt swap search. This comparison proves that our method provides competitive and effective solutions in terms of minimising the overall assembly time.     

PCB assembly scheduling for collect-and-place machines using genetic algorithms

In printed circuit board (PCB) assembly, collect-and-place machines, which use a revolver-type placement head to mount electronic components onto the board, represent one of the most popular types of assembly machinery. The assignment of feeders to slots in the component magazine and the sequencing of the placement operations are the main optimisation problems for scheduling the operations of an automated placement machine. In this paper, we present different genetic algorithms (GAs) for simultaneously solving these highly interrelated problems for collect-and-place machines in PCB assembly. First we consider single-gantry machines as the basic type of machinery. In the conventional GA approach all placement operations and the feeder-slot assignment are represented by a single chromosome. In order to increase the efficiency of the genetic operators, we present a novel GA approach, which integrates a clustering algorithm for generating sub-sections of the PCB and grouping the corresponding placement operations. It is shown that the proposed GAs can be extended to schedule dual-gantry placement machines, which are equipped with two independent placement heads and two dedicated component magazines. Hence, component feeders have to be allocated between the two magazines. To solve this allocation problem, two different heuristic strategies are proposed. Finally, detailed numerical experiments are carried out to evaluate the performances of the proposed GAs.     

Estimating printed circuit board assembly times using neural networks

Several production planning tasks in the printed circuit board (PCB) assembly industry involve the estimation of the component placement times for different PCB types and placement machines. This kind of task may be, for example, the scheduling of jobs or line balancing for single or multiple jobs. The simplest approach to time estimation is to let the production time be a linear function of the number of components to be placed. To achieve more accurate results, the model should include more parameters (e.g. the number of different component types, the number of different component shapes, the dimensions of the PCBs, etc.). In this study we train multilayer neural networks to approximate the assembly times of two different types of assembly machines based on several parameter combinations. It turns out that conventional learning methods are prone to overfitting when the number of hidden units of the network is large in relation to the number of training cases. To avoid this and complicated training and testing, we use Bayesian regularisation to achieve efficient learning and good accuracy automatically.     

A GA-based solution approach for balancing printed circuit board assembly lines

Printed circuit board (PCB) assembly lines consist of a number of different machines for mounting electronic components onto PCBs. While high-speed placement machines are employed to assemble standard components, so-called fine-pitch placement machines are used to mount complex electronic components with high precision and by use of specific nozzles. In this paper, we investigate a typical mass production environment where a single type of PCB is assembled in a line comprising high-speed as well as high-precision placement machines. The PCB assembly line balancing problem consists of assigning component feeders, each holding a specific electronic component type, and the corresponding placement operations to machines in the line so as to minimize the assembly cycle time. To solve this problem, a two-stage solution procedure based on genetic algorithm (GA) is proposed. In the first stage, component feeders are assigned to the placement machines with the objective of balancing the workload within the assembly line. A number of candidate solutions are then transmitted to the second stage, where specific machine optimization algorithms are applied to determine the feeder-slot assignment in the component magazine of the machines and the placement sequence of the various components. As a result, fine-tuned placement operation times are achieved which reflect the individual operation mode and the actual component setup of the placement machines. Finally, from the candidate solutions the one which minimizes the actual PCB assembly time is selected.     

Development of group setup strategies for makespan minimisation in PCB assembly

Balancing setup effort and actual production time is an important issue in medium-variety, medium-volume printed circuit board (PCB) assembly. By grouping batches of similar PCB types to be processed with a common machine setup, the total time required for setting up the component feeders in the magazine of the placement machine can be reduced. On the other hand, the assembly times per PCB increase, since it is no longer possible to optimise the feeder locations in the magazine for each PCB type individually. In order to balance the savings in setup time and the increase in assembly time and to minimise the global makespan, we propose efficient grouping procedures which include machine-specific algorithms for fine-tuning the machine operations for a group of PCBs. Hence, the actual placement times are reflected much more accurately, compared with conventional grouping procedures which merely analyse the component similarity between pairs of PCBs. Two different agglomerative clustering techniques are proposed. One is based on average linkage clustering, the other on a novel hierarchical clustering approach using an inclusion tree representation of the PCB types. Both take the limited capacity of the component magazine into account. We demonstrate the effectiveness of our approach in an extensive numerical investigation of a single-gantry collect-and-place machine equipped with a rotary placement head and an interchangeable feeder trolley. Compared to conventional methodologies, the proposed group setup strategies reduce the global makespan for a given number of batches significantly.     

A feeder replenishment policy for a turret-head placement machine

In this paper, a feeder replenishment strategy for a turret-head placement machine is proposed. The proposed method decreases the production time in a high volume electronics-manufacturing environment by using multiple allocations of components to feeder slots. The related reduction in production time is achieved by reducing the total number of replenishments through feeder exhaust synchronization. In our approach, we first solve a 0–1 linear programming model to reduce the downtime due to the replenishments by utilizing the unused feeder slots for multiple assignments. Since any small variation in the reel sizes will disrupt the synchronization among feeder exhausts, we propose a procedure called ‘Fixed Replenishment Policy’ to reduce this effect. The approach has been tested with data obtained from a high-volume electronics manufacturer and the results are examined.     

An MILP model and a hybrid evolutionary algorithm for integrated operation optimisation of multi-head surface mounting machines in PCB assembly

This paper focuses on an operation optimisation problem for a class of multi-head surface mounting machines in printed circuit board assembly lines. The problem involves five interrelated sub-problems: assigning nozzle types as well as components to heads, assigning feeders to slots and determining component pickup and placement sequences. According to the depth of making decisions, the sub-problems are first classified into two layers. Based on the classification, a two-stage mixed-integer linear programming (MILP) is developed to describe it and a two-stage problem-solving frame with a hybrid evolutionary algorithm (HEA) is proposed. In the first stage, a constructive heuristic is developed to determine the set of nozzle types assigned to each head and the total number of assembly cycles; in the second stage, constructive heuristics, an evolutionary algorithm with two evolutionary operators and a tabu search (TS) with multiple neighbourhoods are combined to solve all the sub-problems simultaneously, where the results obtained in the first stage are taken as constraints. Computational experiments show that the HEA can obtain good near-optimal solutions for small size instances when compared with an optimal solver, Cplex, and can provide better results when compared with a TS and an EA for actual instances.     

Simultaneous versus sequential loading and scheduling of flexible assembly systems

A monolithic and a hierarchical approach is presented for loading and scheduling in a general flexible assembly system and a flexible assembly line. The system is made up of a set of assembly stations of various types each with limited working space and is capable of simultaneously producing a mix of product types. The objective is to determine an assignment of assembly tasks to stations and an assembly schedule for all products so as to complete the products in a minimum time. In the monolithic approach loading and scheduling decisions are made simultaneously. In the hierarchical approach, however, first the station workloads are balanced by solving the loading problem, and then detailed assembly schedule is determined for prefixed task assignments and assembly routes by solving a standard job-shop problem. Mixed integer programming formulations are presented for simultaneous and for sequential loading and scheduling. Loading and scheduling with alternative or with single task assignments are considered. Numerical examples are included to illustrate and compare the two approaches proposed.     

A NOTE ON THE REEL ALLOCATION PROBLEM

The reel allocation problem is to choose the numbers of reels of each of a number of types of items to be used in populating a printed circuit board by a SMT machine so as to maximize the length of an uninterrupted machine production run while using no more slots for reels than are available. We show this problem can be solved to optimality very efficiently with a quite simple and robust bisection search algorithm. Algorithm run times are less than 1 second on a 486 PC.     

Mixed model assembly system with multiple secondary feeder lines: layout design and balancing procedure for ATO environment

The constant research for efficiency and flexibility has forced assembly systems to change from simple/single assembly lines to mixed model assembly lines, while the necessity to reduce inventory has led the transition from single to multi-line systems, where some components are assembled in secondary lines, called feeder lines, connected to the main one by a ‘pull philosophy’. A possible approach to configure such an assembly system is to balance the main line first and use the retrieved cycle time to balance each feeder line separately, which is a questionable solution, especially if operators can perform tasks on both the feeder and the main line. Moreover for its complexity the mixed model balancing problem is usually solved transforming it into a single model by creating a single ‘virtual average model’, representative of the whole production mix. The use of a virtual average model assumes that the processing times of some models are higher or lower than the cycle time, which creates overload/idle time at the stations. This approach, especially in complex multi line production systems, largely reduces the assembly line productivity and increases the buffers dimensions. This paper faces the mixed model assembly line balancing problem in the presence of multiple feeder lines, introducing an innovative integrated main-feeder lines balancing procedure in case of unpaced assembly systems. The proposed approach is compared with the classical one and validated through simulation and industrial applications.     

A note on ‘balancing printed circuit board assembly line systems’

In a recent paper of (Lapierre, S.D., Debargis, L. and Soumis, F., Balancing printed circuit board assembly line systems. Int. J. Prod. Res., 2000, 38, 3899–3911.), the authors considered the balancing of a PCB assembly line consisting of several pick-and-place machines. The authors claimed that, for the particular machine type they considered, the component placement time is independent of the placement sequence of the components and then concentrated on allocating component types to machines and configuring the feeders on each machine to balance the line. We show that, the placement time is actually dependent on the placement sequence and thus, it needs to be accounted for if a more accurate line balance is looked for.     

Extended dynamic point specification approach to sequencing robot moves for PCB assembly

In PCB assembly planning, most of the current works solved the assembly sequence and feeder assignment problem directly. They have not decomposed the problem into subproblems. Consequently, the problem remains very complex and, therefore, it is hard to solve. Few research works considered about the detail on how to determine the optimal picking points (or placement points), but results are still limited. The extension of these works is necessary. This paper extends the point specification problem based on the Dynamic Pick and Place (DPP) model, namely, the Extended Dynamic Pick and Place (EDPP0 model. The EDPP determined the picking/placement point coordinates from global consideration of point relationship in the system. The whole system is analysed to establish the new model. From this guideline the system is modelled in a systematic scheme based on the objectives of each object in the systems (robot arm, feeder rack, board table). These objectives should be satisfied together to reach the global objective of the system. Numerical experiment shows that the EDPP model is better than the DPP model in terms of total assembly time.     

Synchronized manufacturing at final assembly and feeder shops

Many manufacturing environments consist of a final assembly shop that receives components from various feeder shops. Suppose the final assembly shop assembles a mix of products, each requiring varying amounts of different components. Thus, the sequence in which products are assembled imposes time-dependent demands on the feeder shops. Such problems are often found in the assembly of high-tech telecommunications systems and in the assembly of mixed models of automobiles. We develop a variety of models that link the work-in-process inventory in the feeder shop and the finished component inventory to the component production interval and the final assembly sequence. The manufacturing disciplines considered include push, look-ahead and kanban. Feeder shops are assumed to manufacture components continuously, periodically, or at a fixed lot size. Simple performance characteristics of the feeder shop are derived to provide insight into synchronized manufacturing issues and to help evaluate the effect of different final assembly sequences on feeder shops.     

Assembly line sequencing for model mix

This paper describes a model sequencing algorithm for model-mix assembly lines. A new formulation of the sequencing problem is proposed, the objective function of which is to minimize the overall assembly line-length for no operator interference. Lower bounds for the overall line-length are developed.

Two types of work station interfaces are considered; ‘closed’, where boundaries cannot be violated, and ‘open’ where defined boundaries do not exist—adjacent operators being allowed to enter each others apparent work areas without causing any interference.

A complete factorial experiment was made on five factors to determine their influence on the overall assembly line length. These are, the number of models, the model cycle time deviation, the production demand deviation for each model, the operator time deviation, and the number of stations in the assembly line. The main conclusions of this experiment are discussed and recommendations made for the selection of parameters used in the design of model-mix assembly lines.

Also discussed is an approach for accommodating small changes in production demand for existing assembly lines.     

ANALYTICAL TOOLS FOR ASSEMBLY LINE DESIGN AND SEQUENCING

Many complex assembly lines, such as those in the automobile industry, have dozens or hundreds of stations that are affected by customer-selected options on the jobs being assembled. The various options often require significantly different amounts of processing time, and the role of assembly line sequencing in this context is to smooth out the flow of work to each station. However, most assembly line sequencing algorithms developed for such situations cannot consider so many stations or options effectively. In this paper, we develop an analytical method to compute a criticality index for each station, which can be used to determine which stations are most important to include in an assembly line sequencing algorithm. We report computational results using actual industry data which indicates that substantial improvements can be obtained by selecting stations based upon this criticality index.     

Component allocation to balance workload in printed circuit card assembly systems

Component allocation in printed circuit card assembly systems is a special case of the classical mixed-model assembly line balancing problem and involves assigning component types to machines to achieve specific production objectives. In this paper the component allocation problem is considered for the scenario where there are two or more placement machines (possibly nonidentical) and the objective is to balance, for every card type, a combination of the card assembly time and the machine setup time. A mathematical formulation of the problem is developed for a class of placement machines. Two alternative solution approaches are presented: a list-processing-based heuristic for a simple version of the problem, and a linear-programming-based branch-and-bound procedure for the general component allocation problem. Industrial case study results are presented for each approach that indicate expected throughput improvements of up to 8-10% over the company's current procedure, with much less direct effort required by the process engineer.     

A spreadsheet method for calculating work completion time probability distributions of paced or linked assembly lines

This study presents a spreadsheet method for computing the work completion time probability distribution of a linked assembly line with variable station service times. Once developed, this distribution can be used to analyse the probability of completing all work at all stations within a given cycle time on either a linked or mechanically paced assembly line. The method can be used to determine what cycle time to set on a paced line, given a desired workload at each station. Alternately, given a desired cycle time and probability that all work has been completed at each station within the cycle time, the method can be used to determine how much work to allocate to each station on the paced line. The method is simple, easy to use, and works with any continuous or discrete station service time distribution that can be specified in a spreadsheet. Comparisons between the output of the spreadsheet method and simulations of the same system indicate the spreadsheet method is quite accurate. Hence, the method can be useful to both researchers and practitioners working with the design and/or behaviour of linked or paced lines, and it provides an easy-to-use teaching tool for illustrating characteristics of linked or paced assembly lines.