排队论-四川大学课程中心

11.排队论11.1基本概念排队现象是指到达服务机构的顾客数量超过服务机构提供服务的容量,也就是说顾客不能够立即得到服务而产生的等待现象。

顾客可以是人,也可以是物,比如说,在银行营业部办理存取款的储户,在汽车修理厂等待修理的车辆,在流水线上等待下一到工序加工的半成品,机场厂上空等待降落的飞机,以及等待服务器处理的网页等,都被认为是顾客。

服务机构可以是个人,像理发员和美容师,也可以是若干人,像医院的手术小组。

服务机构也还可以是包装糖果的机器,机场的跑道,十字路口的红绿灯,以及提供网页查询的服务器等等。

11因为顾客到达,服务时间具有不确定性,排队系统又称随机服务系统,它的基本结构如图1.所示:商业服务理发店,银行柜台,机场办理登机手续的柜台,快餐店的点餐柜台运输行业城市道路的红绿灯,等待降落或起飞的飞机,出租车制造业待修理的机器,待加工的材料,生产流水线社会服务法庭,医疗机构为了描述一个排队系统,我们需要说明输入(到达)和输出(服务)过程,及其他基本特征。

表2.11列举了一些排队系统的到达和服务过程。

表11.2: 排队系统举例)1(到达过程通常,我们假设顾客的相继到达间隔时间是相互独立并且都具有相同概率分布。

在许多实际(Poisson流,或指数分布。

顾客源可能是有限的,也可情况中,顾客的相继到达间隔是服从泊松)能是无限的。

顾客到来方式可能是一个接一个的,也可能是批量的。

比如,到达机场海关的旅行团就是成批顾客。

一般来说,我们假设到达过程不受排队系统中顾客数量的影响。

以银行为例,无论银行内有3位顾客还是300位顾客,顾客来到银行的到达过程是不会受到影响的。

但是在两种情况下到达过程与排队系统中的顾客数量相关。

第一种情况发生在顾客源是有限的系统,比如某工厂共有五台机床,若在维修部中已有两台机床,接下来到达维修部的最大量是三台。

另一种情况是当顾客到达排队系统时,如果服务机构的设施都被占用,顾客可能耐心等待,也可能选择离开。

排队是在日常生活中经常遇到的现象，如顾客到商店购买物品、病人到医 院看病常常要排队。

此时要求服务的数量超过服务机构（服务台、服务员等） 的容量，也就是说，到达的顾客不能立即得到服务，因而出现了排队现象。

这 种现象不仅在个人日常生活中出现，电话局的占线问题，车站、码头等交通枢 纽的车船堵塞和疏导，故障机器的停机待修，水库的存贮调节等都是有形或无 形的排队现象。

由于顾客到达和服务时间的随机性，可以说排队现象几乎是不 可避免的。

如果增添服务设备，就要增加投资或发生空闲浪费；如果服务设备太少， 排队现象就会严重，对顾客个人和对社会都会带来不利影响。

因此，管理人员 必须考虑如何在这两者之间取得平衡，经常检查目前处理是否得当，研究今后 改进对策，以期提高服务质量，降低成本。

排队论（Queueing Theory ）也称随机服务系统理论，就是为解决上述问题 而发展的一门学科，它研究的内容有下列三部分：（ 1）性态问题，即研究各种排队系统的概率规律性， 主要是研究队长分布、 等待时间分布和忙期分布等，包括了瞬态和稳态两种情形。

（ 2）最优化问题， 又分静态最优和动态最优， 前者指最优设计，后者指现 有排队系统的最优运营。

（ 3）排队系统的统计推断，即判断一个给定的排队系统符合于那种模型， 以便根据排队理论进行分析研究。

这里将介绍排队论的一些基本知识，绍排队系统的最优化问题。

排队论一、排队过程的一般表示图 12-1 就是排队过程的一般模型。

各个顾客由顾客源（总体）出发，到达 服务机构（服务台、服务员）前排队等候接受服务，服务完了后就离开。

排队结构指队列的数目和排列方式，排队规则和服务规则是说明顾客在排队系统中 按怎分析几个常见的排队模型，最后将介第一节 基本概念样的规则、次序接受服务的。

我们所说的排队系统就指图中虚线所包括的部分。

在现实中的排队现象是多种多样的，对上面所说的“顾客”和“服务员”，要作广泛地理解，它现可以是人，也可以是非生物；队列可以是具体地排列，也可以是无形的（例如向电话交换台要求通话的呼唤）；顾客可以走向服务机构，也可以相反（如送货上门）。

退出前一页后一页前一页后一页退出退出前一页后一页前一页后一页退出退出前一页后一页前一页后一页退出退出前一页后一页前一页后一页退出退出前一页后一页前一页后一页退出退出前一页后一页前一页后一页退出退出前一页后一页前一页后一页退出退出前一页后一页前一页后一页退出退出前一页后一页前一页后一页退出退出前一页后一页前一页后一页退出退出前一页后一页前一页后一页退出退出前一页后一页前一页后一页退出退出前一页后一页退出前一页后一页退出前一页后一页退出前一页后一页退出前一页后一页随机服务系统理论与展望退出前一页后一页随机服务系统理论与展望退出前一页后一页随机服务系统理论与展望退出前一页后一页随机服务系统理论与展望退出前一页后一页退出前一页后一页退出前一页后一页随机服务系统理论与展望退出前一页后一页随机服务系统理论与展望退出前一页后一页随机服务系统理论与展望退出前一页后一页随机服务系统理论与展望退出前一页后一页退出前一页后一页退出前一页后一页随机服务系统理论与展望退出前一页后一页随机服务系统理论与展望退出前一页后一页随机服务系统理论与展望退出前一页后一页随机服务系统理论与展望退出前一页后一页退出前一页后一页退出前一页后一页随机服务系统理论与展望退出前一页后一页随机服务系统理论与展望随机服务系统理论与展望退出前一页后一页。

第七章排队论Chapter 7Queuing Theory§7.1 排队的基本概念7.1.1 顾客、服务台、服务先举一些排队系统的例子。

排队的过程可表示为：队列服务台顾客到达进入队列接受服务顾客离去7.1.2 排队系统的分类7.1.2.1、按顾客到达的类型分类(1)按顾客源顾客的数量，可分为有限顾客源和无限顾客源；(2)按顾客到达的形式，可分为单个到达和成批到达；(3)按顾客相继到达的时间间隔分布，可分为定长分布和负指数分布；7.1.2.2、按排队规则分类(1)等待制：顾客到达后，一直等到服务完毕以后才离去；(2)损失制：到达的顾客有一部分未接受服务就离去；例如：*队列容量有限的系统。

设队列容量为L0，顾客到达时的队长为L。

若L<L0，则顾客进入队列等待服务，若L=L0，则顾客离去。

*顾客对等待时间具有不耐烦性的系统。

设最长等待时间是W0，某个顾客从进入队列后的等待时间为W。

若W<W0，顾客继续等待；若W=W0，则顾客脱离队列而离去。

7.2.1.3、按服务规则分类(1)先到先服务（FCFS，First Come First Serve）；(2)后到先服务（LCFS，Last Come First Serve）；(3)有优先权的服务（PR，Priority）(4)随机服务（SIRO，Service in Random Order）7.1.2.4、根据服务台的数量及排队方式，排队系统可以分为(1)单服务台单队(2)多服务台单队(3)多队多服务台(4)多服务台串联服务7.1.3 排队论中常用的记号及各类排队系统的符号7.1.3.1、排队论中常用的记号n ––系统中的顾客数；λ––顾客到达的平均速率，即单位时间内平均到达的顾客数；μ––平均服务速率，即单位时间内服务完毕离去的顾客数；P n(t) ––时刻t系统中有n个顾客的概率；c ––服务台的个数；M ––顾客相继到达的时间间隔服从负指数分布；D ––顾客相继到达的时间间隔服从定长分布；E k––顾客相继到达的时间间隔服从k阶Erlang分布。

排队论（2005）某储存所只有一个出纳员，顾客以平均速度为4人/小时的poisson流到达，所有的顾客排成一队。

出纳员与顾客的交易时间服从平均数为10分钟的负指数分布，试求：（1）银行内空闲时间的概率P0；（2）平均队列长LQ；（3）银行内的顾客平均数L；（4）在银行内的平均逗留时间WS；（5）等待服务的平均时间WQ；（2007）考虑M/M/s模型，设其服务者数为1，期望服务时间恰为1分钟。

就顾客平均到达率分别为0.5和0.9分别计算L、LQ、W、WQ与P{w>5}。

（2009）某修理站只有一个修理工，且站内最多多只能停放2台机器。

设待修机器按POISSON流到达休息站，平均每分钟到达1台；修理时间服从负指数分布，平均每1.25分钟可修理1台。

试求该系统有关的数量指标：顾客损失率、有效到达率、平均队长、平均排队长、平均逗留时间、平均等待时间。

（2010）某工厂有一个半成品加工操作间，内设一个半成品加工操作台和可存放3个待加工半成品的场地。

已知半成品按平均每3个的泊松过程到达该操作间，而完成该半成品加工的必要时间服从平均每个需0.25天的负指数分布。

若半成品到达操作间时操作间内已没有场地存放，则需要运行到其他地方。

试求：（1）任一半成品期望等候时间；（2）需运往其他地方的半成品占到达操作间的半成品总数的比例是多少？（2012）某理发店只有一个理发师，顾客到达过程为POISSON流，平均每小时3人，理发时间服从负指数分布，平均需要10分钟，求：（1）店内空闲的概率；（2）至少有一个顾客的概率；（3）店内顾客的平均数；（4）等待服务的顾客数；（5）平均等待理发的时间；（6）一个顾客在店内逗留时间超过15分钟的概率。

（2013）某修理店只有一个修理工人，来修理的顾客到达次数服从POISSON分布，平均每小时3人，修理时间服从负指数分布，平均需10分钟，求：（1）修理店空闲的概率；（2）店内有4个顾客的概率；（3）店内至少有一个顾客的概率；（4）在店内顾客平均数；（5）等待服务的顾客平均数；（6）在店内平均逗留时间；（7）平均等待修理时间；（8）必须在店内消耗15分钟以上的概率。

四川大学2015-2016学年第二学期课程考试试卷答案(A卷)课程名称：运筹学考试时间：120分钟年级：xxx级专业：xxx题目部分，（卷面共有85题，0分，各大题标有题量和总分）一、判断（20小题，共0分）1、在顾客到达及机构服务时间的分布相同的情况下，对容量有限的排队系统，顾客的平均等待时间少于允许队长无限的系统。

( )答案：对2、若两两顾客依次到达的间隔时间服从负指数分布，又将顾客按到达先后排序，则第1、3、5、7、…名顾客到达的间隔时间也服从负指数分布。

( )答案：错3、一个排队系统中，不管顾客到达和服务时间的情况如何，只要运行足够长的时间后，系统将进入稳定状态；（）答案：错4、若两两顾客依次到达的间隔时间服从负指数分布，又将顾客按到达先后排序，则第1,3，5，7，…名顾客到达的间隔时间也服从负指数分布；（）答案：错5、在顾客到达及机构服务时间的分布相同的情况下，对容量有限的排队系统，顾客的平均等待时间将少于允许队长无限的系统；（）答案：对6、假如到达排队系统的顾客来自两个方面，分别服从泊松分布，则这两部分顾客合起来的顾客流仍为泊松分布。

( )答案：对7、在顾客到达的分布相同的情况下，顾客的平均等待时间同服务时间分布的方差大小有关，当服务时间分布的方差越大时，顾客的平均等待时间将越长；（）答案：对8、在机器发生故障的概率及工人修复一台机器的时间分布不变的条件下，由1名工人看管5台机器，或由3名工人联合看管15台机器时，机器因故障等待工人维修的平均时间不变。

( )答案：错9、假如到达排队系统的顾客来自两个方面，分别服从普阿松分布，则这两部分顾客合起来的顾客流仍为普阿松分布；（）答案：对10、在顾客到达分布相同的情况下，顾客的平均等待时间同服务时间分布的方差大小有关，当服务时间分布的方差越大时，顾客的平均等待时间就越长。

( )答案：对11、在排队系统中，一般假定对顾客服务时间的分布为负指数分布，这是因为通过对大量实际系统的统计研究，这样的假定比较合理；（ ） 答案：错12、若到达排队系统的顾客为普阿松流，则依次到达的两名顾客之间的间隔时间服从负指数分布；（ ） 答案：对13、在机器发生故障的概率及工人修复一台机器的时间分布不变的条件下，由1名工人看管5台机器，或由3名工人联合看管15台机器时，机器因故障等待工人维修的平均时间不变。