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

A major drawback of most automated warehousing solutions is that fixedly installed hardware makes them inflexible and hardly scalable. In the recent years, numerous robotized warehousing solutions have been innovated, which are more adaptable to varying capacity situations. In this paper, we consider robotized sorting systems where autonomous mobile robots load individual pieces of stock keeping units (SKUs) at a loading station, drive to the collection points temporarily associated with the orders demanding the pieces, 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, so that we face a very challenging scheduling environment in which the following operational decisions must be taken in real time: First, since pieces of the same SKU are interchangeable among orders with a demand for this specific SKU, we have to assign pieces to suitable orders. Furthermore, each order has to be temporarily assigned to a collection point. Finally, we have to match robots and transport jobs, where pieces have to be delivered between loading station and selected collection points. These interdependent decisions become even more involved, since we (typically) do not posses complete knowledge on the arrival sequence but have merely a restricted lookahead of the next approaching products. In this paper, 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.