「排队论」排队论

排队论

排队论
- 模型背景（排队现象）
- 概念
  - 排队系统的要素
  - 模型参数
    - 系统运行状态参数
    - 系统运行指标参数
- 模型分类
  - M/M/1模型（单服务台负指数排队系统）
  - M/M/S模型
- 代码
  - 计算代码
  - 仿真代码
  - 操作及相关说明

模型背景（排队现象）

到达顾客	服务内容	服务机构
病人	诊断/手术	医生/手术台
进港的货船	装货/卸货	码头泊位
到港的飞机	降落	机场跑道
电话拨号	通话	交换台
故障机器	修理	修理技工
修理技工	领取修配零件	仓库管理员
上游河水	入库	水闸管理员

概念

排队系统的要素

顾客输入过程1
排队结构与排队规则2
服务机构与服务规则3

模型参数

系统运行状态参数

系统状态N(t)" role="presentation"> $N (t)$

——指排队系统在时刻 t" role="presentation"> $t$ 时的全部顾客数N(t)" role="presentation"> $N (t)$ ，包括“排队顾客数”和“正被服务顾客数”。

系统状态概率：

（1）瞬态概率Pn(t)" role="presentation"> $P_{n} (t)$

——表示时刻 t" role="presentation"> $t$ 系统状态N(t)=n" role="presentation"> $N (t) = n$ 的概率；

（2）稳态概率Pn" role="presentation"> $P_{n}$

——Pn=limt→∞Pn(t)" role="presentation"> $P_{n} = lim_{t \to \infty} P_{n} (t)$ ；

——一般排队系统运行了一定长时间后，系统状态的概率分布不再随时间 t" role="presentation"> $t$ 变化，即初始时刻(t=0)" role="presentation"> $(t = 0)$ 系统状态的概率分布(Pn(0),n>>0)" role="presentation"> $(P_{n} (0), n >> 0)$ 的影响将消失。

系统运行指标参数

用于评价排队系统的优劣，重点。

1、队长与排队长

（1）队长：系统中顾客数(n)" role="presentation"> $(n)$ ，期望值记为Ls(L)" role="presentation"> $L_{s} (L)$ ；

（2）排队长：系统中排队等待服务的顾客数，期望值记为Lq" role="presentation"> $L_{q}$

2、逗留时间与等待时间

（1）逗留时间：指一个顾客在系统中的全部停留时间，期望值记为Ws(W)" role="presentation"> $W_{s} (W)$ ;

（2）等待时间：指一个顾客在系统中排队等待时间，期望值记为Wq" role="presentation"> $W_{q}$

（Ws=Wq+E" role="presentation"> $W_{s} = W_{q} + E$ (服务时间)）

3、其他相关指标

（1）忙期：指从顾客到达空闲服务机构起到服务机构再次空闲的时间长度；

（2）忙期服务量：指一个忙期内系统平均完成服务的顾客数；

（3）损失率：指顾客到达排队系统，未接受服务而离去的概率；

（4）服务强度：ρ=λ/sμ" role="presentation"> $ρ = λ / s μ$ ；

模型分类

这里我们主要谈两种模型

M/M/1模型（单服务台负指数排队系统）

模型条件：

输入过程——顾客源是无限的，顾客到达完全是随机的，单个到来，到达过程服从泊松分布，且是平稳的；
排队规则——单队，且队长没有限制，先到先服务；
服务机构——单服务台，服务时间长短是随机的，服从相同的指数分布。

M/M/S模型

此模型与M/M/1模型不同之处在于有 S 个服务台，各服务台的工作相互独立，服务率相等，如果顾客到达时，S 个工作台都忙着，则排成一队等待，先到先服务的单队模型。
整个系统的平均服务率为sμ" role="presentation"> $s μ$ ，ρ∗=λ/sμ" role="presentation"> $ρ^{*} = λ / s μ$ ，(ρ∗<1)" role="presentation"> $(ρ^{*} < 1)$ 为该系统的服务强度。

代码

计算代码

s = 3;
mu = 24;
lambda = 54;
% 一般单位时间为小时
ro = lambda / mu;
ros = ro / s;
sum1 = 0;

for i = 0 : (s - 1)
    sum1 = sum1 + ro .^ i / factorial(i);
end

sum2 = ro .^ s / factorial(s) / (1 - ros);

p0 = 1 / (sum1 + sum2);
p = ro .^ s .* p0 / factorial(s) / (1 - ros);
Lq = p .* ros / (1 - ros);
L = Lq + ro;
W = L / lambda;
Wq = Lq / lambda;
fprintf('排队等待的平均人数为%5.2f人\n', Lq)
fprintf('系统内的平均人数为%5.2f人\n', L)
fprintf('平均逗留时间为%5.2f分钟\n', W * 60)
fprintf('平均等待时间为%5.2f分钟\n', Wq * 60)

