佇列系統期末整理

目錄

• 佇列系統期末整理
  • Birth-Death Process(BDP)
    • time-homogeneous BDP
  • Definition of Queueing system
    • Work-conserving property
    • Customer loss probability
    • Waiting time distribution
    • Little's law(formula)
    • Poisson Arrivals See time Average(PASTA)
  • M/M/1 queue
    • state transition probability
    • global balance equation
    • 迭代法解
    • 透過 generating function 解
    • long-term system
    • waiting time distribution
    • system time distribution
    • System time, waiting time, service time 的關係
  • M/M/c queue
    • state transition probability
    • global balance equation
    • L, Lq, W(T), Wq(Tq)
  • Finite-Source Queue

Birth-Death Process(BDP)

• 在 CTMC 的基礎上定義出來的一種 process

• 基礎定義：

  1. $P_j(t)=P(X(t)=j),t\ge 0,j\ge 0,X(0)=r,r\ge 0$，其中
     $X(0)=r$ 代表 initial state 在
     $r$。
  2. $P_r(0)=P(X(0)=r)=1$ (initial state probability)
  3. $P_{i,k}(s,t)=P(X(t)=k|P(s)=i),0\le s\le t<\mathrm{\infty }$ (同前面 DTMC 和 CTMC 定義)
  4. $P_{i,k}(t)=P_{i,k}(0,t)=P(X(t)=k|P(0)=i)$ (time homogeneous)

