queuing-theory

queuing-theory

Charles Lv7
  2023-09-02 19:16:33 2023-09-02 19:16:33 Created   2023-09-02 22:35:46 2023-09-02 22:35:46 Updated      2.6k Words  10 Mins  

排队论

排队论在多本数学建模书籍中均没有提及，但在2019年数学建模国赛c题中被使用。

排队论的基本概念

问题的提出

如果增添服务设备，就要增加投资或可能发生空闲浪费；如果服务设备太少，排队现象就会严重，对顾客甚至对社会都会发生不利影响。因此，管理人员必须考虑如何在这两者之间取得平衡，以提高服务质量，降低成本。

排队论概念

排队论(queuing theory)也称随机服务系统理论，是为研究和解决具有拥挤现象的问题而发展起来的一门应用数学的分支，其研究内容包括三个部分：

  1. 性态问题：即研究各种排队系统的概率规律性，主要是研究队长分布、等待时间分布和忙期分布等，包括了瞬态和稳态两种情形。
  2. 最优化问题
    静态最优 >>最优设计
    动态最优 >>最优运营
  3. 统计推断问题：判断排队系统的类型

排队论模型基本组成

graph RL
A[顾客源].->|"顾客到达(输入)"|B{"队伍(排队规则)"}-->C("服务机构(服务规则)").->|"顾客离开(输出)"|A

style A fill:#F0F0F0,stroke:#333,stroke-width:2px;
style B fill:#FFF,stroke:#333,stroke-width:2px,stroke-dasharray: 5 5;
style C fill:#FFA500,stroke:#333,stroke-width:2px;

subgraph 服务系统 
B
C
end
  • 各个顾客由顾客源（总体）出发，到达服务机构（服务台、服务员）前排队等候接受服务，服务完成后离开。
  • 排队结构指队列的数目和排列方式，排队规则和服务规则是说明顾客在排队系统中按怎样的规则、次序接受服务的。

排队系统的（三大）组成和特征

输入过程
  • 顾客总体：有限，无限。
  • 顾客到达方式：单个，成批。
  • 顾客到达间隔时间：确定的、随机的。
  • 顾客到达的独立性：独立，不独立。
  • 输入过程的平稳性：与时间无关（平稳的），与时间有关（非平稳的）。
排队及排队规则

  • 即时制（损失制）

  • 等待制

    • 先到先服务：FCFS
    • 后到先服务：LCFS
    • 随机服务：SIRO
    • 优先权服务：PR

  • 队容量：有限，无限；有形，无形。

  • 队列数目：单列，多列。

服务机构
  • 服务员数量：无，单个，多个。
  • 队列与服务台的组合
  • 服务方式：单个顾客，成批顾客。
  • 服务时间：确定的，随机的。服务时间和到达间隔时间至少一个是随机的。
  • 服务时间分布是平稳的。

排队论的基本分布

排队论的基本分布基本包含了概率统计的各种分布结构，详细介绍可以见——排队论中的常见分布：泊松分布、指数分布与爱尔朗分布

泊松分布
image-20230902201719545
负指数分布
image-20230902201743501

排队系统的分类

image-20220124144618359

一般可以用6个特征来表示一个排队模型，即X / Y / Z / A / B / C

原则

  • X : 相继到达的间隔时间的分布，一般为负指数分布

  • Y : 服务时间的分布，一般为负指数分布或者确定性

  • Z : 服务台的数目，1台或者多台

  • A : 系统客量的限制，系统中是否存在顾客的最大数量限制

  • B : 顾客源数目，顾客源是否有限

  • C : 服务规则，先到先服务或者后到先服务等

常用符号

M : 负指数分布

D : 确定型

$E_k$ : k阶爱尔朗分布

G : 一般服务时间分布

如标准 M / M / 1 / ∞ / ∞ 模型表示：输入过程服从泊松分布，服务时间服从负指数分布，系统容量无限制且顾客源无限的模型

常用指标

image-20220124151654750

MATLAB代码示例

步骤：
（1）确定问题是否属于排队论领域
（2）确定修理工个数s
（3）确定机器源数m
（4）找到时间终止点T
（5）带入模型即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
function out=MMSmteam(s,m,mu1,mu2,T)
%M/M/S/m排队模型
%s——修理工个数
%m——机器源数
%T——时间终止点
%mu1——机器离开-到达时间服从指数分布
%mu2——修理时间服从指数分布
%事件表：
%  p_s——修理工空闲概率
%   arrive_time——机器到达事件
%   leave_time——机器离开事件
%mintime——事件表中的最近事件
%current_time——当前时间
%L——队长
%tt——时间序列
%LL——队长序列
%c——机器到达时间序列
%b——修理开始时间序列
%e——机器离开时间序列
%a_count——到达机器数
%b_count——修理机器数
%e_count——损失机器数

%初始化

