Optimal control of queueing systems with non-collaborating servers

摘要

We study the dynamic server allocation problem for tandem queueing systems with an equal number of stations and servers. The servers are flexible, yet non-collaborative, so that at most one server can work at a station at any time. The objective is to maximize the long-run average throughput. We show that if each server is the fastest at one station, then a dedicated server assignment policy is optimal for systems of arbitrary size and with general service requirement distributions. Otherwise, the optimal policy is more complex as servers must divide their time between stations. For Markovian systems with two stations and two servers, we characterize the optimal policy completely. For larger Markovian systems, we use our results for two-station systems to propose four heuristic server assignment policies and provide computational results that show that our heuristics are near-optimal. We also compare collaborative and non-collaborative settings to evaluate the benefits of dynamic server allocation, as opposed to collaboration, in systems with flexible servers. We conclude that the loss in the long-run average throughput due to lack of collaboration is mitigated by the similarity of the tasks in the system, and cross-training can still be beneficial in non-collaborative systems.