体检排队.doc

基于排队论的体检安排
【摘 要】：
本文采用与排队论相关的数学理论知识，构建体检排队系统的优化模型，实现对受检人员体检排队的定性描述及量化分析，以提高设备利用率、减少受检人员等待时间。本文将排队论的思想和方法应用到体检中心排队的管理中来，建立了相应于体检排队系统的多服务窗等待制M/M/S排队论模型。文章对体检中心的某一科室上4个时间段的实际数据进行收集和整理，代入模型进行实证分析，获得了相应的目标参数，进行了最优服务台数的确定。通过己建立的数学模型，在单位体检时根据各个科室的平均服务时间对部分科室的最优服务台数进行确定，得到每个个体的体检项目、体检顺序及相应时间安排。结论：该算法适用于个人的体检排队安排，同时适用于团体客人的体检排队安排。
【关键词】：排队论 泊松分布 M/M/S排队论 （Dijkstra）算法
一、问题重述
随着社会的发展，人们生活水平的不断提高，提升了人们对自身健康状况的认知。身体是财富的本钱，通过了解自身健康状况来达到预防保健作用已经越来越大。医院健康体检中心人数众多，受检人员往往在诊室门前拥挤排队，导致秩序混乱、效率低下、体检资源浪费、工作强度增加等问题。由此可见，体检中排队等候这一环节的不完善，在很大程度上降低了体检的服务质量和工作效率。
全部体检项目包括：抽血、内科、外科、B超、五官科、胸透、身高、体重、…等等。每个人的体检项目可能各不相同，假设每个体检项目的服务时间是确定的，并且只有1个医生值班，每次只能为1个客户服务。
现要求你们通过数学建模来完成以下任务：
1. 请你为某个新来的客人安排他的体检顺序，使其完成需要的全部检查的时间尽量少（在各个体检项目处都可能有人排队等待）；
2. 设计1组数据来验证上述结论。
3. 接待团体客人时，如何安排每个人的体检顺序，使得体检中心能尽快完成任务，设计1组数据来验证该结论。
二、问题分析
2.1.背景分析
随着计算机网络的发展及普及，计算机已应用到各种各样的行业与领域。目前一般医院都引入了医院管理系软件系统或者体检管理系统来对用户的相关信息进行管理，大大节省了人力物力。
随着人们的健康意识不断增加，体检中心接待的体检人员众多，一般的体检中心一次也可能接待数百人，常常造成体检人员排队秩序混乱，严重影响体检医生的工作环境。排队系统的应用从根本上解决了以上问题，为病人营造了一个公平、公正、公开的医疗环境，降低体检中心指引护士的工作强度，提高各方面的工作效率；而且为体检中心各级管理人员的科学管理提供了依据，最大限度的发挥体检中心的有限资源，产生最好的社会效益与经济效益。
目前，国内已经有上海、北京、广东、浙江等地的多家大医院投入使用了医院排号系统，并且有越来越多的医院认识到了使用排队系统的必要性，医院排队系统出现了良好的发展势头。但就体检中心来说，尚没有将排队理论引入到实际应用中来。
2.2.评价分析
通常医院的采取的各个方案按照大众的顾客考虑的，在排队体检的过程中由于在各个科室体检时间不相等，同时在各个科室个的等待人数比率不同。
给出评价标准是体检的时间最短。

表格 1

抽血
内科
外科
B超
五官科
胸透
身高
体重
时间
2
2
2
12
2
1
1
1
检率
0.95
0.2
0.2
0.7
0.2
1.0
0.5
0.7

三、问题假设
1. 个个体检项目之间相互独立，互不影响；
2. 病人排队体检和体检完毕到下一个科室之间没有时间延迟；
3. 入院体检的顾客单个到达，相继到达时间间隔服从参数为λ的负指数分布；
4. 各个科室可以抽象一个点；
5. 每个服务台的服务时间相互独立，且服从参数为μ的负指数分布；
四、符号说明

