home/Publications/HA13

E. Hyytiä and S. Aalto, Round-Robin Routing Policy: Value Functions and Mean Performance with Job- and Server-specific Costs, in 7th International Conference on Performance Evaluation Methodologies and Tools (ValueTools), 2013, Torino, Italy.

Abstract: We study the round-robin (RR) routing to a system of parallel queues. The cost structure comprises two components: a service fee and a queueing delay related component, where both can be job- and queue-specific random variables. With Poisson arrivals, the inter-arrival time to each queue obeys Erlang's distribution. This allows us to study the mean and transient behavior of the queues separately. The service fee is independent of the 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 value function. By decomposition, these yield also the value function for the whole system of k 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 time in an M/G/k-RR system gets resolved at the same time. The results are demonstrated in the numerical examples, where we compute near optimal task assignment policies for a sample system with two servers.

Links: (pdf)

BibTeX entry:

@inproceedings{hyytia-valuetools-2013,
  author = {Esa Hyyti{\"a} and Samuli Aalto},
  title = {Round-Robin Routing Policy: Value Functions and Mean Performance with Job- and Server-specific Costs},
  booktitle = {7th International Conference on Performance Evaluation Methodologies and Tools (ValueTools)},
  address = {Torino, Italy},
  month = {Dec.},
  year = {2013},
}