Coupled task scheduling for heterogeneous multi-robot system of two robot types performing complex-schedule order fulfillment tasks

This paper addresses multi-robot task scheduling for two robot types arising from heterogeneous robotic order fulfillment systems. The heterogeneous multi-robot system comprises two types of robots with specialized and complementary capabilities to achieve long-cycle and multi-station order fulfillment tasks on a logistic network. This problem is extremely challenging because of innate complex-schedule constraints of tasks and coupled temporal-spatial relations between all robots. After set-theoretic and mixed integer linear programming problem formulations, we use coupled approach, instead of decoupled approaches to explore the synergy between heterogeneous robots, which is different from most existing similar works. To model the structural (complex-schedule) and quantitative (temporal-spatial) coupledness of robots' time-extended task schedules, an edge-weighted and vertex-weighted block sequence graph is introduced. Based on this model, time-extended task scheduling is achieved using rank-minimal heuristic and genetic algorithm metaheuristic. Theoretically, this model is complete and non-redundant. Empirically, compared with decoupled approach, optimality and efficiency of the proposed methods are evaluated on designed instances. The results demonstrate that coupled methods can achieve near-optimal solutions with higher performance ratio than decoupled methods in moderate time. At the same time, coupled methods can leverage spatial and temporal properties of miscellaneous tasks, and balance instantaneous and time-extended decisions to achieve tight collective synergy in the long run. (C) 2020 Elsevier B.V. All rights reserved.