Header and Body 3


Tercio is a centralized task assignment and scheduling algorithm that scales to multi-agent, factory size problems and supports real-time planning with temporal and spatial-proximity constraints. Tercio takes as an input a set of tasks, temporal interval constraints, agents and an objective function. The algorithm first computes an optimal agent allocation by solving a mixed-integer problem, which includes terms for balancing the amount of work across each agent. Given the agent allocation and a task structure, Tercio sequences the tasks using an analytical test to ensure that all temporal constraints are satisfied. If the schedule is not within a user-specified process duration, Tercio attempts to find the next-best agent allocation. Once the schedule satisfies the temporal specifications, then agent and spatial-resource sequencing constraints are added to the problem. The resulting Simple Temporal Problem (STP), composed of the interval temporal constraints, is compiled into a dispatchable form which guarantees that for any consistent choice of a time point within a flexible window, a solution can be found through one-step propagation of interval bounds. This form maintains flexibility to increase robustness to disturbances, and has been shown to decrease the amount of time spent recomputing solutions in response to disturbances for randomly generated structured problems by up to 75%.