运筹学课件排队论.ppt

1
排队论及其应用Lecture 5 排队网络
中国科学技术大学
计算机科学与技术学院
田野
什么是排队网络
排队网络包含一组节点,每个节点有若干服务器。单个节点可以被视为一个排队系统。
客户可以在从任何节点进入排队网络。当客户在某个节点排队获得服务以后,它们可以离开网络,也可以去另外的节点,甚至回到原来的节点。
2
一个排队网络有k个节点,节点i(i=1,2,…,k)上有ci个服务器,服务器服务单个客户的时间服从指数分布,平均为1/μi。单个节点可以被视为一个M/M/c/∞排队系统
客户到达是泊松过程,以速率γi到达节点i
当一个客户在节点i的服务器上完成服务,它以概率rij进入节点j;以概率ri0离开排队网络
满足以上3条被称为Jackson网络
对任意i,若γi=0, ri0=0,被称为闭合Jackson网络(没有客户进入和离开)
否则被称为开放Jackson网络
3
闭合Jackson网络例子:
修理工模型,存在两个节点,正常工作和故障修理。i=1,2 j=0,1,2 r12=r21=1 并且其余rij=0。
开放Jackson网络,如果满足则这个排队网络被称为串联(Series)。
客户从第一个节点进入网络
客户依次经历节点1,2,3,...,直到离开网络
4
串联(Series)排队网络
例子:
医院看病:挂号、诊断开药、划价、缴费、拿药
每个节点可以被视为一个M/M/c/∞,前一个节点的输出是下一个节点的输入
5
客户到达节点1服从泊松过程,速率为λ。节点i有ci个服务器,是一个M/M/ci排队系统。
问题:客户从节点离开是怎样一个随机过程?离开时间间隔服从何种分布?
结论:稳态下排队网络节点的离开过程=到达过程。离开时间间隔服从指数分布。
直观解释:“时间倒流”,客户到达和客户离开互换,得到一个完全一样的稳态下的排队网络(队列长度,等待时间等指标均一样)。
6
理论证明
系统中有N(t)=n个客户的概率
T表示客户离开事件的时间间隔(类比于到达时间间隔)
系统中有n个客户,且距离上次客户离开超过t的概率
离开时间间隔分布
7
考虑在时间t+Δt有n个客户的概率
令Δt→∞,有
边界条件
8
求解微分方程,得到
9
离开时间间隔服从指数分布
例子:超市
某超市改进了结帐系统。当所有结帐柜台忙时,顾客获得一个号码并等待,当一个结帐柜台空闲,最小号码的顾客去柜台结帐。超市很大,可以容纳很多顾客。顾客到达超市服从泊松过程,平均每小时到达40位;每位顾客购物平均花费3/4小时,购物时间服从指数分布。每位顾客结帐平均需4分钟,结帐时间也服从指数分布。问:
超市至少需要多少个结帐柜台?
如果设置比最少要求多一个的结帐柜台,求顾客的平均等待结帐时间,平均有多少顾客等待结帐,多少顾客在超市的逗留。
10