Optimal scheduling in some multiqueue single-server systems

摘要

The authors address the problem of optimal scheduling in a multiqueue single-server (MQSS) model. An arriving customer joins queue j with probability 1/N, j=1,. . ., N. The server visits each queue for a random period of time whose duration is independent of the queue length. At the end of a visit period, either all customers of the attended queue leave the system (variant I), or only customers that were present in the queue upon the arrival of the server leave the system (variant II). A scheduling policy is a rule that selects the next queue to be visited by the server. When the controller has no information on the state of the system, it is shown that a cyclic policy minimizes the expected number of customers in the system. When the controller knows the number of customers in each queue, it is shown that the so-called most customers first (MCF) policy minimizes, in the sense of strong stochastic ordering, the vector of the number of customers in each queue whose components are arranged in decreasing order.