We consider the problem of allocation and routing a fleet of robots to service a given set of locations while minimizing makespan. The service start times for the locations are subject to AND/OR type precedence constraints. Spatio-temporal constraints prohibit certain states from all feasible schedules where a state is defined as a tuple of robot and it’s location  pairs. In this talk we analyze the sub-problem generated when assignment of locations to the robots and their order of visit has been fixed. We show that it is NP-Complete to determine feasibility and develop an efficient scheduling procedure, both for the sub-problem. We then present two novel makespan minimizing heuristics for the overall problem, the first motivated by  slack based temporal flexibility and the second based on the routing component. We conclude with an anytime procedure for the overall problem and demonstrate results on a real world manufacturing setting.

Stephen Smith

Willem Van Hoeve

Zachary Rubinstein

Chung-Yao Chuang