• 討論間隔時間為極短時 (

  $h\to 0^{+}$，可假設只會發生一種事件)：
  1. if
     $|k-i|\ge 2,P_{i,k}(t,t+h)=o(h)$，也就是發生改變兩個狀態值的機率極低。
  2. if
     $|k-i|\le 1,P_{i,k}(t,t+h)=$
     
     $$\{\begin{array}{l}[a_i(t)+\kappa (t)]\ast h+o(h),k=i+1,i\ge 0\\ 1-[a_i(t)+b_i(t)+\kappa (t)]\ast h+o(h),k=i,i>0\\ 1-[a_0(t)+\kappa (t)]\ast h+o(h),k=i=0\\ [b_i(t)]\ast h+o(h),k=i-1,i\ge 1\end{array}$$
     • $a(t)$ 代表 birth rate
     • $b(t)$ 代表 death rate
     • $\kappa (t)$ 代表 immigration rate (immegrate in)，底下的部分假設這個數值為
       $0$。

time-homogeneous BDP

• $a_i(t)\equiv a_i,b_i(t)\equiv b_i$

• transitional functions:
  

  $$\{\begin{array}{l}{P}_{i,0}^{\prime }(t)=-a_0{P}_{i,0}(t)+b_1{P}_{i,1}(t)\\ P_{i,k}^{\prime }(t)=-(a_k+b_k)P_{i,k}(t)+a_{k-1}{P}_{i,k-1}(t)+b_{k+1}{P}_{i,k+1}(t),k>1\end{array}$$

• sojourn time(waiting time

  $d_k$ for change of state from state
  $k$) is exponentially distributed,
  $d_k=a_k+b_k$
  • 並且這個數值與到達 state
    $k$ 前的路徑無關
  • 在 state
    $k$ 時，前往
    $k+1$ 的機率
    $p_k=\frac{a_k}{d_k}$，前往
    $k-1$ 的機率
    $q_k=\frac{b_k}{d_k}$
    • 對於 state
      $0$ 來說，一開始的
      $p_0=1$；再次抵達 state
      $0$ 後，
      $q_0=1$，也就是不再離開 state
      $0$。

• If

  $p_0=1,0<p_k<1,k\ge 1$
  1. $P_k(t)$ 滿足下列 ODE:
     
     $$\{\begin{array}{l}{P}_0^{\prime }(t)=-a_0{P}_0(t)+b_1{P}_1(t)\\ P_{i,k}^{\prime }(t)=-(a_k+b_k)P_k(t)+a_{k-1}{P}_{k-1}(t)+b_{k+1}{P}_{k+1}(t)\end{array}$$
  2. 對於所有
     $k\ge 0$，極限
     $\underset{t\to \mathrm{\infty }}{lim}{P}_k(t)={\pi }_k$ 存在，而且與 initial distribution 無關。(limiting distribution)
     • 如果
       $\underset{k=0}{\overset{\mathrm{\infty }}{lim}}{\rho }_k<\mathrm{\infty }$，其中
       ${\rho }_0=1,{\rho }_k=\frac{a_0{a}_1\cdots a_{k-1}}{b_1{b}_2\cdots b_k},k\ge 1$，那
       ${\pi }_k>0,k\ge 0$ 而且符合下式
       
       $$\{\begin{array}{l}{\pi }_0=[\sum _{j=0}^{\mathrm{\infty }}{\rho }_j{]}^{-1}\\ {\pi }_k={\rho }_k{\pi }_0\end{array}$$
     • 如果
       $\underset{k=0}{\overset{\mathrm{\infty }}{lim}}{\rho }_k=\mathrm{\infty }$，那
       ${\pi }_k=0,k\ge 0$。 (limiting distribution 不存在)

• balance equation

  • local balance equation(只討論單邊的鄰居)
    
    $$\{\begin{array}{l}-a_k{P}_k+b_{k+1}{P}_{k+1}=0\\ -b_k{P}_k+a_{k-1}{P}_{k-1}=0\end{array}$$
  • global balance equation(所有鄰居都要討論)
    
    $-(a_k+b_k)P_k+a_{k-1}{P}_{k-1}+b_{k+1}{P}_{k+1}=0$

Definition of Queueing system

• Notation

  • $(A/B/c/d/e/x)$

• Arrival process(

  $A$)
  • 使用 intearrival time 的 distribution 描述，並且假設各段 interarrival time 互相獨立。
  • 可能受到顧客數量影響

• Service process(

  $B$)
  • 用來描述 server 服務 customer 的 process
  • 在基礎的 queueing model 內假設是 i.i.d random variables
  • 可能受到顧客數量影響

• 對於 arrival process 和 service process 可能有以下幾種參數：

  • $M$: Memoryless，也就是 exponential distribution
  • $E_r$: order-r Erlang distribution
  • $H_r$: order-r hyperexponential distribution
  • $D$: deterministic (固定不變的常數)
  • $G$ or
    $GI$: 某個 i.i.d 的 distribution

• System structure

  • $c$: server 的數量有幾個
  • $d$: System capacity，也就是整個 queueing system 可以容納多少顧客(包含 queue size 和 server count)。(default value:
    $\mathrm{\infty }$)
    • 如果
      $c=d$，代表這個 queueing system 內沒有任何 waiting room(buffer)。
    • 如果
      $c<d$，顧客從開始進入 queueing system 到開始被服務的時間稱為 waiting time。
  • $e$: 顧客的總數量 (default value:
    $\mathrm{\infty }$)

• Service displine(

  $x$)
  • server 是如何服務 customer 的，預設是 FIFO(FCFS)。

Work-conserving property

• 如果顧客進入 queueing system 時有空閒的 server，這個顧客會立即被服務。

Customer loss probability

• $q=\underset{n\to \mathrm{\infty }}{lim}\frac{m_n}{n}$，
  $m_n$ 代表這
  $n$ 個顧客中沒成功進入 system 的顧客數量。

Waiting time distribution

• $F(x)$: waiting time distribution 的 CDF
  
  $$\{\begin{array}{l}F(x)=\underset{n\to \mathrm{\infty }}{lim}{F}_n(x),\mathrm{\forall }x>0\\ F_n(x)=\frac{1}{n}\sum _{n=1}^n{\mathcal{J}}_{w_i\le x},x>0\end{array}$$
  其中
  $w_i$ 是第
  $i$ 位顧客的 waiting time。

• Mean waiting time

  • $W^{(1)}=\underset{n\to \mathrm{\infty }}{lim}\frac{1}{n}(W_1+\cdots +W_n)$，此時的
    $W^{(1)}$ 就是 mean waiting time。
    • $W^{(k)}=\underset{n\to \mathrm{\infty }}{lim}\frac{1}{n}(W_1^k+\cdots +W_n^k)$，這個算法是計算更高維度的 mean waiting time。

• Busy period

  • $[a_n,b_n),a_n<b_n<a_{n+1},n\ge 1$
    • idle period:
      $[b_n,a_n+1)$
  • 這寫法代表 第
    $n$ 次的 busy period

• Queue Length distribution

  • $L(t),t\ge 0$: 在時間
    $t$ 時 system 內的顧客數量。
  • ${\overline{L}}_k(t)$: 在時間
    $(0,t)$ 內，有
    $k$ 個顧客的時間比例。
    • $p_k=\underset{t\to \mathrm{\infty }}{lim}{\overline{L}}_k(t),k\ge 0$

Little's law(formula)

• 系統中平均顧客數 = arrival rate * 平均顧客在系統內的時間

  • $L=\lambda \ast T$

• 這個算法與以下條件無關：

  • 系統的定義
  • Arrival(Service) time distribution
  • Server 數量
  • Waiting room(buffer) 大小
  • Service discipline

• 其他變種
  • 只針對 Queue 來看
    
  • 只針對 Server 來看
    

Poisson Arrivals See time Average(PASTA)

• 在穩定態時，在 state
  $k(k>0)$ 的機率相等於在一個 customer arrives 時看到 system 在 state
  $k$ 的機率。
  • 用數學式來表示為
    $\underset{t\to \mathrm{\infty }}{lim}P(L(t)=k)=\underset{t\to \mathrm{\infty }}{lim}P(L(t)=k|E_k(t)),k\ge 0$
    • 其中
      $L(t)$ 為在
      $t$ 時間時 system 內的顧客數，
      $E_k(t)$ 則是在時間 t 時發生了 arrival。

M/M/1 queue

• 1個 server，system size 為無限
• arrival process: poisson process with rate
  $\lambda$
• service process: exponentially distributed with rate
  $\mu$
• service disciplne: FCFS
• work-conserving service process

state transition probability

• $P_{i,j}(t)=P(N(t)=j|N(0)=i)$,
  $\mathrm{\Delta }$ 值極小

$$\{\begin{array}{l}{p}_{i,i+1}(\mathrm{\Delta })=\lambda \ast \mathrm{\Delta }+o(\mathrm{\Delta }),i=0.1,\cdots \\ p_{i,i-1}(\mathrm{\Delta })=\mu \ast \mathrm{\Delta }+o(\mathrm{\Delta }),i=1,2,\cdots \\ p_{i,i}(\mathrm{\Delta })=1-(\lambda +\mu )\ast \mathrm{\Delta }+o(\mathrm{\Delta }),i=1,2,\cdots \\ p_{0,0}(\mathrm{\Delta })=1-\lambda \ast \mathrm{\Delta }+o(\mathrm{\Delta })\end{array}$$

global balance equation

$$\{\begin{array}{l}\lambda p_{n-1}+\mu p_{n+1}-(\lambda +\mu )p_n=0,n\ge 1\\ \mu p_1-\lambda p_0=0,n=0\end{array}$$

迭代法解

• 目標是求得
  $p_0$ 和
  $p_n$ 的 close form

$\mu p_1-\lambda p_0=0\Rightarrow p_1=\frac{\lambda }{\mu }{p}_0$

$\lambda p_0+\mu p_2-(\lambda +\mu )p_1=0$

$$\begin{array}{rl}{p}_2& =\frac{1}{\mu }((\lambda +\mu )p_1-\lambda p_0)\\ & =\frac{1}{\mu }((\lambda +\mu )\frac{\lambda }{\mu }{p}_0-\lambda p_0)\\ & =\frac{1}{\mu }(\frac{{\lambda }^2}{\mu }{p}_0)\\ & =\frac{{\lambda }^2}{{\mu }^2}{p}_0\end{array}$$

$p_n=({\displaystyle \frac{\lambda }{\mu }}{)}^n{p}_0$

• 定義
  $\rho \equiv {\displaystyle \frac{\lambda }{\mu }}$ 為 ultilization factor(rate)

$$\begin{gathered} {\displaystyle \sum _{n=0}^{\mathrm{\infty }}{\rho }^n{p}_0=1} \\ \Rightarrow {\displaystyle \frac{1}{1-\rho }}{p}_0=1,\text{if}\rho <1 \\ \Rightarrow p_0=1-\rho \\ \Rightarrow p_n={\rho }^n(1-\rho ) \end{gathered}$$

透過 generating function 解

• 定義
  $P(z)={\displaystyle \sum _{n=0}^{\mathrm{\infty }}{z}^n{p}_n,|z|\le 1}$ (
  $z$ 是複數平面上一點，在單位圓內)
  
  $$\{\begin{array}{l}(\lambda +\mu )p_n=\lambda p_{n-1}+\mu p_{n+1},n\ge 1\\ \lambda p_0=\mu p_1,n=0\end{array}$$
  
  $/\mu$ 後寫成
  
  $$\{\begin{array}{l}\rho \cdot p_n=\rho \cdot p_{n-1}+p_{n+1},n\ge 1\\ \rho \cdot p_0=p_1,n=0\end{array}$$
  同乘上
  $z^n$ 並將所有式子相加起來
  
  $(\rho +1){\displaystyle \sum _{n=1}^{\mathrm{\infty }}{z}^n{p}_n+\rho \cdot p_0=\rho \sum _{n=1}^{\mathrm{\infty }}{z}^n{p}_{n-1}+\sum _{n=0}^{\mathrm{\infty }}{z}^n{p}_{n+1}}$
  將
  $\sum$ 的係數盡可能調成與
  $P(z)$ 一致
  
  $$\begin{gathered} (\rho +1){\displaystyle \sum _{n=0}^{\mathrm{\infty }}{z}^n{p}_n-p_0=\rho z\sum _{n=1}^{\mathrm{\infty }}{z}^{n-1}{p}_{n-1}+{\displaystyle \frac{1}{z}}\sum _{n=1}^{\mathrm{\infty }}{z}^{n+1}{p}_{n+1}} \\ \Rightarrow (\rho +1)P(z)-p_0=\rho zP(z)+{\displaystyle \frac{1}{z}}(P(z)-p_0) \\ \Rightarrow (\rho z^2-\rho z-z+1)P(z)=(1-z)p_0 \\ \Rightarrow P(z)={\displaystyle \frac{p_0}{1-\rho z}} \end{gathered}$$
  boundary condition: z = 1
  
  $$\begin{gathered} P(z=1)={\displaystyle \sum _{n=0}^{\mathrm{\infty }}{1}^n{p}_n=\sum _{n=0}^{\mathrm{\infty }}{p}_n=1={\displaystyle \frac{p_0}{1-\rho }}} \\ \Rightarrow p_0=1-\rho ,P(z)={\displaystyle \frac{1-\rho }{1-\rho z}},\rho <1,|z|\le 1 \end{gathered}$$
  
  $$\begin{gathered} P(z)={\displaystyle \frac{1-\rho }{1-\rho z}}={\displaystyle \sum _{n=0}^{\mathrm{\infty }}(1-\rho ){\rho }^n{z}^n=\sum _{n=0}^{\mathrm{\infty }}{z}^n{p}^n} \\ \Rightarrow p^n=(1-\rho ){\rho }^n \end{gathered}$$

long-term system

• mean system size

  $\overline{N}={\displaystyle \sum _{i=0}^{\mathrm{\infty }}i{P}_i={\displaystyle \frac{\rho }{1-\rho }}={\displaystyle \frac{\lambda }{\mu -\lambda }}}$

• 因為 service time 是 exponential distirbution，剩餘的 service time (waiting)也是 exponential distribution

• mean system time

  $D(t)={\displaystyle \sum _{i=1}^{N(t)}{Y}_i+Y}$
  • $Y_i$: service time of customer
    $i$
  • $Y$: remaining service time

• $E(D(t))=\overline{D}=E(Y_1)\ast \overline{N}+E(Y)={\displaystyle \frac{1}{\mu }}\cdot {\displaystyle \frac{\lambda }{\mu -\lambda }}+{\displaystyle \frac{1}{\mu }}={\displaystyle \frac{1}{\mu -\lambda }}$

waiting time distribution

• $T_q$: random variable representing time spent waiting in queue
• $D_q(t)$: CDF of
  $T_q$

1. t = 0
   

   $q(n)\equiv Pr\{\text{n in system at arrival}\}$
   • $q(n)=p(n)$ in M/M/1
   $$\begin{gathered} D_q(0)=Pr\{T_q\le 0\}=Pr\{T_q=0\}\text{(waiting time can not be negative)} \\ =Pr\{\text{system is empty at arrival}\}=q_0=p_0=1-\rho \end{gathered}$$

2. t > 0
   

   $$\begin{gathered} D_q(t)=Pr\{T_q\le t\} \\ ={\displaystyle \sum _{n=1}^{\mathrm{\infty }}Pr\{T_q\le t|\text{n in system at arrival}\}\times Pr\{\text{n in system at arrival}\}+Pr\{T_q=0\}} \\ ={\displaystyle \sum _{n=1}^{\mathrm{\infty }}Pr\{\text{time for n service completion}|\text{n in system at arrival}\}\times p_n+p_0} \\ ={\displaystyle \sum _{n=1}^{\mathrm{\infty }}(1-\rho ){\rho }^n{\int }_0^t{\displaystyle \frac{\mu (\mu x{)}^{n-1}}{(n-1)!}}{e}^{-\mu x}dx+(1-\rho )} \\ =(1-\rho )\rho {\int }_0^t\mu e^{-\mu x}{\displaystyle \sum _{n=1}^{\mathrm{\infty }}{\displaystyle \frac{(\rho \mu x{)}^{n-1}}{(n-1)!}}+(1-\rho )} \\ =(1-\rho )\rho {\int }_0^t\mu e^{-\mu x(1-\rho )}+(1-\rho ) \\ =\rho {\int }_0^t\mu (1-\rho )e^{-\mu (1-\rho )x}+(1-\rho ) \\ =\rho [1-e^{-\mu (1-\rho )t}]+(1-\rho ) \\ =1-\rho e^{-\mu (1-\rho )t} \end{gathered}$$
   $$\begin{gathered} D_q=E[T_q]={\displaystyle {\int }_0^{\mathrm{\infty }}t\cdot d{D}_q(t)} \\ ={\displaystyle {\int }_0^{\mathrm{\infty }}t[\rho \mu (1-\rho )e^{-\mu (1-\rho )t}]dt=\rho {\displaystyle \frac{1}{\mu (1-\rho )}}} \end{gathered}$$

system time distribution

• $T$: random variable representing time a customer stays in the system
• $D(t)$: CDF of
  $T$

$$\begin{gathered} D(t)=Pr\{T\le t\} \\ ={\displaystyle \sum _{n=0}^{\mathrm{\infty }}Pr\{T\le t|\text{n in system at arrival}\}\times q_n} \\ ={\displaystyle \sum _{n=0}^{\mathrm{\infty }}(1-\rho ){\rho }^n{\int }_0^t\mu e^{-\mu x}{\displaystyle \frac{(\mu x{)}^n}{(n)!}}dx} \\ =(1-\rho ){\displaystyle {\int }_0^t\mu e^{-\mu x}\sum _{n=0}^{\mathrm{\infty }}{\displaystyle \frac{(\rho \mu x{)}^n}{(n)!}}dx} \\ =(1-\rho ){\displaystyle {\int }_0^t\mu e^{-(1-\rho )\mu x}dx} \\ =1-e^{-(1-\rho )\mu t} \\ \Rightarrow \overline{D}={\displaystyle \frac{1}{\mu (1-\rho )}}={\displaystyle \frac{1}{\mu -\lambda }} \end{gathered}$$

• $X_s$: number of customers being served
  • $E(X_s)=0\cdot q_0+1\cdot (1-q_0)=(1-p_0)=\rho$
  • with Little's Law:
    $E(X_s)=\overline{\lambda }\cdot \overline{x}=\lambda {\displaystyle \frac{1}{\mu }}={\displaystyle \frac{\lambda }{\mu }}=\rho$
• $X$: number of customers in the system
  • $E(X)={\displaystyle \sum _{k=0}^{\mathrm{\infty }}k\cdot p_k={\displaystyle \frac{\rho }{1-\rho }}}$
• $X_w$: number of customers waiting in the system
  • $E(X_w)={\displaystyle \sum _{k=0}^{\mathrm{\infty }}(k-1)\cdot p_k=\sum _{k=0}^{\mathrm{\infty }}k\cdot p_k-\sum _{k=0}^{\mathrm{\infty }}{p}_k={\displaystyle \frac{{\rho }^2}{1-\rho }}}$

System time, waiting time, service time 的關係

• $T$: system time
• $W$: waiting time
• $x$: service time

$T=W+x\Rightarrow \overline{T}=\overline{W}+\overline{x}$
用 Little's Law 可以得到

• $\overline{T}={\displaystyle \frac{E(X)}{\lambda }}={\displaystyle \frac{1}{\mu (1-\rho )}}$
• $\overline{W}={\displaystyle \frac{E(X_w)}{\lambda }}={\displaystyle \frac{\rho }{\mu (1-\rho )}}$
• $\overline{x}={\displaystyle \frac{1}{\mu }}$

$\overline{T}$ 也可用另一種方式計算得到

$\overline{T}=\overline{x}+{\displaystyle \sum _{k=0}^{\mathrm{\infty }}k\cdot \overline{x}\cdot p_k}$

M/M/c queue

state transition probability

$$\{\begin{array}{l}{P}_{i,i+1}(\mathrm{\Delta })=\lambda \mathrm{\Delta }+o(\mathrm{\Delta }),i=0,1,\cdots \\ P_{i,i-1}(\mathrm{\Delta })=i\mu \mathrm{\Delta }+o(\mathrm{\Delta }),0\le i\le c\\ P_{i,i}(\mathrm{\Delta })=1-(\lambda +i\mu )\mathrm{\Delta }+o(\mathrm{\Delta }),0\le i\le c\\ P_{i,i}(\mathrm{\Delta })=1-(\lambda +c\mu )\mathrm{\Delta }+o(\mathrm{\Delta }),i\ge c\end{array}$$

global balance equation

$$\{\begin{array}{l}0=-(\lambda +n\mu )p_n+\lambda p_{n-1}+(n+1)\mu p_{n+1},0<n<c\\ 0=-(\lambda +c\mu )p_n+\lambda p_{n-1}+(n+1)\mu p_{n+1},n\ge c\\ 0=-\lambda p_0+\mu p_1\end{array}$$

$p_n={\displaystyle \frac{\lambda }{n\mu }}{p}_{n-1}=({\displaystyle \frac{\lambda }{\mu }}{)}^n{\displaystyle \frac{1}{n!}}{p}_0,n=1,2,\cdots ,c-1$

$p_n={\displaystyle \frac{\lambda }{c\mu }}{p}_{n-1}=({\displaystyle \frac{\lambda }{\mu }}{)}^n{\displaystyle \frac{1}{c!}}{\displaystyle \frac{1}{c^{n-c}}}{p}_0,n\ge c$

$p_0=[{\displaystyle {\displaystyle \frac{1}{c!}}({\displaystyle \frac{\lambda }{\mu }}{)}^c{\displaystyle \frac{1}{(1-\frac{\lambda }{c\mu })}}+\sum _{j=0}^{c-1}({\displaystyle \frac{\lambda }{\mu }}{)}^j{\displaystyle \frac{1}{j!}}{]}^{-1}}$

• $\rho ={\displaystyle \frac{\lambda }{c\mu }},r={\displaystyle \frac{\lambda }{\mu }}$
• $p_n=$
  
  $$\{\begin{array}{l}{\displaystyle \frac{r^n}{n!}}{p}_0,0<n<c\\ {\displaystyle \frac{r^n}{c^{n-c}c!}}{p}_0,n\ge c\end{array}$$

L, Lq, W(T), Wq(Tq)

• $L$: mean number of customers in the system
• $L_q$: mean number of customers in the queue
• $W$: mean system time
• $W_q$: mean waiting time in the queue

$$\begin{gathered} L_q={\displaystyle \sum _{n=c+1}^{\mathrm{\infty }}(n-c)p_n} \\ ={\displaystyle \sum _{n=c+1}^{\mathrm{\infty }}(n-c){\displaystyle \frac{r^n}{c^{n-c}c!}}{p}_0} \\ ={\displaystyle \frac{r^c}{c!}}{p}_0{\displaystyle \sum _{n=c+1}^{\mathrm{\infty }}(n-c)({\displaystyle \frac{r}{c}}{)}^{n-c}} \\ ={\displaystyle \frac{r^c}{c!}}{p}_0{\displaystyle \sum _{n=c+1}^{\mathrm{\infty }}(n-c)(\rho {)}^{n-c}} \\ ={\displaystyle \frac{r^c}{c!}}{p}_0{\displaystyle \frac{\rho }{(1-\rho {)}^2}} \\ ={\displaystyle \frac{r^c}{c!(1-\rho {)}^2}}{p}_0 \end{gathered}$$

$L=L_q+r={\displaystyle \frac{r^c}{c!(1-\rho {)}^2}}{p}_0+r$

---

$\overline{T}=\overline{x}+\overline{W}=\frac{1}{\mu }+{\displaystyle \sum _{k=c}^{\mathrm{\infty }}E(W|k)p_k^{(a)}}$

$E(T)={\displaystyle \frac{1}{\mu }}+{\displaystyle \sum _{k=c}^{\mathrm{\infty }}{\displaystyle \frac{k-c+1}{c\mu }}{p}_k}$

$$\begin{gathered} \overline{T}=\frac{1}{\mu }+{\displaystyle \sum _{k=c}^{\mathrm{\infty }}{\displaystyle \frac{k-c+1}{c\mu }}{p}_c({\displaystyle \frac{\lambda }{c\mu }}{)}^{k-c}} \\ =\frac{1}{\mu }+{\displaystyle \frac{p_c}{c\mu }}{\displaystyle \sum _{k=c}^{\mathrm{\infty }}(k-c+1)({\displaystyle \frac{\lambda }{c\mu }}{)}^{k-c}} \\ =\frac{1}{\mu }+{\displaystyle \frac{p_c}{c\mu }}{\displaystyle \sum _{i=1}^{\mathrm{\infty }}i({\displaystyle \frac{\lambda }{c\mu }}{)}^{i-1}} \\ =\frac{1}{\mu }+{\displaystyle \frac{c\mu p_c}{(c\mu -\lambda {)}^2}} \end{gathered}$$

---

$$\begin{gathered} D_q(0)=Pr\{T_q=0\}=Pr\{\le c-1\text{ in system at arrival}\} \\ ={\displaystyle \sum _{n=0}^{c-1}{q}_n=p_0\sum _{n=0}^{c-1}{\displaystyle \frac{r^n}{n!}},p_0=({\displaystyle \frac{r^c}{c!(1-\rho )}}+\sum _{n=0}^{c-1}{\displaystyle \frac{r^n}{n!}}{)}^{-1}} \\ =1-{\displaystyle \frac{r^c}{c!(1-\rho )}}{p}_0\Rightarrow Pr\{T_q>0\}=\frac{r^c}{c!(1-\rho )}{p}_0 \end{gathered}$$

---

$$\begin{gathered} D_q(t)=Pr\{T_q\le t\} \\ ={\displaystyle \sum _{n=c}^{\mathrm{\infty }}Pr\{n-c+1\text{ completions}\le t|n\text{ in system at arrival}\}{q}_n+D_q(0)} \\ ={\displaystyle \sum _{n=0}^{\mathrm{\infty }}{\displaystyle \frac{r^c}{c^{n-c}c!}}{p}_0{\int }_0^t{\displaystyle \frac{c\mu (c\mu x{)}^{n-c}}{(n-c)!}}{e}^{-c\mu x}dx+D_q(0)} \\ ={\displaystyle \frac{r^c}{(c-1)!}}{p}_0{\displaystyle {\int }_0^t\mu e^{-c\mu x}\sum _{n=0}^{\mathrm{\infty }}{\displaystyle \frac{(r\mu x{)}^{n-c}}{(n-c)!}}dx+D_q(0)} \\ ={\displaystyle \frac{r^c}{(c-1)!}}{p}_0{\displaystyle {\int }_0^t\mu e^{-\mu (c-r)x}dx+D_q(0)} \\ ={\displaystyle \frac{r^c}{(c-1)!(c-r)}}{p}_0{\displaystyle {\int }_0^t\mu (c-r)e^{-\mu (c-r)x}dx+D_q(0)} \\ ={\displaystyle \frac{r^c}{c!(1-\rho )}}(1-e^{-(c\mu -\lambda )t})+D_q(0),D_q(0)=\frac{r^c}{c!(1-\rho )}{p}_0 \\ =1-{\displaystyle \frac{r^c}{c!(1-\rho )}}(1-e^{-(c\mu -\lambda )t})=1-Pr\{T_q>t\} \\ \Rightarrow Pr\{T_q>t\}={\displaystyle \frac{r^c}{c!(1-\rho )}}(1-e^{-(c\mu -\lambda )t}) \end{gathered}$$

---

$Pr\{T_q>0\}={\displaystyle \frac{r^c{p}_0}{c!(1-\rho )}},Pr\{T_q>t\}={\displaystyle \frac{r^c{p}_0}{c!(1-\rho )}}\cdot e^{-(c\mu -\lambda )t}$

$Pr\{T_q>t|T_q>0\}={\displaystyle \frac{Pr\{T_q>t\}}{Pr\{T_q>0\}}}=1-e^{-(c\mu -\lambda )t}$

Finite-Source Queue

• ${\lambda }_n=$
  
  $$\{\begin{array}{l}(M-n)\lambda ,0\le n<M\\ 0,n\ge M\end{array}$$
• ${\mu }_n=$
  
  $$\{\begin{array}{l}n\mu ,0\le n<c\\ c\mu ,n\ge c\end{array}$$

tags: 1111_courses queueing system