N：总共所需体检项目数
i：具体体检的第i项
：第i项体检项目处得排队人数
：第i项体检所需要的时间
：完成第i想体检项目所需要的总时间
S：医院的服务台个数
抽血A1、内科B1、外科C3、B超D4、五官科E5、胸透F6、身高G7、体重H8
和lamuda(i) 表示单位时间平均到达的顾客数, 称为平均到达率
和mu(i) 位时间能被服务完成的顾客数，称为平均服务率
：在ABCDEFGH各个科室检查的时间
:表示在ABCDEFGH各个科室的受检比率
五、模型建立
5.1.泊松流与指数分布
设N(t)表示在时间区间[0,t)内到达的顾客数（t >0），令表示在时间区间 内有n(n≥0)个顾客到达的概率.

当合于下列三个条件时，我们说顾客的到达形成泊松流。这三个条件是：
1.在不相重叠的时间区间内顾客到达数是相互独立的，我们称这性质为无后效
性。
2.对充分小的，在时间区间[t,t +)内有一个顾客到达的概率与t无关，而
约与区间长成正比，即
其中o()，当 →0时，是关于Δt的高阶无穷小。λ > 0是常数，它表示单位时间有一个顾客到达的概率，称为概率强度。
3.对于充分小的，在时间区间[t,t +)内有两个或两个以上顾客到达的概率极小，以致可以忽略，即

在上述条件下，我们研究顾客到达数n的概率分布。
由条件2，我们总可以取时间由0算起，并简记
由条件1和2,有

n=1,2…..
由条件2和3得

因而有

在以上两式中，取趋于零的极限，当假设所涉及的函数可导时，得到以下微分方程组
取初值，容易解出 。
再令 ，可以得到及其它所满足的微分方程组，即

由此容易解得

对于泊松流,表示单位时间平均到达的顾客数,所以1/就表示相继顾客到达平均间隔时间，而这正和的意义相符。
μ表示单位时间能被服务完成的顾客数，称为平均服务率，而1/μ表示一个顾客的平均服务时间。
排队模型 由于个人体检所需时间为定值，排队时间为变量，故某体检者完成体检时间最短等价于其排队等候时问最短。
排队等待时间包括两方面：
① 等待正在检查者完成体检。在第i项体检处若有受检人员已检查分钟，则剩余时间为-；
② 等待前面排队者完成体检。若第i项体检处有人排队，则排队时间为*
因此第i项体检的等待时间为：*+-
则完成第i项体检所需的总时间：
= *+-+
模型建立
根据前面的分析结果，我们可以建立如下模型：
（1） 首先算出每一项体检项目所需的时间，得出min[]，让刚进入医院的顾客A进入该项进行体检。
在A体检的过程中来医院体检的人群：设顾客单个到达，相机到达的时间间隔服从参数为λ的负指数分布。系统中有S个服务台，每个服务台的服务时间相互独立，且服从参数为μ的负指数分布。λ表示单位时间平均到达的顾客数，所以1/λ就表示相继顾客到达的平均时间。μ表示单位时间能能被服务完成的顾客数，称为平均服务率，而1/μ表示一个顾客的平均服务时间。
（2） 在安排A进行体检i项之前，按照统计的方法求出λ，并预计在时间内进入医院的人数，即λ*。每一项体检完成的人数为/，把进来的人数按照（1）的方法进行安排。当A体检完第i项后，根据预计的结果再用（1）的方法进行安排，直到完成全部体检项目为止。
（3） 在建立模型的过程之中，要尽可能准确给出λ和μ的值，使整个与安排能准确的在计算机中完成。
问题二
根据我们体检人员到来情况进行调查研究，对体检人员到来和接受服务时间的数据进行收集、整理和分析。我们得知顾客到来和体检的时间主要集中在上午，下午医务人员对体检结果等相关数据的进行处理。故这里把上午8:00-12:00之间分成4个时间段进行统计，每个时间段随机统计200个单位时间(每个单位时间10分钟)，顾客的到达情况统计整理如表3．1所示。
表3.1顾客到达情况统计表

