Return to Question

Queueing Model:

Consider $n$ independent, parallel $M/M/1$ queues with identical arrival rate $\lambda$ and service rate $\mu$. For each $M/M/1$ queue, we use the FCFS (First Come First Served) discipline Original: and if there is some customer in service, no more customers can enter it.
Added: Each customer, for each $M/M/1$ queue, upon arrival, goes directly into service if the server is free and, if not, the customer joins the queue. When the server finishes serving a customer, the customer leaves the system, and the next customer in line, if there is any, enters service.

For each customer $c$, its start time, finish time, service interval are denoted by $c_{.st}$, $c_{.ft}$, and $[c_{.st}, c_{.ft}]$, respectively.

Problem:

I want to study some concurrency-related problems in such queueing system in the long run.

(1). Given two different $M/M/1$ queues $Q_i$ and $Q_j$ and a customer $c$ served by $Q_i$, what is the probability that it starts during the service interval of some customer $c'$ served by $Q_j$ (i.e., $c_{.st} \in [c'_{.st}, c'_{.ft}]$)?

Notice that $c'$ will be unique if $c_{.st} \in [c'_{.st}, c'_{.ft}]$ holds (see the figure below).

(2). Given a customer $c'$ served by $Q_j$, what is the probability that there are exactly $m$ customers each of which (denoted $c''$) finishes during the service interval of $c'$ (i.e., $c''_{.ft} \in [c'_{.st}, c'_{.ft}]$)?

Notice that there may be more than one customer in $Q_k$ ($Q_k \neq Q_j$) satisfying the condition $c''_{.ft} \in [c'_{.st}, c'_{.ft}]$ (see the figure below).

(3) Combine problems (1) and (2):
Given two different $M/M/1$ queues $Q_i$ and $Q_j$ and a customer $c$ served by $Q_i$, let $c'$ be the customer served by $Q_j$ satisfying $c_{.st} \in [c'_{.st}, c'_{.ft}]$ (i.e., $c$ starts during the service interval of $c'$).
The set of customers that finishes before $c$ starts is denoted by $c^{\prec} = \{c'': c''_{.ft} \le c_{.st} \}$.
What is the probability that there are exactly $k$ customers in $c^{\prec}$ each of which (denoted by $c''$) finishes during the service interval of $c'$ (i.e., $c''_{.ft} \in [c'_{.st}, c'_{.ft}]$)?

parallelmm1_threeproblems http://i1.tietuku.com/5eeddcb2557fb93c.png

In addition, are such concurrency-related problems are the typical ones studied in the literature on queueing theory? Any references related to similar problems are also well appreciated.

Queueing Model:

Consider $n$ independent, parallel $M/M/1$ queues with identical arrival rate $\lambda$ and service rate $\mu$. For each $M/M/1$ queue, we use the FCFS (First Come First Served) discipline and if there is some customer in service, no more customers can enter it.

For each customer $c$, its start time, finish time, service interval are denoted by $c_{.st}$, $c_{.ft}$, and $[c_{.st}, c_{.ft}]$, respectively.

Problem:

I want to study some concurrency-related problems in such queueing system in the long run.

(1). Given two different $M/M/1$ queues $Q_i$ and $Q_j$ and a customer $c$ served by $Q_i$, what is the probability that it starts during the service interval of some customer $c'$ served by $Q_j$ (i.e., $c_{.st} \in [c'_{.st}, c'_{.ft}]$)?

Notice that $c'$ will be unique if $c_{.st} \in [c'_{.st}, c'_{.ft}]$ holds (see the figure below).

(2). Given a customer $c'$ served by $Q_j$, what is the probability that there are exactly $m$ customers each of which (denoted $c''$) finishes during the service interval of $c'$ (i.e., $c''_{.ft} \in [c'_{.st}, c'_{.ft}]$)?

Notice that there may be more than one customer in $Q_k$ ($Q_k \neq Q_j$) satisfying the condition $c''_{.ft} \in [c'_{.st}, c'_{.ft}]$ (see the figure below).

(3) Combine problems (1) and (2):
Given two different $M/M/1$ queues $Q_i$ and $Q_j$ and a customer $c$ served by $Q_i$, let $c'$ be the customer served by $Q_j$ satisfying $c_{.st} \in [c'_{.st}, c'_{.ft}]$ (i.e., $c$ starts during the service interval of $c'$).
The set of customers that finishes before $c$ starts is denoted by $c^{\prec} = \{c'': c''_{.ft} \le c_{.st} \}$.
What is the probability that there are exactly $k$ customers in $c^{\prec}$ each of which (denoted by $c''$) finishes during the service interval of $c'$ (i.e., $c''_{.ft} \in [c'_{.st}, c'_{.ft}]$)?

