Show/Hide Menu
Hide/Show Apps
Logout
Türkçe
Türkçe
Search
Search
Login
Login
OpenMETU
OpenMETU
About
About
Open Science Policy
Open Science Policy
Communities & Collections
Communities & Collections
Help
Help
Frequently Asked Questions
Frequently Asked Questions
Guides
Guides
Thesis submission
Thesis submission
MS without thesis term project submission
MS without thesis term project submission
Publication submission with DOI
Publication submission with DOI
Publication submission
Publication submission
Supporting Information
Supporting Information
General Information
General Information
Copyright, Embargo and License
Copyright, Embargo and License
Contact us
Contact us
Approximation of excessive backlog probabilities of two parallel queues
Date
2018-07-25
Author
Ünlü, Kamil Demirberk
Sezer, Ali Devin
Metadata
Show full item record
Item Usage Stats
165
views
0
downloads
Cite This
Let X be the constrained random walk on Z 2 + with increments (1, 0), (−1, 0), (0, 1) and (0, −1) representing the lengths at service completion times of two queues with exponentially distributed interarrival and service times running in parallel. Denote the arrival and service rates by λ i , µ i , i = 1, 2; we assume λ i < µ i , i = 1, 2, i.e., X is assumed stable. Without loss of generality we assume ρ 1 ≥ ρ 2. Let τ n be the first time X hits the line ∂A n = {x ∈ Z 2 : x(1)+x(2) = n}, i.e., when the sum of the components of X equals n for the first time. Let Y be the same random walk as X but only constrained on {y ∈ Z 2 : y(2) = 0} and its jump probabilities for the first component reversed. Let ∂B = {y ∈ Z 2 : y(1) = y(2)} and let τ be the first time Y hits ∂B. The probability p n = P x (τ n < τ 0) is a key performance measure of the queueing system represented by X (suppose the queues share a common buffer, then p n is the probability that this overflows overflows during the systems first busy cycle). We show that, for x n = ⌊nx⌋, x ∈ R 2 + , x(1) + x(2) ≤ 1, x(1) > 0, P (n−xn(1),xn(2)) (τ < ∞) approximates P xn (τ n < τ 0) with exponentially vanishing relative error. Let r = (λ 1 + λ 2)/(µ 1 + µ 2); for r 2 < ρ 2 and ρ 1 = ρ 2 , we construct a class of harmonic functions for Y with which the probability P y (τ < ∞) can be approximated with bounded relative error. For r 2 = ρ 1 ρ 2 , we obtain the exact formula P y (τ < ∞) = r y(1)−y(2) + r(1−r) r−ρ2 ρ y(1) 1 − r y(1)−y(2) ρ y(2) 1. The Y-harmonic functions are constructed from single points and pairs of conjugate points on a characteristic surface associated with X. The results are obtained using the approach of (Sezer, Exit Probabilities and Balayage of Constrained Random Walks, 2015).
URI
https://hdl.handle.net/11511/75269
Conference Name
International Conference on Queueing Theory and Network Applications QTNA2018, (25 - 27 Temmuz 2018)
Collections
Graduate School of Applied Mathematics, Conference / Seminar
Suggestions
OpenMETU
Core
APPROXIMATION OF EXCESSIVE BACKLOG PROBABILITIES OF TWO TANDEM QUEUES
Sezer, Ali Devin (2018-09-01)
Let X be the constrained random walk on Z(+)(2) having increments (1, 0), (-1, 1), and (0, -1) with respective probabilities A lambda,mu 1, and mu 2 representing the lengths of two tandem queues. We assume that X is stable and mu 1 not equal mu 2. Let tau(n) be the first time when the sum of the components of X equals n. Let Y be the constrained random walk on Z x Z(+) having increments (-1, 0), (1, 1), and (0, -1) with probabilities lambda, mu(1), and mu(2). Let tau be the first time that the components of...
Exit probabilities of markov modulated constrained random walks
Başoğlu Kabran, Fatma; Sezer, Ali Devin; Department of Financial Mathematics (2018)
Let X be the constrained random walk on Z2+ with increments (0, 0), (1, 0), (−1, 1), (0, −1) whose jump probabilities are determined by the state of a finite state Markov chain M. X represents the lengths of two queues of customers (or packets, tasks, etc.) waiting for service from two servers working in tandem; the arrival of customers occur with rate λ(Mk), service takes place at rates μ1(Mk), and μ2(Mk) where Mk denotes the current state of the Markov chain M. We assume that the average arrival rate is l...
Approximation of the exit probability of a stable Markov modulated constrained random walk
Kabran, Fatma Basoglu; Sezer, Ali Devin (2020-06-01)
Let X be the constrained randomwalk on Z(+)(2) having increments (1, 0), (- 1, 1), (0,- 1) with jump probabilities lambda(M-k), mu(1)(M-k), and mu(2)(M-k) where M is an irreducible aperiodic finite state Markov chain. The process X represents the lengths of two tandem queues with arrival rate lambda(M-k), and service rates mu(1)(M-k), and mu(2)(M-k); the process M represents the random environment within which the system operates. We assume that the average arrival rate with respect to the stationary measur...
Using genetic algorithms for single-machine bicriteria scheduling problems
Köksalan, Mustafa Murat; Keha, AB (2003-03-16)
We consider two bicriteria scheduling problems on a single machine: minimizing flowtime and number of tardy jobs, and minimizing flowtime and maximum earliness. Both problems are known to be NP-hard. For the first problem, we developed a heuristic that produces an approximately efficient solution (AES) for each possible value the number of tardy jobs can take over the set of efficient solutions. We developed a genetic algorithm (GA) that further improves the AESs. We then adapted the GA for the second probl...
Optimization of nonuniform array geometry for DOA estimation with the constraint on gross error probability
Birinci, Toygar; Tanık, Yalçın (2007-10-01)
In this work, a novel method is proposed to optimize the array geometry for DOA estimation. The method is based on minimization of fine error variances with the constraint that the gross error probability is below a certain threshold. For this purpose, a metric function that reflects the gross and fine error characteristics of the array is proposed. Theoretical analyses show that the minimization of this metric function leads to small DOA estimation error variance and small gross error probability. Analyses...
Citation Formats
IEEE
ACM
APA
CHICAGO
MLA
BibTeX
K. D. Ünlü and A. D. Sezer, “Approximation of excessive backlog probabilities of two parallel queues,” presented at the International Conference on Queueing Theory and Network Applications QTNA2018, (25 - 27 Temmuz 2018), Tsukuba, Japan, 2018, Accessed: 00, 2021. [Online]. Available: https://hdl.handle.net/11511/75269.