# Approximation of excessive backlog probabilities of two parallel queues

2018-07-25
Ünlü, Kamil Demirberk
Sezer, Ali Devin
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).
International Conference on Queueing Theory and Network Applications QTNA2018, (25 - 27 Temmuz 2018)

# Suggestions

 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
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.