Kumar and Luo [19] view the placement sequencing problem on a Fuji FCP-IV, as a “generalised Traveling Salesman Problem (TSP)” where not only the overall travel time depends on the travel sequence (as in standard TSP), but even the distances between any pair of nodes is sequence dependent (whereas in the standard TSP such distances are constant regardless of travel sequence). Since feeder carriage movement is considerably slower than the PCB table movement and turret rotation, and furthermore, these three operations occur concurrently, the whole process is dependent up on the feeder carriage movement. Then they show that an optimal tour for the distance matrix, dij provides a desired optimal placement sequence (for a given slot assignment) such that it visits all
components of the same part number consecutively. If switching components is required, then the feeder carriage should be moved to the adjacent feeder slots in order to obtain the optimal solution. They show consistent improvement of over 25% in overall assembly time
compared to the solution generated by the chip placement machine optimiser at Lexmark, Inc. For some cases, the rotation of the turret, which takes fixed time, determines the travel time, and thus implies that their optimisation algorithm will be more efficient on machines with faster turret rotation or with smaller rotation angles.

Khoo and Loh [4] employed a genetic algorithm (GA) to generate the component placement sequence and feeder setup by formulating it as a multi-objective optimisation problem constrained. The prototype system has demonstrated the ability to generate a component
placement sequence and feeder setup slightly better than Leu et al.[28].

More recently, Ellis et al. [2] have developed heuristics for feeder setup and component placement sequencing by using a constructive heuristic that groups together the components with similar PCB table speed and turret rotation speed. The constructive heuristic uses the surrogate function which can provide a method to approximate penalties for feeder carriage movements, changes in turret rotation speed and changes in PCB table
speed. After the initial feeder setup and placement sequence have been constructed, the two-opt heuristic is applied to search for placement time improvement. Results indicate that the solutions are close to lower bound and the computational time required to generate the initial solutions is minimal (less than 3 minutes). However, the computational time to generate the improved solution is high, and increases as the problem size increases. For
instance, the initial solution computation time is 2 seconds while improvement solution requires 1586 seconds for the smallest PCB. Larger PCBs requires 164 seconds to generate initial solution and 43200 seconds to compute the improved solution.

3.3 Models and Heuristics for Multi-Station
Csaszar et al. [16] conducted research to optimise the multi-station machine, which has a single head and a single nozzle per station. The system was designed to emulate human experts. They divided the allocation problem into two sub-problems, that is the assigning of components to the stations, and the arrangement of components within station to achieve maximum throughput by minimising the head movements. The expert system is split into four
phases: simulator pre-processing, placement, refining and conversion phases. The results show that the expert systems uses an average of 16.14% fewer feeder slot than the vendor’s software and throughput improve by 13.47% to 15.95%. They prove that by using the cost function of the number of placements together with pick-and-place time they gain better results than using just pick-and-place time.

3.4 Models and Heuristics for Multi-Headed
Since the arm and head can move simultaneously in both the X and Y axis, Altinkemer et al. [12] used the chebychev distance and calculated the distance as the maximum of the movements in the X and Y direction. They consider two cases; when the feeder locator moves and when the feeder locator does not move. When the feeder locator moves, the feeder of the component type that will be processed next can move towards the tool
magazine while the head is mounting another component type, so the distance between the feeder locations and the points on the PCB can be measured from a fixed point next
to the tool magazine. The simultaneous movement enables each component type to have the same origin and destination point, and thus allow the formulation to be an independent capacitated vehicle routing Problem. Since the distance between a point on the PCB and feeder is not dependent on where the component is located among feeders, the feeder setup problem does not have to be integrated with the pick and place sequencing ecisions. For the case where the feeder locator does not move, they formulate the problems as a combination of assignmentlike and vehicle-like problems. They first solve a vehicle routing problem (VRP) for each component type at every possible feeder location, and then use this feasible solution as the cost of assigning the component type to the particular feeder location. They argue that their integrated algorithm provides a feasible solution with an error gap less than or equal to the maximum error gap of the VRP costs.

Lee et al. [29] developed heuristics which are based on dynamic programming and the nearest neighbor TSP to solve the optimisation of multi-head surface mount machine. They choose a hierarchy method to find the solution by starting with the construction of reel-groups, then the assignment of reel-groups and finally sequencing of pick-and-place movements. Since nozzle changes are time-consuming and the number of nozzle changes is proportional to the number of nozzles to be used, they choose a nozzle for each reel in such away that the total number of nozzles is minimised. Then, they assign the reels to heads in such away that each head has about the same workload. Since nozzle changes are the most timeconsuming operation, they decided to first determine the order of nozzle changes before determining the sequence of pick-place movements. The simulation results indicate that their method achieves an average saving of 18% in PCB assembly time over the heuristic algorithm supplied by Yamaha.

Burke et al. [8], have introduced a three phase heuristic to deal with the assembly of multiple printed circuit board types with different batch sizes on a single machine
without set-ups between board types. Experimental result shows that their approaches are very promising.

3.5 Models and Heuristics for Sequential Pick-and- Place

