Dispatching to two parallel nonobservable queues using only static information

Consideration is given to the problem of dispatching independent jobs from one flow to two parallel single server queueing systems each with an infinite capacity queue. There is one dispatcher, which immediately makes decisions where to route newly incoming jobs. In order to make the decision, the dispatcher uses only static information about the system, i. e., servers' speeds, job interarrival time distribution, and job size distribution. The dynamic information (for example, current queue sizes) is unavailable for the dispatcher. For such nonobservable queues, it is known that minimum mean sojourn time is achieved when the dispatcher uses the deterministic (periodic) policy. Even when using this optimal policy, the dispatcher also observes jobs' arrival instants but this information is left unused. The question posed in this paper is the following: Is it possible to reduce the mean sojourn time if one, in addition to the static information, also uses the historical information about jobs' arrival instants? Using simulation techniques, the authors show that the answer to the question is positive. Such policy uses static information and the estimates of the queue sizes based onmultiple replications of the system's trajectory.compared to the optimal policy, the achievable gain varies from 1,5% to 10%, and increases with the decrease of job size variance. When the job size variance is low, the proposed policy is even better than the dynamic join-the-shortest queue policy.

Авторы
Konovalov M.G.1 , Razumchik R.V. 1, 2
Издательство
Федеральный исследовательский центр "Информатика и управление" РАН
Номер выпуска
4
Язык
Русский
Страницы
57-67
Статус
Опубликовано
Том
10
Год
2016
Организации
  • 1 Institute of Informatics Problems, Federal Research Center Computer Science and Control of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow, 119333, Russian Federation
  • 2 Peoples' Friendship University of Russia, 6 Miklukho-Maklaya Str., Moscow, 117198, Russian Federation
Ключевые слова
Dispatching; Nonobservable queues; Parallel service; Queueing system; Static information
Дата создания
19.10.2018
Дата изменения
19.10.2018
Постоянная ссылка
https://repository.rudn.ru/ru/records/article/record/4155/