Improving routing decisions in parallel non-observable queues

We revisit the well-known problem of scheduling in N≥ 2 non-observable parallel single-server queues with one dispatcher having no queue to store the incoming jobs. The dispatcher does not observe the current states of the queues and servers and the sizes of the incoming jobs. The only available information to it is the job size distribution, job’s inter-arrival time distribution and server’s speeds. For this problem setting it is known that if the dispatcher can memorize the sequence of its previous decisions, then a deterministic policy is better than the random choice policy with respect to the job’s mean waiting and mean sojourn time. In this paper we address the following question: can the deterministic policy be improved if the dispatcher, in addition to the decisions made, can memorize also the times between the decisions? We describe the new policy and numerically show that it is almost always possible to do better with it than with the deterministic policy. Two algorithms for choosing decisions under the new policy are given. Both are based on the Lindley recursion and are approximate in nature, because utilize the discretization of the underlying distributions. Our findings show that the relative gain of the new policy may reach 10 % , when minimizing job’s mean sojourn time, and more than 50 % for the job’s mean waiting time. © 2018, Springer-Verlag GmbH Austria, part of Springer Nature.

Authors
Journal
Publisher
Springer-Verlag Wien
Number of issue
10
Language
English
Pages
1059-1079
Status
Published
Volume
100
Year
2018
Organizations
  • 1 Institute of Informatics Problems of the FRC CSC RAS, 44k2 Vavilova Street, Moscow, 119333, Russian Federation
  • 2 Peoples’ Friendship University of Russia (RUDN University), 6 Miklukho-Maklaya St, Moscow, 117198, Russian Federation
Keywords
Mean response time; Mean waiting time; Non-observable; Optimal routing; Parallel queues; Partial information
Date of creation
19.10.2018
Date of change
19.10.2018
Short link
https://repository.rudn.ru/en/records/article/record/6406/