arrive_time=exprnd(mu1,1,m);
arrive_time=sort(arrive_time);
leave_time=[];
current_time=0;
L=0;
LL=[L];
tt=[current_time];
c=[];
b=[];
e=[];
a_count=0;
%循环
while min([arrive_time,leave_time])<T
    current_time=min([arrive_time,leave_time]);
    tt=[tt,current_time];    %记录时间序列
    if current_time==min(arrive_time)      %机器到达子过程
        arrive_time(1)=[];  % 从事件表中抹去机器到达事件
        a_count=a_count+1; %累加到达机器数
        if  L<s            %有空闲修理工
            L=L+1;        %更新队长
            c=[c,current_time];%记录机器到达时间序列
            b=[b,current_time];%记录修理开始时间序列
            leave_time=[leave_time,current_time+exprnd(mu2)];%产生新的机器离开事件
            leave_time=sort(leave_time);%离开事件表排序
        else             %无空闲修理工
            L=L+1;        %更新队长
            c=[c,current_time];%记录机器到达时间序列
        end
    else                   %机器离开子过程
            leave_time(1)=[];%从事件表中抹去机器离开事件
            arrive_time=[arrive_time,current_time+exprnd(mu1)];
            arrive_time=sort(arrive_time);%到达事件表排序
            e=[e,current_time];%记录机器离开时间序列
            if L>s   %有机器等待
                L=L-1;        %更新队长
                b=[b,current_time];%记录修理开始时间序列
                leave_time=[leave_time,current_time+exprnd(mu2)];%产生新的机器离开事件
                leave_time=sort(leave_time);%离开事件表排序
            else    %无机器等待
                L=L-1;        %更新队长
            end
    end
    LL=[LL,L];   %记录队长序列
end
Ws=sum(e-c(1:length(e)))/length(e);
Wq=sum(b-c(1:length(b)))/length(b);
Wb=sum(e-b(1:length(e)))/length(e);
Ls=sum(diff([tt,T]).*LL)/T;
Lq=sum(diff([tt,T]).*max(LL-s,0))/T;
p_s=1.0/(factorial(m)/factorial(m).*(mu2/mu1)^0+factorial(m)/factorial(m-1).*(mu2/mu1)^1+factorial(m-2)/factorial(m-1).*(mu2/mu1)^2+factorial(m)/factorial(m-2).*(mu2/mu1)^2+factorial(m)/factorial(m-4).*(mu2/mu1)^4+factorial(m)/factorial(m-5).*(mu2/mu1)^5);
fprintf('修理工空闲概率:%d\n',p_s)%修理工空闲概率
fprintf('到达机器数:%d\n',a_count)%到达机器数
fprintf('平均逗留时间:%f\n',sum(e-c(1:length(e)))/length(e))%平均逗留时间
fprintf('平均等待时间:%f\n',sum(b-c(1:length(b)))/length(b))%平均等待时间
fprintf('平均修理时间:%f\n',sum(e-b(1:length(e)))/length(e))%平均修理时间
fprintf('平均队长:%f\n',sum(diff([tt,T]).*LL)/T)%平均队长
fprintf('平均等待队长:%f\n',sum(diff([tt,T]).*max(LL-s,0))/T)%平均等待队长
for i=0:m
     p(i+1)=sum((LL==i).*diff([tt,T]))/T;%队长为i的概率
     fprintf('队长为%d的概率:%f\n',i,p(i+1));
end
fprintf('机器不能马上得到修理的概率:%f\n',1-sum(p(1:s)))%机器不能马上得到修理的概率
out=[Ws,Wq,Wb,Ls,Lq,p];


演示代码
clear 
clc 
%***************************************** 
%初始化顾客源 
%***************************************** 
%总仿真时间 
Total_time = 10; 
%队列最大长度 
N = 10000000000; 
%到达率与服务率 
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

2009.1516

%PROGRAMLANGUAGEPROGRAMLANGUAGE
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;
  • Title: queuing-theory
  • Author: Charles
  • Created at : 2023-09-02 19:16:33
  • Updated at : 2023-09-02 22:35:46
  • Link: https://charles2530.github.io/2023/09/02/queuing-theory/
  • License: This work is licensed under CC BY-NC-SA 4.0.
recommend_articles
OO_pre_7 OO_pre_7 Latex_note_5 Latex_note_5 decision-tree decision-tree
recommend_articles
OO_pre_7 OO_pre_7 Latex_note_5 Latex_note_5
Comments
On this page
queuing-theory
  1. 排队论
    1. 排队论的基本概念
      1. 问题的提出
      2. 排队论概念
      3. 排队论模型基本组成
      4. 排队系统的（三大）组成和特征
        1. 输入过程
        2. 排队及排队规则
        3. 服务机构
      5. 排队论的基本分布
        1. 泊松分布
        2. 负指数分布
      6. 排队系统的分类
        1. 原则
        2. 常用符号
      7. 常用指标
    2. MATLAB代码示例