Technical Report CS0555

Title: Customer Scheduling Under Queueing Constraints
Authors: Z. Rosberg and P. Kermani
Abstract: We consider a single server that serves customers from n different classes. Customers arrive at the system according to n independent Poisson processes, each of which has rate Ai, 1<=i<=n. Every customer of class i requires a service duration that is exponentially distributed with mean 1/miuI. All service requirements are assumed to be mutually independent, and independent of the arrival streams. Every customer class i has its own waiting queue whose length Ni is assumed to be finite. Arriving customers that find a full queue are lost. We are interested in finding a scheduling policy that allow service preemption and has a weighted throughput which is close enough to the optimal one.

When queue sizes are finite, finding the optimal scheduling policy is known to be untractable and therefore we apply a different methodology to tackle the problem. First we bound the optimal weighted throughput from above, and find the asymptotica.Ily optimal policy. Then we propose, based on our 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.

The upper bound is obtained by considering an ideal system, where the server optimally serves each class .of customers for a pre-determined long run proportion of time, irrespective of the existence of customers from other classes. Then, we optimize over all possible proportions. The asymptotic analysis is carried out for gaining insight on the structure of good scheduling policies.

Keywords: Exponential Queues, Finite Queues, Customer Scheduling, Markov Decision Processes, Overflow queues.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1989
To the main CS technical reports page

Computer science department, Technion