Resequencing delay for a queueing system with two heterogeneous servers under a threshold-type scheduling

In service centers with multiple-parallel servers, jobs may complete their service in a different order from the one in which they enter the center. In order to reestablish the original order, resequencing protocols need to be implemented. It is shown that under a threshold-type policy, the resequencing delay depends on the strategy by which customers are selected and dispatched to the servers. Two selection strategies are developed, and the delay characteristics corresponding to the two strategies are studied. Existing methods for finding the sequencing delay are extended to cover the threshold-type policy. Closed-form solutions for the resequencing delay distributions under both selection policies are derived. To characterize the performance of the system under the two policies, two optimization criteria are introduced, namely, the fraction of customers that experience resequencing delay and the mean resequencing delay. These quantities are calculated explicitly, and their comparison reveals that the optimal decision is independent of the load on the system. The selection of the optimal policy under the first criterion depends only on the service rates, whereas for the second criterion the optimal selection depends on the threshold value and the ratio of the service rates