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.

Авторы
Журнал
Издательство
Springer-Verlag Wien
Номер выпуска
10
Язык
Английский
Страницы
1059-1079
Статус
Опубликовано
Том
100
Год
2018
Организации
  • 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
Ключевые слова
Mean response time; Mean waiting time; Non-observable; Optimal routing; Parallel queues; Partial information
Дата создания
19.10.2018
Дата изменения
19.10.2018
Постоянная ссылка
https://repository.rudn.ru/ru/records/article/record/6406/