Friday, 11:00 - 11:25 h, Room: H 0106


Cornelius Schwarz
The laser sharing problem with fixed tours

Coauthor: Joachim Schauer


In the Laser Sharing Problem (LSP) a set of industrial arc
welding robots has to perform a series of welding seams. For this task they need
to be connected to a laser source supplying them with the necessary energy.
In principle, a laser source can serve up to six
robots but only one at a time. The task of the LSP is to find an assignment of a given set
of laser sources to robots and collision-free robot tours so that welding seams
performed using the same laser source do not overlap in time and the overall
makespan is minimal.
Prescribing the robot tours we obtain a pure scheduling problem referred to as LSP-T.
We will show that LSP-T can be seen as an extension of the famous job-shop problem. Then
we extend the geometric approach of Akers for the two job-shop problem to LSP-T
leading to a polynomial algorithm for the two robot case.
Since the job-shop problem is a special case of LSP-T the three robot case is
already NP-hard. We will propose a pseudo-polynomial algorithm for it based on
transversal graphs and show how to derive a FPTAS. By this we fully settle the
complexity of LSP-T with a constant number of robots.


Talk 2 of the invited session Fri.1.H 0106
"Optimizing robot welding cells" [...]
Cluster 13
"Logistics, traffic, and transportation" [...]


  The majority of financial loan companies provide the service of getting North Carolina Payday Loans for U.S. citizens. On the global pharmaceutical market this medicine was issued in 2003 by two companies - Eli Lilly and ICOS. Initially, permission to sell Cheap Cialis was obtained in Europe, Australia, New Zealand.