Resequencing Control for a Queueing System with Two Heterogeneous Servers

Abstract

We consider a heterogeneous M/M/2/L queueing system where the two servers may work at different rates. A class of threshold type scheduling policies, called fixed position policies (FPP's), is introduced. If FIFO delivery is required, departures (customers, jobs, messages) must wait at the receiving node to be put back into proper sequence. Therefore, they incur resequencing delay in addition to whatever previous delays they experienced. The challenge is to find a method for analyzing and evaluating the performance of the FPP's. We develop a new approach, based on an imbedded Markov chain model, for obtaining the resequencing delay characteristics of FPP's. Closed-form expressions for the distribution and the mean of the resequencing delay are derived. For a given threshold value, the choice of the preferred FPP depends on which optimization criterion is used, such as the mean resequencing delay or the expected resequence buffer occupancy. It is shown that the selection rule for the preferred policy depends only on the ratio of the service rates. However, the optimal policy which minimizes the total delay (queueing delay plus resequencing delay) also depends on the threshold. Application examples of these optimization procedures are illustrated. © 1993 IEEE.