5以下
5---10
10--15
15--20
20--25
25--30
30--35
35--40
40--45
45--50
8:00-9:00
52
24
10
5
3
1
2
3
1
0
9:00-10:00
28
45
12
6
1
3
2
2
1
2
10:00-11:00
17
42
20
8
5
2
0
2
3
1
11:00-12:00
62
31
5
1
1
0
0
0
0
0

通过对原始数据进行计算，我们可得到体检人员的平均到达率，如表3．2所示。
在该表中，入表示顾客的到达均值。
表3.2体检人员平均到达率
时间段
（人/时）
8:00-9:00
37.5
9:00-10:00
85.8
10:00-11:00
117.2
11:00-12:00
32.1

如表3．2所示，上午8:00-9:00为顾客到达量最少的时候，9:00-10:00体检人员逐渐增加，10:00-11:00达到最高峰，11:00-12:00到达人数回落。这是由于体检中心接受的体检人员大多是由单位来组织体检的，10:00-11:00这个时间段内顾客到来较为方便。
我们以上午8:00-9:00的顾客到达情况进行说明。
下面根据表3．1的数据，我们对单位时间内到达的顾客数是否服从泊松分布进行拟合检验。
首先，我们用极大似然估计法来估计泊松分布中包含的未知参数。设总体X服从泊松分布。首先，我们用极大似然估计法来估计泊松分布中包含的未知参数。设总体X服从泊松分布

则参数入的似然函数为：

两边取对数得：

得似然方程：

解得：

又可算得：

故参数λ的极大似然估计量为：

根据表3．2，顾客的平均到达率为37．5人／小时，故单位时内顾客的平均到达
率：

概率：

其中，与为第n-1个组的下限与上限。理论频数=200，对于理论频数小于5的组进行合并后k=4，但因在计算概率是，估计了一个参数，故r=1，自由度为k-r-1=3，求的值为：

取a=0.05，可得：
，
故认为单位时间内到达的顾客服从参数为的泊松分布。
对于其他各个时间段，我们可以用同样的方法可证明在每一个时间段顾客的到达都是服从泊松分布。
为了研究系统中体检人员接受服务时间的概率分布，在该体检中心的随机调查了200个体检人员接受服务的时间，记录整理如表3．3所示。
表3.3服务时间原始数据
服 务时 间 (m)
1.0— 1.2
1.2— 1.4
1.4— 1.6
1.6— 1.8
1.8— 2.0
2.0— 2.2
2.2— 2.4
2.4— 2.6
2.6— 2.8
2.8— 3.0
3.0— 3.2
3.2— 3.4
3.4以上
频数
6
12
21
44
29
37
59
41
21
15
7
5
3

根据调查的原始数据，顾客的平均服务时间为t=2.29m=132.6s。下面我们使用极大似然估计法来估计理论分布中包含的未知参数µ：
设顾客的服务时间T服从负指数分布

则参数的似然函数为：

两边取对数得：

得似然方程：

解得：
又可算得：

故参数的极大似然估计量为：

根据极大似然估计法，其参数为：

与顾客到达时间一样，进行矛拟合检验，同样可验证：该体验中心排队系统中
体检人员接受服务的时间服从参数为=27.144的负指数分布。
综上，体检排队模型假设成立。
问题三
对于一个团体的客人，要求使整个团体的客人所用时间最少，我们采用0-1规划，假设该团体公有M人，按照仪器充分利用、所用总时间最少的分配原则，设每一个体检项目分配xi人，得到如下的模型：

根据模型，我们用lingo编程求出最优解.

