3
$\begingroup$

Consider a single queue server system with Poisson arrival rate of jobs $\lambda$ and exponential service times with mean $1/\mu$. When $\lambda < \mu$ the system can be proven to be positive recurrent. One general methodology to prove that is using Foster-Lyapunov criterion for continuous time processes, with Lyapunov function simply being equal to the number of jobs in the queue. See section 6.9.2 of this book for more details. The particular example is simple enough to admit simpler solutions though.

Now consider that whenever the server and queue are empty, the server enters a maintenance state with exponential maintenance duration with mean $1/\mu_2$ and during that time no job is scheduled. Intuitively the system will still be positive recurrent, because no matter how many jobs will arrive during maintenance, the queue will empty eventually during regular service time. Can this intuition be expressed with the previous theorem and if not what other theorems could be used to prove the above?

While I realize the last problem admits an analytical solution I am not interested into that. I would like a methodology for a more general class of problems where e.g. there could be possibly multiple queues and multiple servers.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

In this situation the Foster-Lyapunov criterion still works. Let the state of the system be $n$ when there are $n>0$ customers in the system and the server is working, and $0$ when the server is under maintenance (regardless of the number of waiting customers). Then, $f(n)=n$ still proves positive recurrence, since you have negative drift outside $\{0\}$, and $\mathbb{E}_0f(X_1)<\infty$. See Theorems 2.6.4 (discrete time) and 7.3.4 (continuous time) of this book: http://www.ime.unicamp.br/~popov/book_lyapunov.pdf.

Let me stress, though, that there is no "easy" way to transfer this argument to multiple servers, because you need the negative drift for all states outside a finite set (and finite mean jump w.r.t. the Lyapunov function from that set). One needs to modify the Lyapunov function in some way (e.g., in such a that the drift towards the "origin" is large when at least one queue is large, this could be achieved by considering e.g. "quadratic" Lyapunov functions). Or use the Foster-Lyapunov criterion "in several steps", see Theorem 2.2.4 of [Fayolle, Malyshev, Menshikov, "Topics in the constructive theory of countable Markov chains"].

Improve this answer
$\endgroup$
6
  • $\begingroup$ The last theorem is what I was looking for but if I am not mistaken, is for discrete time only? Also your first argument is not valid because the set of states $s$ for which $V(s)$ < constant should be finite. Example 6.16 in the book of my question highlights why this is necessary. I can see nonetheless that including maintenance state in function would work. $\endgroup$
    – kon psych
    Commented Mar 21, 2017 at 0:06
  • $\begingroup$ Who is $V(\cdot)$? $\endgroup$
    – Serguei Popov
    Commented Mar 21, 2017 at 0:52
  • $\begingroup$ If $V$ is $f$, then it is finite (at least in one-dimensional case). $\endgroup$
    – Serguei Popov
    Commented Mar 21, 2017 at 0:58
  • $\begingroup$ For continuous time it's difficult to speak about "several steps". But if your transition rates are uniformly bounded, then you can switch to discrete time (the embedded chain)?.. $\endgroup$
    – Serguei Popov
    Commented Mar 21, 2017 at 1:00
  • $\begingroup$ Yes $V$ is $f$ in the book you sent (I am used to see Lyapunov function denoted by $V$). If we consider the states as a tuple of queue size and of a binary variable that indicates if server is maintained, then the set of states for which $f$ is 0 is infinite. $\endgroup$
    – kon psych
    Commented Mar 21, 2017 at 4:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .