Robotized sorting systems: Large-scale scheduling under real-time conditions with limited lookahead

To meet the expectations of demanding customers, there is a trend toward warehouse automation, especially in large e-commerce distribution centers. In this context, this paper considers robotized sorting systems, where autonomous mobile robots are applied to automatically sort products after picking. The robots load individual pieces of stock keeping units (SKUs) at a loading station, drive to the collection points temporarily associated with customer orders, and autonomously release them, e.g., by tilting a tray mounted on top of each robot. In these systems, a huge number of products approach the loading station with an interarrival time of very few seconds. Hence, we have a very challenging real-time environment for the following decisions: First, since pieces of the same SKU are interchangeable among orders with a demand for this specific SKU, we must assign pieces to suitable orders. Furthermore, each order must be temporarily assigned to a collection point. Finally, we must assign robots to transport jobs. These interdependent decisions become even more involved, since we (typically) do not possess complete knowledge on the arrival sequence but have merely a restricted lookahead of the next approaching products. We show that even in such a fierce environment sophisticated optimization, based on a novel two-step multiple-scenario approach applied under real-time conditions, can be a serviceable tool to significantly improve the sortation throughput. With our approach a limited-lookahead system is shown to almost reach the performance of a (hypothetical) system with complete knowledge on the approaching products.