|
Digital
Library of the European Council for Modelling
and Simulation |
Title: |
Using Inter-Arrival Times For Scheduling In
Non-Observable Queues |
Authors: |
Mikhail
Konovalov, Rostislav Razumchik |
Published in: |
(2017).ECMS 2017 Proceedings
Edited by: Zita Zoltay Paprika, Péter Horák, Kata Váradi, Péter Tamás
Zwierczyk, Ágnes Vidovics-Dancs, János Péter Rádics European Council for Modeling and Simulation. doi:10.7148/2017 ISBN:
978-0-9932440-4-9/ ISBN:
978-0-9932440-5-6 (CD) 31st European Conference on Modelling and
Simulation, Budapest, Hungary, May 23rd
– May 26th, 2017 |
Citation
format: |
Mikhail
Konovalov, Rostislav Razumchik (2017). Using Inter-Arrival Times For
Scheduling In Non-Observable Queues, ECMS 2017 Proceedings Edited by: Zita
Zoltay Paprika, Péter Horák, Kata Váradi, Péter Tamás Zwierczyk, Ágnes
Vidovics-Dancs, János Péter Rádics European Council for Modeling and
Simulation. doi: 10.7148/2017-0667 |
DOI: |
https://doi.org/10.7148/2017-0667 |
Abstract: |
In
online dispatching systems, when there is no opportunity to observe the state
of the systems’ components, one may implement “blind” scheduling policies
i.e. those which use incomplete/indirect observations of the system state or
do not use any information at all. Here we deal with the well-known problem
of scheduling in several non-observable parallel single server queues with
single Poisson incoming flow, when the broker (scheduler) does not observe
neither the current states of the queues and servers, nor the size of the
incoming jobs. The only available information is the job size distribution,
server’s speeds and job’s inter-arrival time distribution. For this problem
setting it is known that if the scheduler can memorize the sequence of its
previous decisions, then a deterministic policy is much better than the
probabilistic policy (with respect to the job’s mean waiting and mean sojourn
time). But if the broker can memorize its decision, it is also very natural
to assume that it can also memorize the time instants at which these
decisions are made. In this paper we address the following question: can the
deterministic policy be improved if the broker, in addition to decisions
made, utilizes also the information about the lengths of time between the
decisions? We give numerical evidence that it is indeed possible; the cases
presented include three, five and nine parallel jMj1 queues. We describe the
simple new policy according to which, the broker’s decisions are based on the
estimates of the queue sizes. In most of the numerical experiments, the new
policy outperformed the deterministic policy The relative gain may reach 10%
in the case of the job’s mean sojourn time and 50% in the case of the job’s
mean waiting time. |
Full
text: |