The cafeteria problem: order sequencing and picker routing in on-the-line picking systems

This paper is dedicated to the cafeteria problem: given a single waiter operating multiple counters for different dishes arranged along a line and a set of customers with given subsets of dishes they desire, find a sequence of customers, which may not overtake each other, and a service schedule for the waiter, such that the makespan is minimized. This generic problem is shown to have different real-world applications in order picking with blocking restrictions. We present different heuristic and exact solution procedures for both problem parts, i.e., customer sequencing and waiter scheduling, and systematically compare these approaches. Our computational results reveal that the largest performance gains are enabled by not strictly processing order after order. Instead, the waiter should be allowed to flexibly swap between customers waiting along the line. Such a flexible service policy considerably reduces the makespan and the total walking distance of the waiter.