[分享]排队问题

zhimaoyong · 发表于 2005-9-11 03:28:42

<

>function[maxque,mwait_t,mstay_t,queue_l,use_rate]=MM1queue(mean_arr,mean_lea,peo_num)
<

>status=zeros(3,peo_num);
<

> %用一个3行矩阵表示每个顾客的状态;
 %到达时间间隔，服务时间，等待时间;
status(1,

=exprnd(mean_arr,1,peo_num);
 %随机生成各顾客的到达间隔;
status(2,

=exprnd(mean_lea,1,peo_num);
 %随机生成各顾客的服务时间;
 
 
for i=2:peo_num
 if status(1,i)<=status(2,i-1)+status(3,i-1)
 status(3,i)=status(2,i-1)+status(3,i-1)-status(1,i);
 else
 status(3,i)=0;
 end;
 %对状态进行更新；
end;
 
 
arr_time=cumsum(status(1,

);
status(1,:)=arr_time;
lea_time=sum(status);
stairs([0 arr_time],0:peo_num);
 %绘出各顾客的到达时间图;
 
hold on;
stairs([0 lea_time],0:peo_num,'r');
 %绘出各顾客的离去时间图;
 
legend('Arrive curve','leave curve',0)
hold off
figure;
plot(1:peo_num,status(3,:),'r:',1:peo_num,status(2,:)+status(3,:),'k-');
 %绘出每个顾客的等待时间和停留时间;
 
legend('Wait Time','Stay Time',0);
n1=1;
n2=1;
mstay_t=(sum(status(2,:))+sum(status(3,:)))/peo_num;
mwait_t=mean(status(3,:));
 %求平均停留时间和等待时间;
queue_num=zeros(1,2*peo_num+1);
queue_time=zeros(1,2*peo_num+1);
n3=1;
 %while循环求每个时间队列的长度;
while n1<=peo_num
 n3=n3+1;
 if arr_time(n1)<lea_time(n2)
 queue_num(1,n3)=n1-n2+1;
 queue_time(1,n3)=arr_time(n1);
 n1=n1+1;
 else
 queue_num(1,n3)=n1-n2-1;
 queue_time(1,n3)=lea_time(n2);
 n2=n2+1;
 end;
end;
while n2<=peo_num
 n3=n3+1;
 queue_num(1,n3)=peo_num-n2;
 queue_time(1,n3)=lea_time(n2);
 n2=n2+1;
end;
figure;
stairs(queue_time,queue_num,'k');
 %绘出队列长度的时间变化曲线, stairs 是Matlab的函数
 
legend('Queue Length Curve',0);
hold off;
temp=diff(queue_time);
overtime=max(queue_time);
queue_l=sum(temp.*queue_num(2

2*peo_num+1)))/overtime;
use_rate=sum(temp(find(queue_num)))/overtime;
maxque=max(queue_num); % 最大队长
 
%然后在Matlab命令窗口中输入命令即可，如：[maxque,mwait_t,mstay_t,queue_l,use_rate]=mm1queue(0.5,0.4,200)，其中0.5表示平均来到时间间隔，
%0.4表示平均离开时间，200为人数
注意以下几点：
1． 首先因为M/M/1中，各个实体的到达时间和服务时间相互独立，所以才能首先把每个实体的这两个时间，根据所给的参数产生模拟的随机数来。而在Matlab中，产生指数分布的随机数的参数是平均时间，而非到达率，这一点需要注意。
2． 确定排队系统状态的程序很简单，只有很短的一部分，程序的后面几块主要是计算该排队系统的队长随时间的变化情况，平均队长和占用率。
计算某时刻的队长的基本思想是用在此时刻前到达的总实体数，减去
3． 在此时刻前结束服务的实体数，然后不难求出平均队长和占用率。
在实体数很大的情况下，计算机仿真的结果和理论推导的结果很接近，这也说明了理论推导结果的正确性。
关于排队论的的一些知识
排队系统主要有：X/Y/Z，其中X表示到达时间间隔的分布，Y表示服务时间的分布，Z表示并列的服务设备的数目。表示相继到达的时间间隔或服务时间的分布的符号是：
M——负指数分布，D——确定性，Ek——k阶Erlang，GI——相互独立的一般随机分布，G——一般的随机分布。
例如：M/M/1表示达到时间间隔为负指数分布，服务时间为负指数分布，单服务设备的排队系统。
这里我们用静态仿真的思想来实现M/M/1仿真。
在排队系统中的每一个动态实体的状态可以有三个量来反映：与前一个实体到达的时间间隔，在排到自己服务前的等待时间以及服务时间。其中服务时间和到达时间间隔服从指数分布，不受别的因素的影响。开始服务前的等待时间则受到排在前面的动态实体的状态的影响。其更新算法如下：
即：如果某个实体到达以后，发现处在它前面的动态实体已经结束服务，所以这个实体就不用等待，直接接受服务；反之，处在它前面的动态实体如果没有结束服务（包括没有开始服务），则这个实体的等待时间就是它前一实体结束服务的时刻减去它到达的时刻。
即：
if arr_time(i)<=arr_time(i-1)+wait_time(i-1)+sever_time(i-1) 
%第i个实体到达时刻和第i-1个实体的离开时刻相比较，
then wait_time(i)= wait_time(i-1)+ sever_time(i-1)+ arr_time(i-1)- arr_time(i);
else wait_time(i)=0;
也就是：
if arr_interval(i) <= wait_time(i-1)+sever_time(i-1)
then wait_time(i)= wait_time(i-1)+ sever_time(i-1)- arr_interval(i);
else wait_time(i)=0;
其中：arr_interval(i)= arr_time(i)- arr_time(i-1); 
arr_time(i-1)+wait_time(i-1)+sever_time(i-1) 表示第i-1个实体的离开时刻。
程序中关于队长求法的解释如下：
我们要求木某一时刻的队长，那要看这个因素；第一个因素是在该时刻正在接受服务的实体（排在最前面的实体）和该时刻到达的人（即此刻排在队尾的人），此时队长很容易求出。第一个排在最前面的实体也就是第一个到达的实体n2=1，此时如果要求在某一时刻的队长，后来的人的到达时间arr_time(n1)要和lea_time(n2) 相比较 （注意：n1从1开始到总实体数），相应的可以计算出某时刻的队长，同时排在最前面的实体也在变化(n2=n2+1)；由于总实体数目一定，因此当n2到某一数值时，将不会再有人到达，此时影响队长的就是排在最前面的人的离开了，因此也可以把队长求出来；总之我们可以把队长得到，详细的实现步骤请看程序中的相应的部分。
严庆强的新程序
仿真程序
 
function[mwait_t,vmwait_t]=mvqueue(mean_arr,mean_lea,r,m,peo_num)
status=zeros(6,peo_num);
status(1,:)=exprnd(mean_arr,1,peo_num);
status(2,:)=exprnd(mean_arr,1,peo_num);
status(4,1)=status(2,1);
for i=2:peo_num
 if status (1,i)<=status(2,i-1)+status(3,i-1)
 status(3,i)=status(2,i-1)+status(3,i-1)-status(1,i);
 else
 status(3,i)=0;
 end;
 status(4,i)=status(2,i)+status(2,i-1)-status(1,i);
 if status(4,i)<=m
 status(5,i)=status(4,i);
 else
 status(5,i)=status(4,i)/r+m*(1-1/r);
 end;
 if status(1,i)<=status(5,i-1)
 status(6,i)=status(5,i-1)-status(1,i);
 else 
 status(6,i)=0;
 end;
end;
arr_time=cumsum(status(1,:));
status(1,:)=arr_time;
lea_time=sum(status);
figure;
plot(1:peo_num,status(3,:),'r:',1:peo_num,status(6,:),'k-');
legend('Wait Time','V-wait time',0);
hold off;
mwait_t=mean(status(3,:));
vmwait_t=mean(status(6,:));

mofen · 发表于 2005-9-14 04:41:58

非常感谢

ruanshijian · 发表于 2008-6-25 11:33:35

排队问题，服务台变为3个，程序要怎么变化。着急

默默鱼 · 发表于 2009-9-17 11:30:07

谢谢分享

		自动登录	找回密码
密码			注-册-帐-号