Abstract
Optimisation of feeder setup and component placement sequence are very important to the efficiency of surface mount placement machines. Much works have been conducted to solve this problem. However, the technological characteristics of the placement machine influences the nature of the planning problems to be solved and the formulation of the associated models. As a result, little consensus exists as to what a suitable model should
be for a given machine characteristics, and the formulations proposed by different authors tend to be difficult to compare. Hence, this paper will survey the relation between models, assembly machine technologies and heuristic methods. Keywords: Modelling, Optimisation, Electronic Assembly, Printed Circuit Board Assembly, SMT.

1. Introduction
When hundreds of electronic components of different shapes and sizes have to be placed at specific locations on a printed circuit board (PCB), finding an optimal robot travelling route is complicated and time consuming [1]. This problem is an NP-Hard problem and most practical instances are difficult to solve to optimality in a reasonable time [2]. In practice, a heuristic solution is highly desirable [1]. Heuristic algorithms can generate good solutions
efficiently at a reasonable computational cost [3]. Khoo and Loh [4], for example, have developed a prototype genetic algorithm (GA) to enhance a planning system for the placement of surface mount devices (SMDs) on a Fuji FCP-IV. Wang et al.[3] argue that their GA performs as well as a human expert in optimising the feeder slot assignment problem for the Fuji QP-122. Crama et al. [5] agree that the technological characteristics of the equipment influences the nature of some of the planning problems to be solved and the formulation of the associated models. Little consensus exists as to what a suitable model should be for a given set of machine characteristics, and the formulations proposed by different authors tend to be difficult to compare. Hence, this paper will discuss the relation between models, assembly machine technologies and heuristic methods.

Optimisation in PCB assembly involves a list of subproblems to be addressed, such as an assignment of PCB types to product families and to machine groups, allocation of components to machines and location of components in feeder slots and component placement sequencing [5]. In this work we focus on feeder setup and component
placement sequencing for various type of placement machine for surface mount technology (SMT). More general reviews on PCB assembly problems can be found in [5, 6].

2. Placement Machines
Placement machines are sometimes called “chip shooters” [3]. There are many types of SMT placement machines available, such as sequential pick-and-place, rotary disk turret, concurrent pick-and-place, etc. [4,7]. Various types of SMT placement machines have different characteristics and restrictions [3]. Thus, the PCB production scheduling
process is highly influenced by the type of placement machine being used [8]. Industrial robotic placement machines have already been classified by mechanical structure such as cartesian/gantry, cylindrical, spherical, single compliance robot for assembling (SCARA),
articulated and parallel [9]. However, the mechanical structure classifications do not greatly influence the nature of optimisation problems since most of the placement machines used in PCB assembly industry are cartesian/gantry robots. Thus, in this work we propose five
categories of machines based on their specification and operational methods. Previously, the placement machines have been classified into two categories these being concurrent and sequential by McGinnis et al. [6], or fixed pick-and-place point (FPP) and dynamic pick-and-place point (DPP) by Wang et al. [10]. However, these two categories are too general, hence it tends to be difficult to formulate the optimisation problems based on these categories.

Generally, each placement machine has a feeder carrier (or feeder magazine), PCB table, head, nozzle (or gripper) and a tool magazine. The feeder carrier, PCB table and head can be either fixed or moveable depending on the specification of the machine. In some cases, the feeder carrier is divided into separate feeder banks, each consisting feeder slots [3]. A typical feeder carrier consists of either several tape reels or vibratory ski slope feeders or
both [11]. The feeder reels or vibratory ski slope feeders are positioned in the feeder slots according to the arrangement given by feeder setup. The nozzle grasps the component from the feeder and then mounts it on the PCB [12]. The placement arm, that is equipped with head(s), are responsible for picking and placing components. Each head may have more than one nozzle and each machine may have more than one head. There are various types of placement heads, such as a rotating turret head, or a positioning arm head [3]. The PCB table(s) are required to position the PCB(s) during placement operation. The
table(s) could be stationary, a conveyor system, or an X-Y motion table. Different sizes of SMD require different sizes of nozzle to pick-and-place them. Hence, a tool magazine is required to provide the exact nozzle size.

2.1 Dual Delivery Placement Machine
This machine consists of the PCB table which can move in both X and Y directions and should be aligned under the head to perform the placement operation; the placement
arms and two component delivery carriers are only able to move in the X-direction [11, 13]. The pick-and-place heads are mounted at the two ends of a fixed length arm, which can move between two fixed positions in the Y-direction only. Each pick-and-place operation alternates between two sides, i.e. while one head is performing the pick operations, the other one is placing components on the board [13]. For this machine, all movements of the PCB table and feeder carrier are frozen during the pick-andplace operations. Therefore, the maximum time taken by the arm, PCB table and feeder carrier movements will determine the cycle time. The Dynapert MPS 500 [13], the Panaset MCF that is equipped with 10-nozzle gang pickup [14], the Fuji NP-132 which contains dual turret placement heads with 16 nozzles on each head and the Siemens Siplace 80S-20 [15] are all examples of dual delivery placement machine.

