Site Overlay

运筹学笔记:排队论基础

基本概念

排队系统的组成

  • 输入过程:顾客按照怎样的规律到达
    • 顾客的数量
    • 单个到达还是批量到达
    • 顾客到达间隔的分布(如泊松分布,负指数分布)
  • 排队规则
    • 损失制:到达后发现被占用,顾客离开(不允许排队)
    • 等待制:排队等候
    • 先到先服务(队列)
    • 后到先服务(栈)
    • 随机服务
    • 按优先权服务
    • 混合制:如当人数超过阈值,顾客不再排队
  • 服务机构
    • 服务台的数目
    • 任意时刻的容量
    • 每个顾客服务时间的分布

服务密度$\rho = \dfrac{\lambda}{\mu}$,即到达数比服务数。越小效率越高。

符号描述

$n$:排队系统中顾客数目

$\lambda$:顾客到达的平均速率(到达顾客数/时间)

$\mu$:系统的平均服务速率(服务顾客数/时间)

$p_n(t)$$t$ 时刻有 $n$ 个顾客的概率。

$C$:服务台个数

$\text{FCFS}$:FIFO

$\text{FCLS}$:FILO

PR:优先权服务的排队规则

$M$:负指数过程

$D$:定长型分布

$E_k$:k阶爱尔朗分布

a:顾客到达过程的概率分布(输入)

b:服务过程的概率分布(输出)

d:排队系统的最大容量

e:顾客总体的数量

f:排队规则

a/b/c/e 记号,如 $M/M/1/\infty$ 表示

  1. 顾客以泊松过程到达
  2. 服务时间服从指数分布
  3. 单服务台
  4. 顾客源无限

1971 标准:a/b/c/d/e/f

顾客到达的分布:泊松分布

$$
p_{n}(t)=\frac{(\lambda t)^{n}}{n !} e^{-\lambda t}, t>0, n=0,1,2, \cdots
$$

表示长 $t$ 的时间区间到达 $n$ 个顾客的概率。期望和方差都是 $\lambda t$

顾客到达的密集程度(间隔):负指数分布

上面的泊松分布,当 $n=0$,即 $[0,t]$没有顾客到达的概率是 $p_0(t) = e^{-\lambda t}$

则至少有一个顾客到达的概率是 $F_T(t) = 1 - e^{-\lambda t}$,期望是 $\dfrac{1}{\lambda}$,方差是 $\dfrac{1}{\lambda^2}$

服务时间的分布:负指数分布

$\mu$ 是单位时间内可以服务完的人数。则服务时间分布为 $f_v(t) = \mu e^{-\mu t}$。期望 $\dfrac{1}{\mu}$ 表示一个顾客的平均服务时间。

负指数分布具有无记忆性。所以研究过程不必考虑之前的情况,只需要研究当前的排队状况。

泊松过程的三个条件

  1. 无后效性:前面到达的顾客数,不影响后面到达的顾客数。
  2. 平稳性:顾客到达的多少只和时间间隔有关。
  3. 普通性:极短时间间隔到达多个顾客的概率极小。

单服务台模型(M/M/1)

  1. 输入过程: 顾客源是无限的,顾客单个到达,相互独立,到达数服从泊松分布,到达过程是平稳的;

  2. 排队规则: 单队,队长无限制,先到先服务;

  3. 服务机构: 单服务台,各顾客服务时间是相互独立的,服从相同的指数分布.

系统状态概率

$p_n$:系统中有 $n$ 个顾客的概率。

