Technical Report CS0592

Title: Optimal Routing to Two Parallel Heterogeneous Servers with Resequencing
Authors: S. Ayoun and Z. Rosberg
Abstract: Customers arrive to a single service queue according to a Poisson process with rate LAMBDA, from which they are routed to two parallel heterogeneous and exponential servers whose rates are Mu1 > Mu2. Customers are released from the system after service completion, according to their arrival order - a requirement introducing additional resequencing delays. Customers which are delayed due to resequencing are waiting in a resequencing queue. We consider the optimal routing problem under the class of fixed-position routing policies, that route customers to the faster server from the head of the service queue, and to the slower server from position J. The cost function is taken as the long-run average holding cost of the customers in the system. We show that an optimal stationary policy exists and is of the following type: The faster server is kept active as long as the service queue is not empty. The decision whether or not to route a customer to the slower server is independent of the state of the resequencing queue. If the position J is greater than Jo=???, Alph=??? then customers are routed to the slower server if and only if the length of the service queue is at least m* (a threshold policy). We also show that the routing position Jo is 'optimal' in the sense that every policy can be improved by dispatching a customer from position Jo (if not empty), rather than from position J.

Keywords: Exponential Queues, Parallel Servers, Resequencing, Routing, Optimal Control, Markov Decision Processes.

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