Server Routing-Scheduling Problem in Distributed Queueing System with Time-Varying Demand and Queue Length Control
研究了分布式排队系统中服务器在多个队列间移动的路由调度问题，提出动态规划模型和启发式算法，在机场和景区实验中减少总工作时长且不违反队列长度约束。
We study a server routing-scheduling problem in a distributed queueing system, where the system consists of multiple queues at different locations. In a distributed queueing system, servers are shared among multiple queues, and they travel between queues in response to stochastic and time-varying demands. Although server traveling can improve service levels and shorten queue lengths, server routing and scheduling is complicated. We propose a dynamic programming model to solve this special routing-scheduling problem with time-varying demand, stochastic travel time, and queue-length constraints. In order to tackle large-scale practical instances, we design a dynamic programming-based rollout heuristic algorithm. Experiments on large-scale airports and scenic spots show that our approach reduces the total working periods of servers/employees without violating queue-length constraints. Furthermore, we demonstrate that our algorithm outperforms existing benchmark methods and the practical schedules of a scenic spot. Funding: Financial support from the National Natural Science Foundation of China [Grant 71972133] is gratefully acknowledged. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2022.0099 .