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.     

AUTOMATED PROCESS PLANNING FOR PRINTED CIRCUIT CARD ASSEMBLY

Printed circuit card assemblies form the core of a vast array of contemporary manufactured products. The technologies for assembling printed circuit cards require a hierarchy of complex decisions for grouping card types and processes, staging components at assembly machines, arranging feeders, and sequencing placement operations. This paper is motivated by the largely unmet needs of industrial process planners for computer aids. Our objective is to develop a framework for the printed circuit card assembly process planning problem and to assess the current state of the research on appropriate models and solution methods. We first provide an overview of the essential elements of printed circuit card terminology, assembly technologies, and assembly system operations. Then we propose a decision hierarchy, survey the published literature, and identify needs for future research.     

Process and production planning for circuit board assembly

Process planning output can be post-processed into criteria for job scheduling decisions in printed circuit board assembly using surface-mount technology (SMT). Artificial intelligence-based techniques used in computerized planning and scheduling systems in other industries can be extended to printed circuit board operations. These techniques include blackboard architectures, object-oriented programming systems, and nonmonotonic reasoning systems. These techniques were used to demonstrate a unique architecture of blackboard systems that communicate via object-oriented messages to arrive at a shop-floor process plan and production schedule. The methodology was specialized to the assembly of printed circuit boards using surface-mounted components in a high-variety/low-volume product mix. The assembly facility was represented as a hierarchical object of product, process, and organizational knowledge. The system of working heuristics was integrated within a prototype environment with the practitioners that assisted in its development. The end result is a good working methodology for system development, implementation, and maintenance by knowledge worker involvement.     

Aggregate line capacity design for PWB assembly systems

In a multi-product, flexible manufacturing environment, line capacity of printed wiring board (PWB) assembly systems may need to be adjusted at the beginning of each aggregate planning period because of demand fluctuation over multiple periods. A model of production planning and equipment changeover scheduling at the aggregate level is developed. In the described model, three kinds of equipment changeover methods, i.e. adding machine, removing machine and transferring machine, are involved. Because the model is a large-scale integer programming problem, it cannot be solved directly. A solution approach is developed, which first solves a recursive linear programming problem to obtain a rough set of machines to be added and a rough set of machines to be removed for each machine line in each period, then applies a branch and bound heuristic to the rough sets to obtain near-optimal solutions to the equipment changeover scheduling problem. Computational studies show the financial benefit both on capital cost and equipment changeover costs.     

A simultaneous-mounting process for automated printed circuit board assembly

Current robotized printed circuit board assembly systems allow one component to be inserted onto the board at a time and the corresponding design usually causes complicated operation planning problems for plant engineers. This paper addresses an opportunity for productivity improvement in automated printed circuit board assembly through the design of a new assembly mechanism from plant engineer's viewpoint. The mechanism not only will allow simultaneous insertions of multiple components but also will simplify the component placement planning task.     

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.     

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.     

Productivity improvement through a sequencing generalised assignment in an assembly line system

This paper considers the assignment of heterogeneous workers to workstations of an assembly line in order to minimise the total production time. As the structure of the system implies that each of the workstations needs at least one worker, thus the problem can be considered as a generalised assignment problem (GAP). The objective is to perform an efficient human resource planning for a specified horizon consisting of several periods. Hence, we present an extension of the generalised assignment problem, consisting of a set of GAPs (one for each planning period) in which each GAP depends on the previous ones. A mixed integer mathematical model is presented for this sequencing assignment problem. The model is solved by an exact algorithm using Gurobi solver. It is proved that the problem is NP-hard and solving the medium and large size instances is not possible by the exact algorithms. Hence, two matheuristic approaches based on the disaggregated formulation of GAP are proposed. The first approach solves the problem through two sub-problems as the transportation formulation and assignment formulation. The second approach solves the problem by decomposition of the problem into several classical GAPs. The approaches are examined by a total of 27 instances. The results illustrate the efficiency of the proposed algorithms in the computational time and accuracy of the solutions.     

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.     

Robotic U-shaped assembly line balancing using particle swarm optimization

Automation in an assembly line can be achieved using robots. In robotic U-shaped assembly line balancing (RUALB), robots are assigned to workstations to perform the assembly tasks on a U-shaped assembly line. The robots are expected to perform multiple tasks, because of their capabilities. U-shaped assembly line problems are derived from traditional assembly line problems and are relatively new. Tasks are assigned to the workstations when either all of their predecessors or all of their successors have already been assigned to workstations. The objective function considered in this article is to maximize the cycle time of the assembly line, which in turn helps to maximize the production rate of the assembly line. RUALB aims at the optimal assignment of tasks to the workstations and selection of the best fit robot to the workstations in a manner such that the cycle time is minimized. To solve this problem, a particle swarm optimization algorithm embedded with a heuristic allocation (consecutive) procedure is proposed. The consecutive heuristic is used to allocate the tasks to the workstation and to assign a best fit robot to that workstation. The proposed algorithm is evaluated using a wide variety of data sets. The results indicate that robotic U-shaped assembly lines perform better than robotic straight assembly lines in terms of cycle time.     

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.     