parallelmm1_threeproblems http://i1.tietuku.com/5eeddcb2557fb93c.png

In addition, are such concurrency-related problems are the typical ones studied in the literature on queueing theory? Any references related to similar problems are also well appreciated.

Model:

Consider $n$ independent, parallel $M/M/1$ queues with identical arrival rates $\lambda$ and service rates $\mu$. For each $M/M/1$ queue, we use the FCFS (First Come First Served) discipline and if there is some customer in service, no more customers can enter it.

For each customer $c$, its start time, finish time, service interval are denoted by $c_{.st}$, $c_{.ft}$, and $[c_{.st}, c_{.ft}]$, respectively.

Problems:

I want to study some concurrency-related problems in such queueing system in the long run. Specifically,

(1). Given two different $M/M/1$ queues $Q_i$ and $Q_j$ and a customer $c$ served by $Q_i$, what is the probability that it starts during the service interval of customer $c'$ served by $Q_j$ (i.e., $c_{.st} \in [c'_{.st}, c'_{.ft}]$)?

Note that $c'$ will be unique if $c_{.st} \in [c'_{.st}, c'_{.ft}]$ holds, as shown in the following figure.

(2). On the other hand, given a customer $c$ served by $Q_i$, what is the probability that there are exactly $m$ customers each of which (denoted $c'$) finishes during the service interval of $c$ (i.e., $c'_{.ft} \in [c_{.st}, c_{.ft}]$)?

Note that there may be more than one customer in $Q_j$ ($Q_j \neq Q_i$) satisfying the condition $c'_{.ft} \in [c_{.st}, c_{.ft}]$, as shown in the following figure.

References related to similar problems are also well appreciated. Thanks in advance.

Queueing Model:

Consider $n$ independent, parallel $M/M/1$ queues with identical arrival rate $\lambda$ and service rate $\mu$. For each $M/M/1$ queue, we use the FCFS (First Come First Served) discipline Original: and if there is some customer in service, no more customers can enter it.
Added: Each customer, for each $M/M/1$ queue, upon arrival, goes directly into service if the server is free and, if not, the customer joins the queue. When the server finishes serving a customer, the customer leaves the system, and the next customer in line, if there is any, enters service.

For each customer $c$, its start time, finish time, service interval are denoted by $c_{.st}$, $c_{.ft}$, and $[c_{.st}, c_{.ft}]$, respectively.

Problem:

I want to study some concurrency-related problems in such queueing system in the long run.

(1). Given two different $M/M/1$ queues $Q_i$ and $Q_j$ and a customer $c$ served by $Q_i$, what is the probability that it starts during the service interval of some customer $c'$ served by $Q_j$ (i.e., $c_{.st} \in [c'_{.st}, c'_{.ft}]$)?

Notice that $c'$ will be unique if $c_{.st} \in [c'_{.st}, c'_{.ft}]$ holds (see the figure below).

(2). Given a customer $c'$ served by $Q_j$, what is the probability that there are exactly $m$ customers each of which (denoted $c''$) finishes during the service interval of $c'$ (i.e., $c''_{.ft} \in [c'_{.st}, c'_{.ft}]$)?

Notice that there may be more than one customer in $Q_k$ ($Q_k \neq Q_j$) satisfying the condition $c''_{.ft} \in [c'_{.st}, c'_{.ft}]$ (see the figure below).

(3) Combine problems (1) and (2):
Given two different $M/M/1$ queues $Q_i$ and $Q_j$ and a customer $c$ served by $Q_i$, let $c'$ be the customer served by $Q_j$ satisfying $c_{.st} \in [c'_{.st}, c'_{.ft}]$ (i.e., $c$ starts during the service interval of $c'$).
The set of customers that finishes before $c$ starts is denoted by $c^{\prec} = \{c'': c''_{.ft} \le c_{.st} \}$.
What is the probability that there are exactly $k$ customers in $c^{\prec}$ each of which (denoted by $c''$) finishes during the service interval of $c'$ (i.e., $c''_{.ft} \in [c'_{.st}, c'_{.ft}]$)?

parallelmm1_threeproblems http://i1.tietuku.com/5eeddcb2557fb93c.png

In addition, are such concurrency-related problems are the typical ones studied in the literature on queueing theory? Any references related to similar problems are also well appreciated.