Throughput maximization for two station tandem systems: A proof of the Andradóttir-Ayhan conjecture

John J. Hasenbein; Bara Kim

doi:10.1007/s11134-011-9222-5

Throughput maximization for two station tandem systems: A proof of the Andradóttir-Ayhan conjecture

John J. Hasenbein, Bara Kim

Research output: Contribution to journal › Article › peer-review

9 Citations (Scopus)

Abstract

We study a tandem queueing network with two stations, M heterogeneous flexible servers, and a finite intermediate buffer. The objective is to dynamically assign the servers to the stations in order to maximize the throughput of the system. The form of the optimal policy for M≤3 was derived in two previous papers. In one of those papers, Andradóttir and Ayhan (Operations Research 53:516-531, 2005) provide a conjecture on the form of the optimal policy for M≥4. We prove their conjecture in this paper, showing that the optimal policy is defined by monotone thresholds and the ratios of the service rates among the servers. For M>1, we also prove that the optimal policy always uses the entire intermediate buffer.

Original language	English
Pages (from-to)	365-386
Number of pages	22
Journal	Queueing Systems
Volume	67
Issue number	4
DOIs	https://doi.org/10.1007/s11134-011-9222-5
Publication status	Published - 2011 Apr

Bibliographical note

Funding Information:
Acknowledgements We would like to thank Hayriye Ayhan and Doug Down for useful discussions during the course of this research. John Hasenbein was partially supported by NSF grant 26-1130-32. Bara Kim was supported by LG Yonam Culture Foundation.

Keywords

Flexible servers
Markov decision processes
Tandem queueing networks
Throughput optimality

ASJC Scopus subject areas

Statistics and Probability
Computer Science Applications
Management Science and Operations Research
Computational Theory and Mathematics

Access to Document

10.1007/s11134-011-9222-5

Cite this

@article{6b632c16ecaa4a928970fc57ceaa1d2f,

title = "Throughput maximization for two station tandem systems: A proof of the Andrad{\'o}ttir-Ayhan conjecture",

abstract = "We study a tandem queueing network with two stations, M heterogeneous flexible servers, and a finite intermediate buffer. The objective is to dynamically assign the servers to the stations in order to maximize the throughput of the system. The form of the optimal policy for M≤3 was derived in two previous papers. In one of those papers, Andrad{\'o}ttir and Ayhan (Operations Research 53:516-531, 2005) provide a conjecture on the form of the optimal policy for M≥4. We prove their conjecture in this paper, showing that the optimal policy is defined by monotone thresholds and the ratios of the service rates among the servers. For M>1, we also prove that the optimal policy always uses the entire intermediate buffer.",

keywords = "Flexible servers, Markov decision processes, Tandem queueing networks, Throughput optimality",

author = "Hasenbein, {John J.} and Bara Kim",

note = "Funding Information: Acknowledgements We would like to thank Hayriye Ayhan and Doug Down for useful discussions during the course of this research. John Hasenbein was partially supported by NSF grant 26-1130-32. Bara Kim was supported by LG Yonam Culture Foundation.",

year = "2011",

month = apr,

doi = "10.1007/s11134-011-9222-5",

language = "English",

volume = "67",

pages = "365--386",

journal = "Queueing Systems",

issn = "0257-0130",

publisher = "Springer Netherlands",

number = "4",

}

TY - JOUR

T1 - Throughput maximization for two station tandem systems

T2 - A proof of the Andradóttir-Ayhan conjecture

AU - Hasenbein, John J.

AU - Kim, Bara

N1 - Funding Information: Acknowledgements We would like to thank Hayriye Ayhan and Doug Down for useful discussions during the course of this research. John Hasenbein was partially supported by NSF grant 26-1130-32. Bara Kim was supported by LG Yonam Culture Foundation.

PY - 2011/4

Y1 - 2011/4

N2 - We study a tandem queueing network with two stations, M heterogeneous flexible servers, and a finite intermediate buffer. The objective is to dynamically assign the servers to the stations in order to maximize the throughput of the system. The form of the optimal policy for M≤3 was derived in two previous papers. In one of those papers, Andradóttir and Ayhan (Operations Research 53:516-531, 2005) provide a conjecture on the form of the optimal policy for M≥4. We prove their conjecture in this paper, showing that the optimal policy is defined by monotone thresholds and the ratios of the service rates among the servers. For M>1, we also prove that the optimal policy always uses the entire intermediate buffer.

AB - We study a tandem queueing network with two stations, M heterogeneous flexible servers, and a finite intermediate buffer. The objective is to dynamically assign the servers to the stations in order to maximize the throughput of the system. The form of the optimal policy for M≤3 was derived in two previous papers. In one of those papers, Andradóttir and Ayhan (Operations Research 53:516-531, 2005) provide a conjecture on the form of the optimal policy for M≥4. We prove their conjecture in this paper, showing that the optimal policy is defined by monotone thresholds and the ratios of the service rates among the servers. For M>1, we also prove that the optimal policy always uses the entire intermediate buffer.

KW - Flexible servers

KW - Markov decision processes

KW - Tandem queueing networks

KW - Throughput optimality

UR - http://www.scopus.com/inward/record.url?scp=79956217067&partnerID=8YFLogxK

U2 - 10.1007/s11134-011-9222-5

DO - 10.1007/s11134-011-9222-5

M3 - Article

AN - SCOPUS:79956217067

SN - 0257-0130

VL - 67

SP - 365

EP - 386

JO - Queueing Systems

JF - Queueing Systems

IS - 4

ER -

Throughput maximization for two station tandem systems: A proof of the Andradóttir-Ayhan conjecture

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this