《运筹学 第2版 教学课件 ppt 作者 沈荣芳 第十三章 排 队 论》由会员分享，可在线阅读，更多相关《运筹学 第2版 教学课件 ppt 作者 沈荣芳 第十三章 排 队 论（28页珍藏版）》请在金锄头文库上搜索。
1、第十三章 排 队 论,第一节 排队论的基本概念 第二节 单服务台系统 第三节 多服务台系统,第一节 排队论的基本概念,一、输入过程 二、排队规则 三、服务机构 四、常用符号 五、主要的数量指标,一、输入过程,1.泊松流(记为M) 2.定长输入(记为D) 3. k阶爱尔郎输入(记为Ek) 4.一般独立输入(记为GI),1.泊松流(记为M),2.定长输入(记为D),流水线上定时送往包装机的成品，其输入过程就是定长输入。如果规定的产品到达的间隔时间为c，则相继到达产品间隔时间t的分布函数为 A (t)=P ( t l )=0，tc1，t c,3. k阶爱尔郎输入(记为Ek),相继到达顾客的间隔时间t
2、的分布为k阶爱尔郎分布，其密度函数为 A (t)=( t)(k-1)!e- t， t0(0) 服从爱尔郎分布的随机变量t=t1+t2+t k，每个t i都是服从参数为的负指数分布随机变量，且t1，t2，t k是相互独立的。,4.一般独立输入(记为GI),如果各相继到达顾客的间隔时间t1，t2，是相互独立的同分布的随机变量，那么称为一般独立输入。,二、排队规则,1.等待制 2.消失制 3.混合制,1.等待制,顾客到达后，如果服务机构已经占满，当允许顾客等待时，再到的顾客便排队等待。常见的有以下几种排队方式： (1)先到先服务 这是最普遍的情形。 (2)后到先服务 许多存储系统中运用这种规则。 (
3、3)随机服务 当一名顾客接受服务完毕离去时，随机地从等候的顾客中选择一名进行服务。 (4)优先服务 对于不同的顾客规定不同的优先权，具备较高优先权的顾客优先接受服务。,2.消失制,当服务机构已全部占满时，再到的顾客不能进入服务系统，顾客自动消失，也就是不允许排队的情形。例如当旅店客满时，再来的顾客只好离去。对于消失制的情形，不存在排队现象。主要考虑的是顾客消失的概率和服务机构的利用率。,3.混合制,等待制的排队方式可以认为排队的队伍长度没有限制。当允许排队、但服务机构的空间和排队时间有限时，队伍长度必然有一定的限制，这种情形称为混合制。,三、服务机构,服务机构中可能是单服务台，例如只有一名医生
4、的诊室，也可能是多服务台，例如有c个理发师的理发店等。当有多个服务台时，排队的顾客可以排成一个队，依次到空出的服务台去接受服务。例如在有2名医生的诊室外候诊的病人，依次到医生那里就诊；也可以每个服务台前排成一队，且一旦排好后，不再更换，例如排队买饭的窗口。本章首先讨论单服务台的情形。由于顾客的情况不同，服务所需要的时间(称为服务时间)T也不同，例如出现故障的机器，损坏的情况不同，排除故障所需要的时间也不同。,四、常用符号,通常用记号1/2/3/4来表示一个排队系统。 1表示输入的类型。 2表示服务时间T的分布类型，例如M表示T服从负指数分布。 3表示服务机构中的服务台数。 4表示服务机构的容量
5、。,五、主要的数量指标,1.队伍长度 2.逗留时间w和等待时间wq的分布 3.服务台的利用率 4.顾客损失率,1.队伍长度,在排队系统中的平均顾客数，称为队伍长度，简称队长，这是顾客和设计人员都关心的问题。队长的大小直接关系到顾客的利益，也关系到服务机构的利用率。,2.逗留时间w和等待时间wq的分布,这是顾客最关心的指标，但各个顾客关心的角度不同。例如就诊的病人对等待时间比较关心，对诊断时间却不希望太快。,3.服务台的利用率,服务台工作的时间占总时间的比例，可以衡量服务台的劳动强度及服务成本的大小。这是服务部门所关心的。,4.顾客损失率,对于消失制和混合制的排队系统，必须考虑因服务能力不足导致
6、顾客消失的比例，因为这直接关系到经济效益。,第二节 单服务台系统,一、概述 二、机器看管问题,一、概述,服务机构只有一个服务台的排队系统称为单服务台系统。当输入过程是泊松流，服务时间服从负指数分布，单服务台时，排队系统记为M/M/1/+，是最基本的排队模型。,二、机器看管问题,例3 某工人负责6台刨床的更换加工产品的工作。当一台刨床加工的工件达到合乎规格时，将自动停机，由工人更换工件，然后再重新启动。已知一个工件的加工时间服从负指数分布，平均1h加工完1个，更换1个工件的时间也服从负指数分布，平均每个需要6min，求有关数量指标。,二、机器看管问题,第三节 多服务台系统,一、M/M/c/+模型
7、 二、多服务台的机器看管问题,一、M/M/c/+模型,1.系统状态的概率 2.几种主要数量指标,1.系统状态的概率,当系统中顾客数Nc时，这N个顾客都是正在接受服务，在时间 t内，1个顾客离去的概率为N ( t)；当N c时，在时间 t内，1个顾客离去的概率为c ( t)。两个和两个以上的顾客离去的概率为o ( t)。,2.几种主要数量指标,(1)队长 (2)排队长度 (3)平均逗留时间 (4)平均等待时间,二、多服务台的机器看管问题,例5 某港有2个泊位用作装卸矿砂，共有5艘船进行专线循环运输。每天24h每艘船到达1次。每个泊位平均每天可卸4艘船。设船的到达是泊松流，卸船时间服从负指数分布。求该问题的数量指标。,二、多服务台的机器看管问题,
