大家好，又见面了，我是你们的朋友全栈君。
排队论简介
历史
- 排队论又称随机服务系统，是研究系统随机聚散现象和随机 服务系统工作过程的数学理论和方法，是运筹学的一个分支。
- 排队论的基本思想是 1909 年丹麦数学家 A.K. 埃尔朗在解 决自动电话设计问题时开始形成的，当时称为话务理论。
- 现实生活中如排队买票、病人排队就诊、轮船进港、高速路 上汽车排队通过收费站、机器等待修理等都属于排队论问题。
定义
- 通过对服务对象到来及服务时间的统计研究
- 得出这些数量指标（等待时间、排队长度、忙期长短（决定服务台数量）等）的 统计规律，
- 然后根据这些规律来改进服务系统的结构或重新组织被服务 对象
- 使得服务系统既能满足服务对象的需要，又能使机构的费用 最经济或某些指标最优。
应用
- CUMCM 2009B 的眼科病床的合理安排问题
- MCM 2005B 收费站最佳配置问题
- ICM 2017D 机场安检问题
模型与模拟
排队论基本构成与指标
排队论的基本构成
- 输入过程：描述顾客按照怎样的规律到达排队系统。顾客总 体（有限/无限）、到达的类型（单个/成批）、到达时间间隔。
- 排队规则：指顾客按怎样的规定次序接受服务。常见的有等 待制、损失制、混合制、闭合制。
- 服务机构：服务台的数量; 服务时间服从的分布
排队系统的数量指标
- 队长：系统中的平均顾客数（包括正在接受服务的顾客）。
- 等待队长：系统中处于等待的顾客的数量。
- 等待时间：等待时间包括顾客的平均逗留时间。
- 忙期：连续保持服务的时长。
数学表示
排队论中的符号表示
[{A/B/C/n} ]
A 输入过程，B 服务时间，C 服务台数，n 系统容量。
排队论表示实例 M/M/S/∞
- 输入过程是 Poisson 流 （顾客到达的时间服从泊松分布，到达的时间间隔便服从负指数分布）
- 服务时间服从负指数分布
- 系统有 S 个服务台平行服务
- 系统容量为无穷大的等待制排队系统
等待制模型 M/M/S/∞ S=1
单位时间内到达的人数为λ,所以[0,t] 时间内到达的顾客平均数为 λt
**µ代表单位时间服务人的个数 ** 判断模型是否稳定，一般用比较λ和µ的大小（下图的系统服务强度）
((1-rho)sum_{n=0}^{infty}nrho^{n}),当(rho)<1时候级数收敛
平均等待队长比平均队长少一人，因为一人在接受服务。
平均等待时间=逗留的时间-服务的时间
Little公式是根据前面推导出来。
实例
λ/µ=8/9<1,系统是稳定的。
平均等待7.1个人
等待制模型 M/M/S/∞ S>1(服务台数量>1)
k=[0:s-1]
实例
案例
- 来访人员按照 Poisson 流到达，到达速率为 µ = 20 人/小时。
- 接待人员的服务速率间服 λ = 9 人/小时的负指数分布。
- 为使来访问者等待不超过半小时，最少应配置几名接待员？
lambda = 20; mu = 9; s = 3;
rho = lambda/(s*mu); %服务强度
k=(0:s-1);
p0 = 1./( sum((s*rho).^k./factorial(k)) ...
(s*rho)^s/(factorial(s)*(1-rho)) ); %服务台空闲的概率
Ls = s*rho (s*rho)^s*rho/(factorial(s)*(1-rho)^2)*p0; %平均长度
Ws = Ls/lambda; %平均逗留时间
Wq = Ws - 1/mu%平均等待时间其他模型
混合制：
系统容量K为队长，理发店的的凳子数（等待凳子和服务凳子）
闭合制：
工厂的工人，使用的机器。
单服务台
做模拟：
开始服务, 到达, 离开时刻和服务, 等待时长的关系
- 服务时刻(i) = max{到达时刻(i),离开时刻(i−1)}
- 离开时刻(i) = 服务时刻(i) 服务时长(i)
- 等待时长(i) = 离开时刻(i)−到达时刻(i)
多服务台
开始服务, 到达, 离开时刻和服务, 等待时长的关系
- 服务时刻(i) = max{到达时刻(i),min{服务台空闲时刻}} （假设所有顾客目的尽早的接受服务）
- 所使用服务台(i) = k, 其中 k 使服务台空闲时刻(k) = min
- 离开时刻(i) = 服务时刻(i) 服务时长(i)
- 服务台空闲时刻(k) = 离开时刻(i)
- 等待时长(i) = 离开时刻(i)−到达时刻(i)（包括服务时间）
自动取款机问题
问题
- 银行计划安置取款机, A 机价格和平均服务率都是 B 机的 2 倍. 应购置 1 台 A 机还是 2 台 B 机?
- 顾客平均每分钟到达 1 位，A 型机的平均服务时间为 0.9, B 型机为 1.8 分钟, 顾客到达间隔和服务时间都服从指数分布.
单服务台
属于M/M/1/∞ 模型
代码语言：javascript复制n = 100000; % 模拟顾客总数
mu = 1; muA = 0.9; % 到达率和服务率
tarr = cumsum(exprnd(mu,1,n));% 到达时刻 ，exprnd生成指数分布（到达的时间间隔）
tsrv = exprnd(muA,1,n); % 服务时长
tsta = zeros(1,n); % 初始化服务时刻
tlea = zeros(1,n);% 初始化离开时刻
twat = zeros(1,n); % 初始化等待时长
tsta(1) = tarr(1);% 首位顾客服务时刻=到达时刻
tlea(1) = tsta(1) tsrv(1); % 首位顾客离开时刻
twtime(1) = tlea(1) - tarr(1); % 首位顾客等待时长=0
% 上面初始化第一个顾客
for i = 2:n
% 服务时刻 = max{到达时刻, 上一个顾客离开时刻}
tsta(i) = max(tarr(i),tlea(i-1));
tlea(i) = tsta(i) tsrv(i);% 离开时刻=服务时刻 服务时长
twat(i) = tlea(i) - tarr(i);;% 等待时长=离开时刻-到达时刻
end
hist(twat)
sum(twat)/n两服务台(多个服务台)
代码语言：javascript复制n = 100000; % 模拟顾客总数
mu = 1; muB = 1.8; % 到达率和服务率
tarr = cumsum(exprnd(mu,1,n)); % 到达时刻
tsrv = exprnd(muB,1,n);% 服务时长
tsta = zeros(1,n);% 初始化服务/离开时刻
tlea = zeros(1,n); % 初始化等待时长
twat = zeros(1,n);% 初始化服务台结束服务时刻
last = [0 0];%几个服务台几个0
for i = 2:n
[minemp, k] = min(last); % 找出最快结束服务的服务台时刻
tsta(i) = max(tarr(i),minemp);% 服务时刻
tlea(i) = tsta(i) tsrv(i); % 离开时刻
last(k) = tlea(i); % 服务台结束服务时刻
twat(i) = tlea(i) - tarr(i);% 等待时长
end
hist(twat)
sum(twat)/n
真题
2013HIMCM-B: 银行服务问题
分析
如何生成序列来满足题意概率分布呢？
举一个例子，由时间间隔 t = [0 1 2] 和概率 p = [0.2 0.3 0.5] 得到各到顾客达时间间隔 。
- 先把概率p倒过来求前缀和 [p′ = cumsum([0.5,0.3,0.2]) = [0.5,0.8,1.0] ]
- 我们生成随机数x，则x<=0.5的概率为0.5，0.5<x<=0.8的概率为0.3，0.8<x<=1.0的概率为0.2 [R = rand(1,5) = [0.1,0.9,0.2,0.4,0.8]; ]
- 替换随机序列的数 把随机序列R<0.5的数换成2……
[R(R < 0.5) = 2, R(R < 0.8) = 1, R(p < 1.0) = 0 ]
由到达时间间隔得到各顾客到达时刻
[间隔 = [0,1,3,2] ⇒ 时刻 = cumsum(间隔) = [0,1,4,6] ]
开始服务, 到达, 离开时刻和服务, 等待时间的关系:
- 开始服务的时刻(i) = max{到达时刻(i),离开时刻 (i-1)}
- 离开时刻(i) = 开始服务的时刻(i) 服务时间(i)
- 等待时间(i) = 离开时刻(i)−到达时刻(i)−服务时间(i)（不是逗留时刻
代码
代码语言：javascript复制%计算 Tarrival到达时刻, Tservice服务时间
n = 150;
ta = [5 4 3 2 1 0];
pa = [0.05 0.25 0.35 0.10 0.15 0.10];
ts = [ 4 3 2 1 ];
ps = [ 0.15 0.40 0.20 0.25 ];
pacum = cumsum(pa);%递增
pscum = cumsum(ps);
Tarrival = rand(1,n);
for i = 1:length(pa)
Tarrival(Tarrival<pacum(i)) = ta(i);
end
Tarrival = cumsum(Tarrival);%累加才得到到达时刻
Tservice = rand(1,n);
for i = 1:length(ps)
Tservice(Tservice<pscum(i)) = ts(i);
end
Tstart = zeros(1,n); %开始服务的时刻
Tleave = zeros(1,n); %离开的时刻
Twait = zeros(1,n); %等待的时长
line = zeros(1,n); %队长
%初始化第一位顾客
Tstart(1) = Tarrival(1);
Tleave(1) = Tstart(1) Tservice(1);
Twait(1) = Tleave(1) - Tarrival(1) - Tservice(1);
line(1) = 0;
for i = 2:n
Tstart(i) = max(Tleave(i-1), Tarrival(i));
Tleave(i) = Tstart(i) Tservice(i);
Twait(i) = Tleave(i) - Tarrival(i) - Tservice(i);
%队长的计算，一直找到前面的人离开了
k = i-1;
while ( k>0 )&&( Tarrival(i)<Tleave(k) )
line(i) = line(i) 1;
k = k - 1;
end
end
subplot(1,2,1)
hist(Twait)
line
subplot(1,2,2)
hist(line)因为随机数，所以可以多算几次，取平均值。
ICM2017-D: 优化机场安检口旅客通行
问题
- 建立一个或多个模型，研究旅客通过安检口的流量，确定瓶 颈，明确判断当前流程问题区域位置。
- 设计两个或更多对现有系统德潜在改进，提高旅客通信，减 少等待时间。模拟这些变化展示改进如何影响流程。
排队系统: µr = 10, µb = 13, µ1 = 12, µ2 = 9, µ3 = 16
多服务并联
代码语言：javascript复制function [tlea, twat, qlen] = mms(tarr, type, mus)
% MMS Stochastic simulation for M/M/c queue
%
% [tlea, twat, qlen] = mms(tarr, type, mus)
% tarr ：每一个顾客到达的时间
% type ：客户类型参数
% mus ：服务台的服务速度
% tlea ：服务台的离开时间
% twat ：服务台的等待时间
% qlen ：客户的队列长度（排队的长度）
narr = length(tarr); % 客户的个数
nsvr = length(mus); % 服务台的数量
% last time at which a customer left a particular server
last = zeros(nsvr,1);
[tsta, tlea, twat, qlen] = deal(zeros(narr,1));
rndm = zeros(nsvr,narr); % rndm(k,i) = 第i个客户的服务时间
for k = 1:nsvr;
rndm(k,:) = exprnd(mus(k)*type); %生成服从指数分布的随机数
end
for i = 1:narr
% find booth service was/will be emptied soonest and record
[minemp, ksvr(i)] = min(last);
% start time = max{arrival time, minemp}
tsta(i) = max(tarr(i), minemp);
% severe time = exponential random number with mean parameter mu
tsvr(i) = rndm(ksvr(i),i);
% leaving time = start time service time
tlea(i) = tsta(i) tsvr(i);
% last time of k-th server = leaving time of i-th customer
last(ksvr(i)) = tlea(i);
% waiting time = leaving time - arrival time
twat(i) = tlea(i) - tarr(i);
% queue length for i customer
j = i - 1;
while j>0 && tarr(i)<tlea(j)
if ksvr(j)==ksvr(i); qlen(i) = qlen(i) 1; end
j = j - 1;
end
end分别求出A区域两个队列（红色和绿色队列）的离开的时刻，作为下一阶段服务台到达的时刻。
具体使用看下面主程序。
串并混合系统
µr = 10, µb = 13, µ1 = 12, µ2 = 9, µ3 = 16
代码语言：javascript复制n1 = 2; n2 = 3; n3 = 3;% ni表示第i个服务台的数量
mu1 = 12; mu2 = 9; mu3 = 16;% 服务台的到达率
muR = 10; muB = 13;% 蓝色与红色服务台的服务率
nR = ceil(24*3600/muR); nB = ceil(24*3600/muB);% 服务的人数
tArrR = cumsum(exprnd(muR,nR,1));
tArrB = cumsum(exprnd(muB,nB,1)); %到达时刻
tArr = [tArrR; tArrB];
type = [0.8*ones(nR,1); 1.2*ones(nB,1)];%区分两种服务的时长
%A区域
[tLeaR, tWatR, qLenR] = mms(tArrR, ones(nR,1), mu1*ones(n1,1));
[tLeaB, tWatB, qLenB] = mms(tArrB, ones(nB,1), mu2*ones(n2,1));
[tArrG, order] = sort([tLeaR; tLeaB]);%输出为离开A区域的时间，排序进入下一区域
%order数组为排序后的数组在原始数组的位置，保存原来的顺序
%下一区域
[tLeaG, tWatG, qLenG] = mms(tArrG, type(order), mu3*ones(n3,1));
tLeaG(order) = tLeaG;
tWatG(order) = tWatG;
qLenG(order) = qLenG;
figure('position',[50,50,1200,600])
subplot(2,3,1); hist(qLenR); ylabel('Frequency');
xlabel('length of the waiting line'); title('Red')
subplot(2,3,4); hist(tWatR); ylabel('Frequency');
xlabel('waiting time'); title('Red')
subplot(2,3,2); hist(qLenB); ylabel('Frequency');
xlabel('length of the waiting line'); title('Blue')
subplot(2,3,5); hist(tWatB); ylabel('Frequency');
xlabel('waiting time'); title('Blue')
subplot(2,3,3); hist(qLenG); ylabel('Frequency');
xlabel('length of the waiting line'); title('Green')
subplot(2,3,6); hist(tWatG); ylabel('Frequency');
xlabel('waiting time'); title('Green')
发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/167090.html原文链接：https://javaforall.cn
