Resequencing Delay for a Queueing System with Two Heterogeneous Servers Under a Threshold-Type Scheduling

Abstract

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. For a service center with two heterogeneous servers, the mean queueing delay is known to be minimized by a threshold-type scheduling policy. If FIFO delivery is required, out of sequence customers experience additional delay called the resequencing delay. It is shown that, under the threshold-type policy, the resequencing delay depends on the strategy by which customers are selected and dispatched to the servers. Two typical strategies of the selection policy are developed and the delay characteristics corresponding to the two strategies are studied. The existing methods for solving resequencing delay are extended to cover the threshold-type policy. Closed-form solutions for the resequencing delay distributions under both selection policies are derived. In order to characterize the performance of the system under the two different policies, two optimization criteria are introduced, namely, the fraction of customers that experience resequencing delay and the mean resequencing delay. These two 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. © 1988 IEEE