Paper Info
Title
Improving routing decisions in parallel non-observable queues.
Abstract
We revisit the well-known problem of scheduling in \(N\ge 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.
Year
DOI
Venue
2018
10.1007/s00607-018-0598-5
Computing
Keywords
Field
DocType
Parallel queues,Non-observable,Partial information,Optimal routing,Mean waiting time,Mean response time,68M20,90B36
Mean sojourn time,Discretization,Mathematical optimization,Observable,Scheduling (computing),Queue,Server,Almost surely,Mathematics,Recursion
Journal
Volume
Issue
ISSN
100
10
0010-485X
Citations 
PageRank 
References 
0
0.34
22
Authors
2
Name
Order
Citations
PageRank
Mikhail Konovalov101.01
Rostislav Razumchik299.46