六、模型解答
问题一
根据表格一的数据和实际情况，给出每个科室的λ和μ的表格
表格 2
lamuda1
30
mu1
20
lamuda2
30
mu2
24
lamuda3
30
mu3
25
Lamuda4
5
mu4
3
lamuda5
30
mu5
21
Lamuda6
60
mu6
42
Lamuda7
60
mu7
30
Lamuda8
60
mu8
45
根据表格2的数据，用MATLAB编程得出了抽血科室的到达时间和离开时间的图，和等待时间与停留时间。

根据对抽血科室的时间和表格一的数据处理，通过上面的图可以看出：
当人数呈数据流的泊松分布，与现实相符。

问题二
把每个科室抽象成一个点，时间与检比的积根当做权重。
据迪克斯特拉（Dijkstra）算法，其基本思想是按距 从近到远为顺序，依次求得A到G 的各顶点的最短路和距离，直至（或直至G 的所有
顶点），算法结束。为避免重复并保留每一步的计算信息，采用了标号算法
（i）令，对，令
（ii）对每个

计算把达到这个最小值的一个顶点记为，令

（iii）.若i=|V|-1,停止。
若i<|V|-1,用i+1代替i，转（ii）。
算法结束后，可以知道遍历的最短路径。
通过数据的处理：
网络优化研究的是网络上的各种优化模型与算法。为了在计算机上实现网络优化的算法，首先我们必须有一种方法（即数据结构）在计算机上来描述图与网络。一般来说，算法的好坏与网络的具体表示方法，以及中间结果的操作方案是有关系的。这里我们介绍计算机上用来描述图与网络的5 种常用表示方法：邻接矩阵表示法、关联矩阵表示法、弧表表示法、邻接表表示法和星形表示法 ，在下面数据结构的讨论中，我们首先假设G=（V，A）是一个简单有向图。m，并假设V 中的顶点用自然数1,2,L,n表示或编号， A中的弧用自然数1,2,L,m表示或编号。对于有多重边或无向网络的情
况，我们只是在讨论完简单有向图的表示方法之后，给出一些说明。
邻接矩阵表示法是将图以邻接矩阵（adjacency matrix）的形式存储在计算机中。G=（V，A）的邻接矩阵是如下定义：

也就是说，如果两节点之间有一条弧，则邻接矩阵中对应的元素为 1；否则为0。
可以看出，这种表示法非常简单、直接。但是，在邻接矩阵的所有个元素中，只有m个为非零元。如果网络比较稀疏，这种表示法浪费大量的存储空间，从而增加了在网络中查找弧的时间。
对于上述的问题，可以分别在A、B、C、D、E、F、G、H等各个体检项目抽象成一个点，边权近似等于时间和受检比率的内积。可以得到邻接矩阵:

A
B
C
D
E
F
G
H
A
0
1.5
1.5
7.7
1.5
0.5
1.4
1.2
B

0
0
8
0
0.6
0.1
0.3
C

0
8
0
0.6
0.1
0.3
D

0
8
7.4
7.9
7.7
E

0
0.6
0.1
0.3
F

0
0.5
0.3
G

0
0.2
H

0
同样，对于网络中的权，也可以用类似邻接矩阵的n × n 矩阵表示。只是此时一条弧所对应的元素不再是1，而是相应的权而已。如果网络中每条弧赋有多种权，则可以用多个矩阵表示这些权。用矩阵An × n来存放各边权的邻接矩阵，行向量pb,index1，index2，d分别表示存放P 标号信息、标号顶点顺序、标号顶点索引、最短通路的值。其中分量

index2(i)存放始点到第i各点最短路径的第i个顶点的序号
d(i):存放由始点到i个点的最短路径。

