An Almost Time Optimal Route Planning Method for Complex Manufacturing Topologies
Sprache des Vortragstitels:
Englisch
Original Tagungtitel:
EuroCAST 2015
Sprache des Tagungstitel:
Englisch
Original Kurzfassung:
A main trend in today's automation industry is to reduce process time in order
to increase production rate. In many applications like welding, punching and
cutting, the execution sequence of the welds, holes etc. is crucial for the process
time. The trajectories of individual manufacturing processes are defined as
B-Splines and are connected via straight lines. Finding the optimal topology
can be treated in the same way as the well-known traveling salesman problem
(TSP).While finding the optimal solution for the TSP is possible for small scaled
problems, for more complex task the solution can only be approximated.
In this work the TSP is modeled as an undirected weighted graph. The solution
is approximated by the Christofides algorithm, which yields an approximation
of the optimal solution in polynomial-time. In more detail, the value of the
objective function for the approximation found by the Christofides algorithm will
be at worst 50% higher than the optimal solution. The main focus of this work is
the choice of the weights of the graph, which have a strong influence on the quality
of the solution. The performance of the algorithm is extensively examined by
means of simulations, and is compared with random execution sequences.
Forschungs-