Round-Robin routing policy: Value functions and mean performance with job -and server-specific costs

Esa Hyytiä*, Samuli Aalto

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

5 Citations (Scopus)

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 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 time in an M/G/m-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.

Original languageEnglish
Title of host publicationVALUETOOLS 2013 - 7th International Conference on Performance Evaluation Methodologies and Tools
EditorsVittorio Cortellessa, Peter Buchholz, Mark Squillante, Andras Horvath, Luca Muscariello
PublisherInstitute for Color Science and Technology (ICST)
Pages69-78
Number of pages10
ISBN (Electronic)9781936968480
DOIs
Publication statusPublished - 2013
Event7th International Conference on Performance Evaluation Methodologies and Tools, VALUETOOLS 2013 - Torino, Italy
Duration: 10 Dec 201312 Dec 2013

Publication series

NameVALUETOOLS 2013 - 7th International Conference on Performance Evaluation Methodologies and Tools

Conference

Conference7th International Conference on Performance Evaluation Methodologies and Tools, VALUETOOLS 2013
Country/TerritoryItaly
CityTorino
Period10/12/1312/12/13

Bibliographical note

Publisher Copyright:
Copyright © 2013 ICST.

Other keywords

  • Dispatching
  • Erl/G/1 queue
  • M/G/m-RR
  • MDP
  • Parallel queues
  • Round-Robin
  • Task assignment

Fingerprint

Dive into the research topics of 'Round-Robin routing policy: Value functions and mean performance with job -and server-specific costs'. Together they form a unique fingerprint.

Cite this