Customer scheduling under queueing constraints

A scheduling problem of an exponential single server with a finite queueing capacity that serves customers from n heterogeneous classes is considered. Arrivals are Poissonian and every class has its own rate and its own finite waiting room. The waiting rooms can be of arbitrary size. Arriving customers that find a full queue are lost. Of particular interest is finding a scheduling policy that allows service preemption and has a weighted throughput which is close enough to the optimal one. As an optimal scheduling policy is extremely hard to find, a different methodology is used to tackle the problem. First, the optimal weighted throughput is bound from above, and the asymptotically optimal policy is found. Then, based on the bounding technique and the asymptotically optimal policy, a new policy, the overflow scheduling policy, that provides a weighted throughput which is very close to the upper bound is proposed. The quality of the policy is demonstrated by various examples