10.4 Problems 153Fig. 10.12. The PCB examplemachine with a robot arm makes vias (a kind of drill operation) at points
A, B,..., L. A high volume of PCB's are processed one after another.
a) Suppose that the robot arm moves in horizontal as well as vertical direction
using a single motor. It switches its direction in an infinitesimal time unit.
The CNC programmer uses the following logic to find the sequence of vias
to be processed: Start from A, go to the closest neighbor if it has not been
processed yet. Break the ties in terms of ascending lexicographical order of
locations. Once the initial sequence (Hamiltoncan tour) is obtained, examine
the nonconsecutive pair of edges of the tour if it is possible to delete these
edges and construct another tour (which is uniquely determined by the four
locations) that yields smaller tour in length. In order to check whether there
exist such an opportunity, the programmer calculates the gains associated
with all possible pairs once. Suppose that the connections between (a, /3) and
(7, S) is broken in the current tour. Then, new connections (a, 7) and (/3, 5) is
constructed in such a way that some portion of the tour is reversed and a new
tour spanning all locations is obtained. Once all the gains are calculated, all
the independent switches is made. This improvement procedure is executed
only once.
- Find the initial tour after deciding on the appropriate metric.
- Improve the tour.
b) What if the robot arm moves in any direction using its motor?
c) What if the robot arm moves in horizontal as well as vertical direction
using two independent but identical motors?
d) Suppose that we have N PCBs to process. All the operation times are
identical, each taking p time units. The robot arm moves at a speed of one
leg distance per unit time along each direction. Let C\ be the cost of making
the robot arm to move along any direction using the single motor and Ci be
the cost of adding a second motor. Using the improved solutions found, which