Prasad Chalasani, Los Alamos National Laboratory, NM, USA

Rajeev Motwani, Stanford University, Stanford, CA, USA

Anil S. Rao, Qualcomm, Inc., San Diego, CA, USA

We consider the following application from industrial automation: parts arrive on a conveyer belt and have to be grasped by a robot arm of finite capacity and then delivered to specified delivery points for packaging or other processing. An intelligent choice of the order of picking up the parts can significantly reduce the total distance traveled by the robot arm and, consequently, its cycle time. We model this application as problems of the form: Given n identical parts initially located on a conveyer belt, and a robot arm of capacity k parts, compute the shortest route for the robot arm to grasp and deliver the n parts, handling at most k at a time. We consider arbitrary finite k as well as unbounded k. We also allow the belt to be either motionless or moving with a known fixed velocity. For the moving belt problem, we require all parts to be delivered to a specified origin point, while for the static case we allow up to n different destinations for the parts. In either case, since the optimization problems that result are NP-hard, the focus is on devising efficient approximation algorithms. While the approaches taken for the static and the moving belt cases are very different, all our algorithms are simple to implement, efficient, and produce a solution within a small constant factor of the optimum.