Kumar and Li [23] model the optimisation of feeder setup and component placement sequence for sequential pickand- place machine as an instance of a linear integer
programming problem. They solve the problem by determining an assignment of pickup slots and a component assembly sequence for each individual nozzle. Heuristics such as nearest neighbour, nearest insertion, furthest insertion, and random generation are used to
construct an initial assembly sequence, and the other heuristics such as 2-opt, 3-opt, and Or-opt are used to improve upon the initially generated assembly sequence. Simulation results show a consistent assembly time saving of 25% over the current approach used in the factory.

Ball and Magazine [30] formulated the placement sequence problem as a type of directed postman problem. They show that balance and connect heuristic can be applied to this problem. Ahmadi and Mamer [31] have modelled the problem of sequencing the part types for placement and the problem of scheduling the movement between points on the PCB as a collection of interdependent travelling salesman problems. The computational results shown that the approximation of the problem by a sequence of TSPs was able to produce
significant increases in throughput.

Fu and Su [32], and Hop and Tabucanon [26] strongly believe that robotic travel routing should be based on relative coordinates to obtain a better solution because the robotics, board and magazine are simultaneously moved at different speeds during assembly. Their dynamic pick and place (DPP) model has been introduced by Su et al. [33]. In the DPP model, the robot moves vertically along the Yaxis (in the optimal condition), while the PCB table and feeder rack move horizontally along the X-axis, and the pickup and placement point are dynamically allocated. The optimal condition occurs when the robot travels only in the Y direction, and no movement in the X direction is observed [10]. Wang et al [10] have applied off-line heuristics to improve the placement sequence and feeder setup to take advantage of the DPP model. They sequence the placement first by considering the adjacent placement to be as close as possible (minimum travel in X direction) to achieve minimum total travel while placing each component in its proper location. Next, they organise feeder slots to let all adjacent slots have the highest exchange frequency pickups of the same component type. The exchange frequency is defined as an index that counts
the exchange frequency between two different component types for succeeding pickups. They claim that the approach provides a rapid solution to even very large problems, and
demonstrate the on-line implementation to ensure the feasibility of the approach. Nevertheless, Wang’s approach was still based on a fixed coordinate system using the TSP
method to obtain robotic travel routing [34]. To resolve such a dynamic combinatorial problem, Fu and Su [32] have applied Genetic Algorithms (GA), Simulated Annealing (SA) and Tabu Search (TS). In the GA approach, a possible solution is represented by chromosome, and each gene in the chromosome represents the insertion point and component. The fitness function is defined as the cycle time of the robotic assembly. In the
SA and TS algorithms, the possible solution is represented by vector. The cycle time of the robotic assembly is defined by the energy function in SA or the objective function in TS. These approaches can simultaneously arrange the insertion sequence and assign the magazine slots and yield a better performance compared to the conventional approach (fix pick-and-place model). Computational experiments indicate that the GA’s performance is the worst among these approaches in a larger number of insertion points and/or component types. A GA requires more computational time for the larger size of tested cases for a near optimal solution to be obtained. The performance of TS is better than the performance of
the other two approaches in smaller number of problem sizes. SA is a robust technique that has better performance in a large number of problem sizes if the computational time is limited. Implementation results also demonstrate that the proposed approach is superior to that of Wang’s approach.

More recently, Hop and Tabucanon, proposed two new heuristic algorithms that are multiple criteria approaches [26] and extended DPP (EDPP) model [35], to improve Wang’s approach. The multiple criteria approach uses the trade-off between two strategies: minimise the PCB table travelling distance where the strategy is ‘assemble by
area’, and minimise the feeder rack travelling distance where the strategy is ‘assemble by component type’. The principle is to select components to assemble which have the same component type as close to each other as much as possible. The algorithm starts with an initial solution from Wang’s [10]. Then a new feeder setup is constructed based on criteria assembly by component type. Next, the assembly sequence is generated based on the principle of assemble by area. These two steps are iterative, and will be terminated by a stopping criteria. Computational results indicate that the total reduction time ranges between 4% for lower density board, to 28% for higher density board compared to Wang’s approach. The main difference between DPP and EDPP is that the EDPP considers not
only the robot arm motion to be the problem’s objective, but also the feeder motion and PCB table motion [26]. The result suggests that the EDPP model is superior to the DPP
model.

4. Conclusions
Our survey found that based on the specification and operational methods, placement machines may be arranged into five categories: dual-delivery, multi-station, turret style, multi-head and sequential pick-and-place. By classifying placement machines into these categories based on their common characteristics and operational methods, we have shown the relation between models, assembly machine technologies and heuristic methods. Most
researchers highlight that the crucial moves which are subject to optimisation are the feeder carrier movements [7, 19, 31]. Currently, there are few works that consider the DPP model in pick-and-place sequencing. Interesting results have been reported by applying the DPP model to the sequential placement machine and it is claimed that the DPP model is superior to the fix-pick-and-place (FPP) model. Therefore, the application of this model to other
type of placement machines in future may give good solutions.