数模日记3

排队论模型

PS：此处的排队论，真的就是单纯的排队。

排队论研究随机服务系统的确定性规律。

等待时间、服务时间、到达时间具有随机性。

[TOC]

基本组成

输入

• 顾客总体的数量：有限/无限
• 顾客到来的方式：个体/批
• 到达的间隔时间：不确定（随机变量，遵从概率分布）

顾客的行为假定为：

• 在未服务之前不会离开（等待制）
• 当看到队列很长的时候离开（有损失）
• 从一个队列移到另一个队列（上两种结合）

排队规则

• 队列容量：有限/无限

  ——- 此处的队列是排队队列。

• 排队规则：FCFS、LCFS、RSS（random）、PS（priority）、GD（一般规则）

服务规则

• 服务机构（1 / 多）个
• 服务台：并行、串行、混合排列
• 服务方式：单个/批处理

数量指标

每天的排队人数是随机的，所以取长期的平均值。

• ：(line system)平均队长。既在排队、又在接受服务的人。

• ：(line query)平均队列长。只包括排队的人，不包括正在接受服务的人。

• ：(wait system)平均逗留时间。顾客在这个系统中（排队+服务）停留的时间平均值。

• ：(wait query)平均等待时间。顾客在排队的时间的平均值。

为求解以上4个指标，引入：

记号方案

Kendall 记号

• X：顾客到达的时间分布，输入过程的特征。
• Y：服务时间分布。
• Z：服务台的个数。取值 1/c（，表示多个服务台）
• A：排队系统允许的最大顾客容量。取值有限/无限。
• B：顾客总体数量，指不在排队的、外部的顾客数量。（多分 ）取值有限/无限。
• C：排队队则，如FCFS。

常见：

X/Y：

• M：表示泊松过程 or 负指数分布
• D：表示确定型分布
• ：表示 k 阶埃尔朗分布（综合到一起的分布）
• G：表示一般服务时间分布
• GI：表示一般相互独立的时间间隔分布

排队论模型

单服务台模型(FCFS)

（标准型）

求解要建立稳态概率方程：

$$\begin{cases} \lambda P_0=\mu P_1 \\ \lambda P_{n-1}+\mu P_{n+1}-(\lambda +\mu)P_n=0& ,n\ge 1 \\ \end{cases}$$

由递推公式得：

$$P_n = (\frac{\lambda}{\mu})^n P_0$$

令：

$$\sum^{\infty}_{n=0}P_n=1\\ P_0\sum^{\infty}_{n=0}P_n= \frac{P_0}{1-\rho}=1$$

故：

$$P_0=1-\rho\\ P_n=(1-\rho)\rho^n$$

这是系统状态为 的概率，然后接下来计算上述的4个指标。

平均队长：(serve+queue)

$$L_s=\sum_{n=1}^\infty nP_n=\sum_{n=1}^\infty n (1-\rho)\rho^n = \frac{\rho}{1-\rho}=\frac{\lambda}{\mu-\lambda}$$

平均队列长：(queue)

$$L_q=\sum_{n=1}^\infty(n-1)P_n=\frac{\rho\lambda}{\mu-\lambda}$$

平均逗留时间：(serve+queue)

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

平均等待时间：(queue)

$$W_q=W_s-\frac 1{\mu}=\frac{\rho}{\mu-\lambda}=\rho\times W_S$$

其稳态概率方程：

$$\left\{ \begin{aligned} \lambda P_1&=\mu P_1 \\ \lambda P_{n-1}+\mu P_{n+1}&=(\lambda +\mu)P_n& ,1\le n\le N-1 \\ \mu P_N&=\lambda P_{N-1} \end{aligned} \right.$$

它的计算结果已知，自己去Google。

顾客的总体数量是有限的，该模型等价于

假设每个顾客到达率相同且为 ，在系统外的平均顾客数为 。

系统的有效到达率

(有效到达率与顾客总容量以及当前剩余的容量有关)

其稳态方程：

$$\left\{ \begin{aligned} m\lambda_e P_1&=\mu P_1 \\ (m-n+1)\lambda_e P_{n-1}+\mu P_{n+1}&=[(m-n)\lambda_e +\mu]P_n& ,1\le n\le m-1 \\ \mu P_m&=\lambda_e P_{m-1} \end{aligned} \right.$$

多服务台模型（FCFS）

（标准型）

顾客流为泊松流，平均到达率为 ，各个服务台的平均服务率是 ，则：

整个服务机构的平均服务率是： or ，令(系统服务强度)

当 时，会出现排队现象。

稳态方程如下。

$$\begin{cases} \lambda P_0=\mu P_1 \\ \lambda P_{n-1}+(n-1)\mu P_{n+1}=(\lambda +n\mu)P_n& ,1\le n\le c \\ c\mu P_{n+1}+\lambda P_{n-1}=(\lambda+c\mu)P_n&,n\gt c \end{cases}$$

（系统容量有限型）

（顾客源有限型）

略，Google。