On Round-Robin routing with FCFS and LCFS scheduling

Esa Hyytiä*, Samuli Aalto

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

10 Citations (Scopus)
130 Downloads (Pure)


We study the Round-Robin (RR) routing to a system of parallel queues, which serve jobs according to FCFS or preemptive 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. The results are demonstrated in the numerical examples, where we compute near optimal job routing policies for sample systems.

Original languageEnglish
Pages (from-to)83-103
Number of pages21
JournalPerformance Evaluation
Publication statusPublished - Mar 2016
MoE publication typeA1 Journal article-refereed


  • Erl/G/1-queue
  • FCFS
  • LCFS
  • M/G/m-RR-system
  • Round-Robin
  • Task assignment


Dive into the research topics of 'On Round-Robin routing with FCFS and LCFS scheduling'. Together they form a unique fingerprint.

Cite this