Combining benders decomposition and column generation for server allocation and scheduling in multiple queues

This paper addresses the server allocation and scheduling problem in a service system with multiple queues at different locations. Each queue experiences stochastic and time-varying customer arrivals. In addition to fixed servers, mobile servers can relocate to cope with fluctuating demands. Our motivation stems from applications in large scenic spots and airports. For example, at a partner large scenic spot, employees are dynamically allocated to various entrances to shorten queues for tourists. Similarly, in large airports, security teams are dynamically assigned to different terminals to reduce passengers’ security queues. The introduction of mobile servers enhances service levels and reduces queue lengths but complicates routing and scheduling due to time-varying travel times. We formulate a nonlinear mixed-integer model of the problem. By exploiting the structural properties of the original model, a mixed-integer convex programming model is developed. We then develop efficient exact algorithms based on Benders decomposition and column generation, providing high-quality solutions. Evaluation using a real-world dataset from a large partner scenic spot shows that the proposed framework reduces employee working time by an average of 14.13% compared to current schedules. The results also reveal two key roles of mobile servers: peak support and off-peak continuity. Airport datasets further confirm that our approach reduces server workloads while satisfying all queue-length constraints, outperforming state-of-the-art methods.