Board sequencing and component loading problem for a single machine in PCB assembly planning

Most current research sequentially solves the board sequencing and component-loading problem for a single machine in printed circuit board (PCB) assembly. The board sequence is first determined. The component-loading order is then established. In addition, other current approaches are used to solve the problem based on the upper bound on component changeovers between two jobs. However, consideration of current magazine status could be a source for total set-up time reduction. In this paper, a new approach is developed to establish board sequence and component-loading order simultaneously. Each board sequence position and component-loading order are obtained together from the process of current set-up determination. The obtained solution is then improved further by the combination of bias and random search processes. Some experiments are tested to confirm theoretical judgement.     

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.     

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.     

A knowledge-based system for solving multi-objective assembly line balancing problems

This paper presents design-and-development details of a knowledge-based system that solve multi-objective assembly line balancing problems to obtain an optimal assignment of a set of assembly tasks to a sequence of workstations. Assembly line balancing problems arise in high-volume production systems with a significant regularity. The formulation and solutions currently employed by managers and practitioners usually aims at optimizing one objective (e.g., number of work stations or cycle time), thus ignoring the multi-dimensional nature of the overall objectives of the manager. Furthermore, in practice ALBPs are ill-defined and ill-structured, making it difficult to formulate and solve them by mere mathematical approaches. The knowledge-based system multi-objective assembly line balancing approach, presented in this paper, addresses these needs. This paper presents a knowledge-base multi-objective approach to assembly line balancing problems. It demonstrates how such a system can be constructed and how a variety of assembly line balancing methods can be used in a uniform structure to support the decision maker (DM) to formulate, validate the formulation, generate alternatives, and choose the best alternative. Its capabilities include: (1) Elimination of inconsistencies in the problem structure. (2) The use of multi-objective formulation of the problem, (3) A well-designed user-interface, (4) Pursuance of the overall objectives of the manager via a new mechanism, (5) Development of several efficient alternatives, consistent with the user-specified constraint structure, providing the decision maker with a larger number of choices, and, (6) An approach for ranking and prioritizing alternatives consistent with the decision-maker's preferences.     

Variability modelling and balancing of stochastic assembly lines

In a production flow line with stochastic environment, variability affects the system performance. These stochastic nature of real-world processes have been classified in three types: arrival, service and departure process variability. So far, only service process – or task time – variation has been considered in assembly line (AL) balancing studies. In this study, both service and flow process variations are modelled along with AL balancing problem. The best task assignment to stations is sought to achieve the maximal production. A novel approach which consists of queueing networks and constraint programming (CP) has been developed. Initially, the theoretical base for the usage of queueing models in the evaluation of AL performance has been established. In this context, a diffusion approximation is utilised to evaluate the performance of the line and to model the variability relations between the work stations. Subsequently, CP approach is employed to obtain the optimal task assignments to the stations. To assess the effectiveness of the proposed procedure, the results are compared to simulation. Results show that, the procedure is an effective solution method to measure the performance of stochastic ALs and achieve the optimal balance.     

Integrated methodology for board assignment and component allocation in printed circuit board assembly

An approach to minimize makespan for assigning boards to production lines is described. Because of sequence-dependent set-up times, board assignment and component allocation have to be performed concurrently. An integrated methodology is developed to obtain a solution to these two problems. The methodology consists of seven phases: printed circuit board grouping, family decomposition, subfamily sequencing, Keep Tool Needed Soonest (KTNS) procedure, component set-up determination, component allocation and board assignment. Application of the methodology to industrial problems demonstrates that it can solve large-scale problems efficiently. In addition, the effect of two key parameters, feeder capacity and threshold value, on the performance of the solution procedure was examined. The results indicate that feeder capacity has an impact on total workload imbalance but not on the global makespan. Threshold value, a measure of effectiveness of joining a component type to a component group for a printed circuit board family, has a significant effect on the global makespan. The interactions of threshold value, and variations in printed circuit board requirement and component usage also affect global makespan.     

Precedence constrained TSP arising in printed circuit board assembly

Component placement sequencing is a challenging problem that arises in automated assembly of printed circuit boards. While for some placement machines all placement sequences are acceptable, in other cases some sequences are not allowed because of the shape of the placement head. In such cases, while the head moves down to perform a placement, it might damage a previously placed component, and the problem of determining a minimum cost and at the same time acceptable sequence leads to a Precedence Constrained Travelling Salesman Problem formulation. In this study, a solution procedure to such a formulation is developed and its implementation in a real PCB assembly environment is discussed.