2015-12-01
Routing policies for a partially observable two-server queueing system
Publication
Publication
Presented at the
International Conference on Performance Evaluation Methodologies and Tools, Berlin
We consider a queueing system controlled by decisions based
on partial state information. The motivation for this work
stems from road traffic, in which drivers may, or may not, be
subscribed to a smartphone application for dynamic route
planning.
Our model consists of two queues with independent exponential service times, serving two types of jobs. Arrivals
occur according to a Poisson process; a fraction alpha of the
jobs (type X) is observable and controllable. At all times
the number of X jobs in each queue and their individual positions are known. Upon its arrival a router decides which
queue the next X job should join. Y jobs (fraction p_Y) are
non-observable and non-controllable. They randomly join a
queue according to some static routing probability.
We address the following main research questions: 1) what
penetration level alpha is needed for effective control, 2) which
policy should be implemented at the router, and 3) what
is the added value of having more system information (e.g.,
average service times)? An extensive simulation study reveals that for heavily loaded systems a low penetration level
suffices and that the performance (in terms of the average
sojourn time) of a simple policy that relies on little system
information is close to w-JSQ (weighted join-the-shortest-
queue policy) which is optimal in a fully controllable and
observable system. The latter result is confirmed by the
analysis of deterministic fluid models that approximate the
stochastic evolution under large loads.
Additional Metadata | |
---|---|
, , , | |
, , | |
, | |
A. Busic , M. Gribaudo , P. Reinecke | |
International Conference on Performance Evaluation Methodologies and Tools | |
Organisation | Stochastics |
Ellens, W., Kovacs, P., van den Berg, H., & Núñez Queija, R. (2015). Routing policies for a partially observable two-server queueing system. In A. Busic, M. Gribaudo, & P. Reinecke (Eds.), . |