Informatics and Applications

2016, Volume 10, Issue 4, pp 57-67

DISPATCHING TO TWO PARALLEL NONOBSERVABLE QUEUES USING ONLY STATIC INFORMATION

  • M. G. Konovalov
  • R. V. Razumchik

Abstract

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 on multiple 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.

[+] References (24)

[+] About this article