Optimizing the route of an assembly arm

ABSTRACT: Optimizing the route of an assembly arm is a procedure of finding placement tours of pick and place robot's arm for the equipping of Printed Circuit Board (PCB). The problem of finding placement tours is a production planning problem with n positions on a board as the assembly points and n bins containing n components as n locations for the bins, called cell points. PCB manufacturing requires a good route for the robot that makes production, so that time savings can be achieved. In the robots considered, working time of the robot is proportional to the distance travelled, and the problem appears as a combination of the Traveling Salesman Problem (TSP) and the matching problem. Such a problem is a special type of the TSP, known as the bipartite TSP. Given the complete graph on vertices, a weight function and a partition of into 2 subsets of size , bipartite TSP is to find a Hamiltonian cycle of minimum weight that visits the subsets in a fixed alternating order. The problem has simulated many efforts to find an efficient algorithm but no algorithm is presently available that can solve for the optimal solution of this problem in polynomial time. As its complexity is NP-Complete the general opinion of scientists is that a fast polynomial algorithm does not exist. The aim of this thesis is to introduce an efficient approximation algorithm for medium-sized (up to 500 assembly points) problems and to derive bounds for the typical length of optimal tours. We present an iterative algorithm which applies a cutting model to get a shorter lower bound by adding cuts to the Linear Programming (LP) relaxations and a combined heuristic algorithm for finding an acceptable upper bound when the optimal integer solution is not found. The method is applied for both Dantzig-Fulkerson-Johnson and Miller-Tucker-Zemlin models. As the problem is NP-Complete, it is often unnecessary to have an exact solution. Thus a special heuristic algorithm is developed to obtain near-optimal solution in a reasonable time, suitable for practical purposes. The developed heuristic method is applied a constructive scheme combining two famous efficient heuristics: Nearest Neighbor and Insertion algorithms. …………………………………………………………………………………………………………………………………………………………………………………………………………