A column generation driven heuristic for order-scheduling and rack-sequencing in robotic mobile fulfillment systems

Optimizing the customer-order picking process in robotic mobile fulfillment systems depends on two closely related decisions: How to schedule the processing of orders on a workbench of limited size and how to sequence the racks that are lifted and transported by automated guided vehicles (robots) to the picking-station to supply the requested items for order-processing? Minimizing the number of these so-called rack-visits at the picking-station is well suited to reduce robot utilization and the makespan of customer-order processing. We present a heuristic solution approach for the order-scheduling and rack-sequencing problem at a single picking-station using column generation to partition the set of customer-orders into batches, while minimizing the number of rack-assignments to batches, which in turn minimizes the rack-visits. The generated batches possess a property that allows to derive an order-processing schedule straightforwardly. Then, we refine the heuristic solution by rearranging the processing of batches and their assigned racks. A comprehensive and comparative computational study demonstrates superior performance of our approach on the vast majority of instances compared to several heuristics from literature, both in terms of solution quality with up to 15% fewer rack-visits and runtime. The average worst-case optimality gap in comparison with valid lower bounds is 10.72% and the solutions are close to optimal if around ten orders can be processed simultaneously on the workbench. It is also shown that the proposed heuristic provides very competitive results for the order-scheduling and rack-sequencing problem at multiple picking-stations.