Abstract 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 [...]