E. Hyytiä and S. Aalto, On Round-Robin Routing Policy with FCFS and LCFS Scheduling, Performance Evaluation, vol. 97, pp. 83-103, 2016.
Abstract: We study the Round-Robin (RR) routing to a system of parallel queues, which serve jobs according to FCFS or LCFS scheduling disciplines. The cost structure comprises two components: a service fee and a queueing delay related component. With Poisson arrivals, the inter-arrival time to each queue obeys the Erlang distribution. This allows us to study the mean and transient behavior of the queues separately. The service fee is independent of the scheduling and queueing, and we obtain the corresponding mean cost rate and value function in closed forms. With respect to queueing delay, we first derive integral expressions enabling efficient computation of the corresponding size-aware value functions. By decomposition, these yield also the value function for the whole system of m parallel queues fed by RR. Given the value function, one can carry out the first policy iteration step with arbitrary holding cost rates (e.g., delay, slowdown etc.) yielding efficient size-, cost- and state-aware policies. Moreover, the mean waiting and sojourn times in the corresponding systems get resolved at the same time This includes also the M/G/m-RR system. The results are demonstrated in the numerical examples, where we compute near optimal job routing policies for sample systems.
Links:
BibTeX entry:
@article{hyytia-peva-2016,
author = {Esa Hyyti{\"a} and Samuli Aalto},
title = {On Round-Robin Routing Policy with {FCFS} and {LCFS} Scheduling},
journal = {Performance Evaluation},
year = {2016},
month = {Mar.},
volume = {97},
pages = {83--103},
doiopt = {10.1016/j.peva.2016.01.002},
}