Routing policies for a partially observable two-server queueing system

Wendy Ellens, Péter Kovács, Rudesindo Núñez-Queija, Hans Leo van den Berg

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    57 Downloads (Pure)

    Abstract

    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 ex-ponential service times, serving two types of jobs. Arrivals occur according to a Poisson process; a fraction of the jobs (type X) is observable and controllable. At all times the number of X jobs in each queue and their individual po-sitions are known. Upon its arrival a router decides which queue the next X job should join. Y jobs 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 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 re-veals that for heavily loaded systems a low penetration level suucces 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 uid models that approximate the stochastic evolution under large loads.
    Original languageUndefined
    Title of host publicationProceedings of the 9th EAI International Conference on Performance Evaluation Methodologies and Tools (VALUETOOLS 2015)
    Place of PublicationNew York
    PublisherAssociation for Computing Machinery (ACM)
    Pages111-118
    Number of pages8
    ISBN (Print)978-1-63190-096-9
    DOIs
    Publication statusPublished - Dec 2015
    Event9th EAI International Conference on Performance Evaluation Methodologies and Tools 2015 - Berlin, Germany
    Duration: 14 Dec 201516 Dec 2015
    Conference number: 9
    http://archive.valuetools.org/2015/show/home

    Publication series

    Name
    PublisherACM

    Conference

    Conference9th EAI International Conference on Performance Evaluation Methodologies and Tools 2015
    Abbreviated titleVALUETOOLS 2015
    CountryGermany
    CityBerlin
    Period14/12/1516/12/15
    Internet address

    Keywords

    • EWI-26917
    • IR-100229
    • METIS-316873

    Cite this

    Ellens, W., Kovács, P., Núñez-Queija, R., & van den Berg, H. L. (2015). Routing policies for a partially observable two-server queueing system. In Proceedings of the 9th EAI International Conference on Performance Evaluation Methodologies and Tools (VALUETOOLS 2015) (pp. 111-118). New York: Association for Computing Machinery (ACM). https://doi.org/10.4108/eai.14-12-2015.2262697