Optimizing the route of an assembly arm

Abstract

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. …………………………………………………………………………………………………………………………………………………………………………………………………………

ÖZ:

Bir montaj kolu rota optimizasyonu seçme ve yerleştirme robot kolunun yerleştirme turlarını bulma işlemidir ki Baskılı Devrenin onatılması için kullanılır. Yerleştirme turları bulma sorunu bir üretim planlama sorunudur. Bu problemlerde montaj noktaları için n tane pozisyon vardır ve her birisinin içerisinde bir tane birleşen parçası yerleştirilmiş n tane kutu vardır ki bunlara hücre denilir. Baskılı devre üretimi zaman tasarufu elde edebilir böylece üretim yapan robot için iyi bir rota bulunması gerekir. Ele alınan robotlarda çalışma süresi gezilen mesafe ile orantılıdır. Bu tip problemler Gezgin Satıcı Problemi ve Eşleştirme Probleminin birleşimi olarak görülür. Böyle bir problem özel gezgin satıcı problemidir ki ikili gezgin satıcı problemi olarak bilinir. Verilen tamamlanmış grafikde G=(V,E), 2n köşe noktası ve ağırlık fonksiyonu W:E￫R≥0 ve V iki n taneli alt kümeye bölünen ikili gezgin satici problemi minumum agırlıklı Hamilton çevrimi bulmakdır ki bir alt kümeyi sabit bir alternatif sırayla ziyaret eder. Etkin bir algorithma bulmak için çok çaba harcanmış ama halen bu sorunun optimal çözümü bulmak için polinom zamanda bir algoritma bulunmamıştır. Bilim adamlarının genel görüşüne göre hızlı bir polinom algoritma yoktur çünkü bu problem bir polinom zamanlı olmayan-tam problemidir. Bu tezin amacı orta büyüklükteki soruları (500 montaj noktasına kadar) için etkin bir yaklaşım algoritması tanıtmaktır. En uygun turların uzunluğunun sınırlarını türetir. Biz bir yenilenen algoritma sunuyoruz ki bir kesim modeli ve birleştirilmiş sezgisel algoritmadan oluşur. Optimal tam sayı çözüm bulunmadığında kesim modelini daha yakın bir alt sınırı ve sezgisel algoritmayı kabul edilebilir bir üst sınırı bulmak için kullanıyoruz. Bu yöntem Dantzig-Fulkerson-Johnson ve Miller-Tucker-Zemlin modelleri için uygulanmıştır. Problem NP-Tam olduğu için çoğu kez kesin bir çözüm olması gereksizdir. Bu nedenle özel bir sezgisel algoritma geliştirilmiştir ki neredeyse optimal çözümü makul bir süre içerisinde ve pratik amaçlar için uygun olan cevabı elde ediyor. Geliştirilmiş sezgisel yöntem iki tane ünlü etkin yapısal sezgiselin birleşimidir. Bahsedilen iki sezgisel algoritma en yakın komşu ve yerleştirme algoritmalarıdır.