2.2 Multi-Station Placement Machine
This machine has more than one placement module (or station) each one being mechanically identical and able to assemble electronic parts concurrently. The stations are
connected by a conveyor system to transfer boards among the stations. Each station receives all the necessary pickand- place coordinate data for one machine cycle (the
interval between two conveyor steps), and completes the cycle’s placement sequence autonomously and concurrently with the other stations. After all stations have finished, the conveyor is moved, and the placement procedure continues. The Fuji QP-122 [3, 16] that has 16 stations with each station consisting of fixed multi-feeder unit and a single-nozzle placement head is an example of the multi-station placement machines.

2.3 Turret Style Placement Machine
This machine uses a placement mechanism mounted on a rotating turret (drum or carousel), with multiple placement heads, that rotate from a fixed pickup location to the
placement location [17]. Each pick-and-place operation starts by retrieving a component at the grip station, while the placement station simultaneously mounts a component at a pre-specified location on the PCB [2, 18]. Then, the feeder rack moves to get the next appropriate feeder in position, and the PCB table simultaneously moves to position the next location under the place station. Some of the common turret style placement machines include the Fuji FCP-IV [19, 20] that has 12-nozzles mounted on a rotary head, the Fuji CP4, CP4-2, and CP4-3, which have 12 mounting heads, the Fuji CP6 which has 20 placement heads [21] and the CM82 equipped with 18 heads [22].

2.4 Multi-Head Placement Machine
In this machine, the tour of the heads begins by picking up a few components from the feeder simultaneously. Then, the head and the arm travel in the X and Y direction
simultaneously and the head positions itself on top of the point where the component will be mounted, and then the head moves down (Z-direction) and mounts the component
on the board then returns to the original position and repeats these steps for the next locations on the board that have to be mounted on the same tour. The PCB table also moves in X and Y directions, concurrent with the movements of head and arm. After completing a tour, the head returns to the feeder location to begin another tour,
unless nozzle changes are required. The heads of this machine can be similar to the heads of turret type machine. The difference is that it is located on top of the arm [12]. A
head is used to grasp a few components from the feeder locations and mount them on the PCB (e.g. the Quad 400 series [12]).

2.5 Sequential Pick-and-Place Machine
According to Kumar and Li [23], the typical machines of this type have placement head mounted at the end of an arm. The arm can move in the X-direction only, simultaneously with the head movement in Y-direction. The nozzle on the head can move in Z-direction to perform pick-and- place operations. The placement arm starts by moving to the tool magazine to equip itself with the proper nozzle. Next, it moves to pick a particular component from the feeder location, and then place the component at the appropriate location on the board. If the following component is of the same type, the arm moves directly to feeder slot to perform the subsequent pick-and-place operation. Otherwise, the arm goes to tool magazine [24, 23]. The Quad IIIC is an example of this machine type [24].

3. Models And Heuristics
Four basic PCB component placement rules are usually adopted [25]: (a) sequence the component placement for minimum routing time, (b) arrange feeder reels so as to
minimise component pickup time, (c) place identical SMDs in one pass, and (d) sequence placement according to component size. Some works have addressed the problems of feeder setup and placement sequence independently by making assumptions about the rest of the problem, and some prefer to solve both problems as an integrated solution [2]. The question of where (i.e. in which slots) the feeder reels should be attached in each
placement machine is referred to as feeder setup [15], feeder rack assignment problem [18], component-feeder arrangement [4], reel positioning problem [13, 22], feeder
assignment [24, 26], feeder allocation [12], or magazine assignment [10]. In this paper we use the term feeder setup refer this problem.

3.1 Models and Heuristics for Dual delivery
An Adaptive Simulated Annealing algorithm has successfully been applied by Tirpak et al. [15] to solve the feeder, nozzle and placement optimisation problems for the Fuji NP-132. Each iteration of the algorithm requires two main steps: generate a candidate solution and determine if the solution is accepted. Each candidate solution includes a nozzle setup, a feeder setup, and a placement sequence for the two heads. Cheapest insertion and nearest neighbor path construction heuristics are used to construct a placement sequence. A constraint satisfaction swapping heuristic is applied to generate feeder and nozzle setups.
The results tested in a Motorola factory show a 3%-12% improvement over the original assembly times. Since feeder movement is a critical issue for improving the performance of this machine, Grotzinger [7] and Ahmadi et al. [11, 13] both addressed this problem in their work. They identified a hierarchical framework consisting of three optimisation problems; the component allocation and partitioning, the placement sequence, and feeder setup.

3.2 Models and Heuristics for Turret Type
Since the PCB table moves simultaneously and independently in X and Y-directions, the chebychev distance can be used to determine PCB table movement time [27]. The turret rotation time is dictated by the component with the slowest turret rotation rate loaded in
the turret since larger and heavier components are more difficult to hold in place by the suction nozzle and must move slower [2]. Francis et al. [27] have modeled the feeder setup problem for this machine as a quadratic assignment problem, since the feeders are assigned to slots on the feeder carriage and the cost of the assignment is impacted by the location of other feeders.

Klomp et al. [18], view a feeder (and its corresponding cluster i.e. set of locations served by a single feeder) as a node in a complete graph. Computational result show that the gap between the solution found and the lowerbound is relatively small (about 20% in the three machine case), which implies that much of PCB table and feeder rack movements fall within the turret rotation time.