$$
\left\{\begin{array}{ccc}
p_{0}=1-\rho \\
p_{n}=\rho^{n}(1-\rho) & p_{n}=\rho^{n} p_{0} \quad n\geq 1\\
\rho=\frac{\lambda}{\mu} & 0 \leq \rho<1 \end{array}\right. $$

排队系统的运行指标

$L$:排队顾客数期望。正在等候的正在服务的之和。

$L_q$:排队中的顾客数期望。

$W$:进入系统时间的期望。包括排队时间被服务时间之和。

$W_q$:顾客排队时间的期望。

系统运行指标的计算

$L$
$$
L = \dfrac{\rho}{1-\rho} = \dfrac{\lambda}{\mu - \lambda}
$$
$L_q$
$$
L_q = \dfrac{\rho^2}{1-\rho}
$$

$W$

顾客在系统中的时间 $T_s$ 是一个随机变量,服从参数为 $\mu - \lambda$ 的负指数分布。

$$
\begin{array}{ll}
f(t)=(\mu-\lambda) e^{-(\mu-\lambda) t} & t \geq 0 \\
W=E\left(T_{S}\right)=\dfrac{1}{\mu-\lambda}
\end{array}
$$

$W_q$

$$
W_{q}=W-\frac{1}{\mu}=\frac{1}{\mu-\lambda}-\frac{1}{\mu}=\frac{\rho}{\mu-\lambda}=\frac{\lambda}{\mu(\mu-\lambda)}
$$
系统内多于 $m$ 个顾客的概率
$$
P\{N>1\}=1-p_{0}-p_{1}=1-(1-\rho)-\rho(1-\rho)=\rho^{2}\\
p\{N>m\} = \rho^{m+1}
$$
顾客停留时间大于 $t$ 的概率
$$
P\{W>t\}=e^{-\mu(1-\rho) t}=e^{-(\mu-\lambda) t}
$$

顾客在系统中平均排队时间超过 t 的概率是

$$
P\left\{W_{q}>t\right\}=\rho e^{-\mu(1-\rho) t}
$$
服务台忙期

$0<\rho<1$ 时,忙期随 $\rho$ 值得增加而增加,当 $\rho \rightarrow 1$ 时,系统趋于饱和状态,服务台忙碌的均值为

$$
E(B)=\frac{\rho}{1-\rho}=\frac{\lambda}{\mu-\lambda}
$$

在一个忙期内完成服务的平均顾客数为

$$
N_{B}=\frac{1}{\mu-\lambda} \cdot \mu=\frac{1}{1-\rho}(0<\rho<1) $$

Little 公式

$\lambda_{e}$ 为顾客到达系统中速率的平均值,则在很宽的条件下有:

$W=\dfrac{L}{\lambda_{e}}, W_{q}=\dfrac{L_{q}}{\lambda_{e}},$

$M / M / 1 / \infty / \infty / F C F S$ 系统中,顾客到达的速率是常数 $\lambda,$$\lambda_{e}=\lambda,$ 因此:

$W=\dfrac{L}{\lambda}, W_{q}=\dfrac{L_{q}}{\lambda},$ 称为利特尔公式.

例题

【例子】服务台全天服务,假设顾客到达的时间间隔服从均值为 1 的负指数分布。现在有一位顾客正好中午12:00 到达,试求:

(1)下一个顾客将在下午 1:00 前到达的概率;

(2)在下午 1:00 与 2:00 之间到达的概率:

(3)在下午 2:00 以后到达的概率。

【分析与解答】

(1)由已知,t 时间至少有一个顾客到达的概率是 $F_T(t) = 1 - e^{-t}$,当 $t = 1$$P = 1-e^{-1} = 0.6321$,所以概率是 $63.21\%$.

(2)在 2:00 内到达的概率是 $1-e^{-2} = 0.8646$$0.8646 - 0.6321 = 0.2325$,即 $23.25\%$

(3)在 2:00 内到达的概率是 $0.8646$,则之后才到达的概率是 $1 - 0.8646 = 0.1354 = 13.54\%$.

【例子】小汽车过收费站,到达速率 100 $h^{-1}$,泊松流,检查一辆车 $15s$,为负指数分布,求稳态概率 $p_0, p_1, p_2$ 和系统的各项指标。

https://www.bilibili.com/video/BV1L5411x7vH?p=45

发表评论

电子邮件地址不会被公开。 必填项已用*标注