仿真代码

clear
clc
%************************************************
%初始化顾客源
%************************************************
%总仿真时间(变量)
Total_time = 10;
%队列最大长度
N = 100000000000;
%到达率与服务率(变量，对于服务台增多的情况可成倍减小 lambda 的大小)
lambda = 10;
mu = 6;
%平均到达时间与平均服务时间
arr_mean = 1 / lambda;
ser_mean = 1 / mu;
arr_num = round(Total_time * lambda * 2);
events = [];
%按负指数分布产生各顾客到达的时间间隔
events(1, :) = exprnd(arr_mean, 1, arr_num);
%各顾客的到达时刻等于时间价格的累积和
events(1, :) = cumsum(events(1, :));
%按负指数分布产生各顾客服务时间
events(2, :) = exprnd(ser_mean, 1, arr_num);
%计算仿真顾客个数，即到达时刻在仿真时间内的顾客数
len_sim = sum(events(1, :) <= Total_time);
%********************************
%计算第 1 个顾客的信息
%********************************
%第 1 个顾客进入系统后直接接受服务，无需等待
events(3, 1) = 0;
%其离开时刻等于其到达时刻与服务时间之和
events(4, 1) = events(1, 1) + events(2, 1);
%其肯定被系统接纳，此时系统内共有
% 1 个顾客，故标志位置 1
events(5, 1) = 1;
%其进入系统后，系统内已有成员序号为 1
member = [1];
for i = 2 : arr_num
    %如果第 i 个顾客的到达时间超过了仿真时间，则跳出循环

    if events(1, i) > Total_time

        break;
    else
        number = sum(events(4, member) > events(1, i));
        %如果系统已满，则系统拒绝第 i 个顾客，其标志位置 0
        if number >= N + 1
            events(5, i) = 0;
            %如果系统为空，则第 i 个顾客直接接受服务
        else
            if number == 0
                %其等待时间为 0
                events(3, i) = 0;
                %其离开时刻等于到达时刻与服务时间之和
                events(4, i) = events(1, i) + events(2, i);
                %其标志位置 1
                events(5, i) = 1;
                member = [member, i];
                %如果系统有顾客正在接受服务，且系统等待队列未满，则录 i 个顾客进入系统

            else len_mem = length(member);
                %其等待时间等于队列中前一个顾客的离开时间减去其到达时刻
                events(3, i) = events(4, member(len_mem)) - events(1, i);
                %其离开时刻等于队列中前一个顾客的离开时刻加上其服
                %务时间
                events(4, i) = events(4, member(len_mem)) + events(2, i);
                %标识位表示其进入系统后，系统内共有的顾客数
                events(5, i) = number + 1;
                member = [member, i];
            end
        end
    end
end
%仿真结束时，进入系统的总顾客数
len_mem = length(member);
%***************************************
%输出结果
%***************************************
%绘制在仿真时间内，进入系统的所有顾客的到达时刻和离
%开时刻曲线图（stairs：绘制二维阶梯图）
stairs([0, events(1, member)], 0 : len_mem);
hold on;
stairs([0, events(4, member)], 0 : len_mem, '.-r');
legend('到达时间', '离开时间');
hold off;
grid on;
%绘制在仿真时间内，进入系统的所有顾客的停留时间和等
%待时间曲线图（plot, 绘制二维线性图）
figure;
plot(1 : len_mem, events(3, member), 'r-*', 1 : len_mem, events(2, member) + events(3, member), 'k-');
legend('等待时间', '停留时间');
grid on;

操作及相关说明

对于计算代码，可以修改的变量就是1、2、3行的“s”、“mu”和“lambda”，它们的含义在前面已经给出。有一点需要注意的是，参数的单位时间以“小时”为准。

对于仿真代码，可以修改的变量就是第七行的总仿真时间“Total_time”，第十一行的“lambda”和第十二行的“mu”。运行脚本后可以得到两个图像。

对于麦当劳这种类似多服务台多队列的情况，是几个M/M/1模型的组合，总共有几个服务台（队列）就把 λ" role="presentation"> $λ$ 除以几。

仅研究顾客源无限，顾客逐个到达，随机到达，相互独立，输入过程平稳的情况。 ↩
仅研究禁止推出与禁止转移的情形。 ↩
仅研究服务员逐个服务，先到先服务(FCFS)，服务时间平稳的情形。 ↩

排队论

排队论

排队论