问题三
根据0-1规划，我们用lingo编写程序如下：
model:
sets:
pt/1..8/:k,t,x;
endsets
data:
t=2,2,2,12,2,1,1,1;
k=5,7,3,4,2,6,3,3;
enddata
min=@sum(pt(i):t(i)*k(i)+x(i)*t(i));
@sum(pt(i):x(i))=100;
x(i)>=0;
x(i)<=100;
end
得到的最优解：
=17 =13 =15 =12 =18 =15 =11 =19
七、模型评价与推广
本文上述结果表明利用计算机模拟完全有能力完成对多人、多项体检项目的分析，并做出仅需等待最短时间的最优安排；同时兼顾提高设备利用率，使得各项体检设备都得以发挥其最大效用。对此不仅能够定性分析，而且作出了定量安排，故而是切实可行的，值得在临床实践中推广应用。尤其在医院排队挂号、就诊，战时大批量伤病员的救治排队等方面具备一定优越性，藉此可以合理利用资源 。在此基础上，对本算法进一步优化，可以考虑团队体检时如何排队，建立以所有受检人员完成检查的总时间最短为目标函数、各体检者的等待时间最短为约束条件的非线性规划模型，探讨团体体检排队的最优方案将是下一步研究方向。
参考文献
【1】马琳．疗养院体健中心动态排队系统[J]．中国数字医学，
2007，1(1)：23—25．
【2】刘京梅．科学的组织管理运用于大批量人员体检工作中
[J]．中原医刊，2004，lo(2o)：56．
【3】茆诗松．统计手册[M]．北京：科学出版社，2003
【4】陈庆宏．排队论在生产过程时间组织中的应用闭．北方经贸，2003(11)：92．93
【5】于志青．排队论在交通工程中的应用研究[J】．中州大学学报，2005，22(1)：
118．119
【6】张维中．排队论在确定集装箱码头吞吐能力中的应用【J】．海岸工程，1998，
17(1)： 67-7l
【7]樊相宇．电话交费窗口用户排队分析【J】．西安邮电学院学报，2003，5(1)：
48-5l
【8】熊桂武．M／M／n系统在学校科学管理中的应用们．长春师范学院学报，
2004，23(1)：31．33
【9】杨灿，卢正鼎．基于排队模型的视频点播系统设计与分析叨．电视技术，
2004(5)：34．36
【10】王勇，孙薇，李道华．排队管理系统在银行管理中的应用阴．黑龙江大学自然科学学报，2004，23(2)：156．158

附录：程序代码：
clear
clc
%*****************************************
%初始化顾客源
%*****************************************
%总仿真时间
Total_time = 10;
%队列最大长度
N = 10000000000;
%到达率与服务率
lambda =30;
mu =20;
%平均到达时间与平均服务时间
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
%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;
其余的图改一下lamuda和mu值。
程序2：
clear;clc;
n=8; a=zeros(n);
a(1,2)=1.5;a(1,3)=1.5;a(1,4)=7.7;a(1,5)=1.5;a(1,6)=0.5;
a(1,7)=1.4;a(1,8)=1.2;a(2,4)=8;a(2,6)=0.6;a(2,7)=0.1;a(2,8)=0.3;
a(3,4)=8;a(3,6)=0.6;a(3,7)=0.1;a(3,8)=0.3;a(4,5)=8;a(4,6)=7.4;
a(4,7)=7.9;a(4,8)=7.7;a(5,6)=0.6;a(5,7)=0.1;a(5,8)=0.3;
a(6,7)=0.5;a(6,8)=0.3;a(7,8)=0.2

a=a+a'; M=max(max(a))*n^2; %M为充分大的正实数
a=a+((a==0)-eye(n))*M;
path=zeros(n);
for k=1:n
for i=1:n
for j=1:n
if a(i,j)>a(i,k)+a(k,j)
a(i,j)=a(i,k)+a(k,j);
path(i,j)=k;
end
end
end
end
a, path model:
sets:
pt/1..8/:k,t,x;
endsets
data:
t=2,2,2,12,2,1,1,1;
k=5,7,3,4,2,6,3,3;
enddata
min=@sum(pt(i):t(i)*k(i)+x(i)*t(i));
@sum(pt(i):x(i))=100;
x(i)>=0;
x(i)<=100;
end

副本图：内科

其余的改变lamudah和mu值。