Minimum time point assignment for coverage by two constrained robots

This paper focuses on the assignment of discrete points to two robots, in the presence of geometric and kinematic constraints between the robots. The individual points have differing processing times, and the goal is to identify an assignment of points to the robots so that the total processing time is minimized. The assignment of points to the robots is the first step in the path generation process for the robots. This work is motivated by an industrial microelectronics manufacturing system with two robots, with square footprints, that are constrained to translate along a common line while satisfying proximity and collision avoidance constraints. The N points lie on a planar base plate that can translate along the plane normal to the direction of motion of the robots. The geometric constraints on the motions of the two robots lead to constraints on points that can be processed simultaneously. We show that the point assignment for processing problem can be converted to a maximum weighted matching problem on a graph and solved optimally in O(N^3) time. Since this is too slow for large datasets, we present a O(N^2) time greedy algorithm and prove that the greedy solution is within a factor of 3/2 of the optimal solution. Finally, we provide computational results for the greedy algorithm on typical industrial datasets.