浅谈排队论方法

1、L/O/G/O排队论方法排队论方法江西中医药大学计算机学院 数理学科组 周 丽2014-8-一般的排队过程为：顾客由顾客源出发一般的排队过程为：顾客由顾客源出发，到达服务机构前，按排队规则排队，到达服务机构前，按排队规则排队，等待服务，服务机构按服务规则给顾客等待服务，服务机构按服务规则给顾客服务，顾客接受完服务后就离开服务，顾客接受完服务后就离开。 顾客源顾客源顾客到来顾客到来输入输入顾客离去顾客离去输出输出顾客源顾客源队伍队伍服务机构服务机构排队规则排队规则服务规则服务规则随机服务系统随机服务系统排队论又称随机服务系统理论，是通过排队论又称随机服务系统理论，是通过研究各种服务系统等待现象中

2、的概率特研究各种服务系统等待现象中的概率特征，从而解决服务系统最优设计与最优征，从而解决服务系统最优设计与最优控制的一种理论。控制的一种理论。 输入过程输入过程 排队规则排队规则 服务机构服务机构 123决定排队系统进程的基本组成部分决定排队系统进程的基本组成部分 输入过程输入过程：1（1 1）顾客源中顾客的数量。）顾客源中顾客的数量。例如，工厂内发生故障待修的机器是有限的；到例如，工厂内发生故障待修的机器是有限的；到达窗口购票的顾客源总体可以看成是无限的。达窗口购票的顾客源总体可以看成是无限的。（2 2）顾客到来的方式。）顾客到来的方式。例如，工厂内发生故障待修的机器是单个到达；例如，工厂内

3、发生故障待修的机器是单个到达；在库存问题中，进货看成是成批到达。在库存问题中，进货看成是成批到达。（3 3）顾客相继到达的间隔时间：通常假定是相互）顾客相继到达的间隔时间：通常假定是相互独立的、平稳的、同分布的。独立的、平稳的、同分布的。描述顾客来源以及顾客到达排队系统的规律描述顾客来源以及顾客到达排队系统的规律排队规则排队规则：2（1 1）损失制（即时制）排队系统：顾客到达时，若所有服）损失制（即时制）排队系统：顾客到达时，若所有服务台均被占，服务机构又不允许顾客等待，此时顾客就自务台均被占，服务机构又不允许顾客等待，此时顾客就自动离去。动离去。（2 2）等待制排队系统：顾客到达时，若所有服

4、务台均被占，）等待制排队系统：顾客到达时，若所有服务台均被占，他们就排队等待服务。他们就排队等待服务。（3 3）混合制排队系统：损失制与等待制的混合。）混合制排队系统：损失制与等待制的混合。例如，系统容量有限的混合制系统、等待时间有限的混合例如，系统容量有限的混合制系统、等待时间有限的混合制系统以及逗留时间有限的混合制系统。制系统以及逗留时间有限的混合制系统。（4 4）闭合式排队系统：系统的容量和潜在的顾客数相同）闭合式排队系统：系统的容量和潜在的顾客数相同（允许排队，顾客不得不排队）（允许排队，顾客不得不排队） 服务是否允许排队，顾客是否愿意排队服务是否允许排队，顾客是否愿意排队 服务机构服

5、务机构：3（1 1）服务台的数量，在多个服务台的情形下，是）服务台的数量，在多个服务台的情形下，是串联还是并联。串联还是并联。 （2 2）每位顾客的服务时间：通常假定是相互独立）每位顾客的服务时间：通常假定是相互独立的、平稳的、同分布的。的、平稳的、同分布的。描述服务台的设置和工作情况描述服务台的设置和工作情况 排队系统的符号表示（排队系统的符号表示（KendallKendall记号）：记号）：X/Y/Z/A/B/CX/Y/Z/A/B/C X X：相继到达间隔时间的分布：相继到达间隔时间的分布 Y Y：（每位顾客接受）服务时间的分布：（每位顾客接受）服务时间的分布Z Z：（并列的）服务台个数：

6、（并列的）服务台个数 A A：系统的容量限制个数：系统的容量限制个数B B：顾客源数目：顾客源数目 C C：服务规则（：服务规则（FCFSFCFS） 损失制（损失制（M/M/S/SM/M/S/S）：当）：当S S个服务器被占用后，顾客自动离去个服务器被占用后，顾客自动离去闭合式（闭合式（M/M/S/K/KM/M/S/K/K）：系统的容量和潜在的顾客数都为）：系统的容量和潜在的顾客数都为K K等待制（等待制（M/M/S/M/M/S/）：系统的容量和潜在的顾客数无限制）：系统的容量和潜在的顾客数无限制混合制（混合制（M/M/S/K/M/M/S/K/）：考虑系统的容量有限。例如，一个）：考虑系统的容

7、量有限。例如，一个 医生的诊所医生的诊所M/M/1/4/M/M/1/4/。 描述排队系统的主要数量指标：描述排队系统的主要数量指标：（1 1）队长：指在系统中顾客（包括排队等待的顾客和正在接受服务的顾）队长：指在系统中顾客（包括排队等待的顾客和正在接受服务的顾客）的数量，其期望值记为客）的数量，其期望值记为LsLs（2 2）排队长（等待队长或队列长）：指在系统中排队等待的顾客数，其）排队长（等待队长或队列长）：指在系统中排队等待的顾客数，其期望值记为期望值记为LqLq（3 3）逗留时间：指一个顾客在系统中的停留时间（包括等待时间和接受）逗留时间：指一个顾客在系统中的停留时间（包括等待时间和接受

8、服务的时间），其期望值记为服务的时间），其期望值记为WsWs（4 4）等待时间：指一个顾客在系统中排队等待的时间，其期望值记为）等待时间：指一个顾客在系统中排队等待的时间，其期望值记为WqWq（5 5）忙期：服务机构连续工作的时间长度）忙期：服务机构连续工作的时间长度（6 6）闲期：系统连续保持空闲的时间长度）闲期：系统连续保持空闲的时间长度（7 7）绝对通过能力（平均服务率）：指单位时间内被服务完的顾客数量）绝对通过能力（平均服务率）：指单位时间内被服务完的顾客数量的均值，记作的均值，记作A A（8 8）相对通过能力）相对通过能力: : 指单位时间内被服务完的顾客数与请求服务的顾客指单位时间

9、内被服务完的顾客数与请求服务的顾客数之比值，记作数之比值，记作Q Q（9 9）系统损失率：由于系统的条件限制，使顾客被拒绝服务而使服务机）系统损失率：由于系统的条件限制，使顾客被拒绝服务而使服务机构受到损失的概率，记作构受到损失的概率，记作P P损损 等待制（等待制（M/M/1/M/M/1/）用用表示单位时间内顾客到达的平均数（表示单位时间内顾客到达的平均数（称为平均到达率）称为平均到达率），则，则1/1/表示顾客相继到达的平均间隔时间；表示顾客相继到达的平均间隔时间；用用表示单位时间内能够服务完的顾客平均数（表示单位时间内能够服务完的顾客平均数（称为平均服称为平均服务率），则务率），则1/1

10、/表示一个顾客的平均服务时间。定义服务强度表示一个顾客的平均服务时间。定义服务强度刻画了服务机构的繁忙程度，又称为服务机构的利用率刻画了服务机构的繁忙程度，又称为服务机构的利用率（设（设11） N tPt必有顾客相继到达的间隔时间必有顾客相继到达的间隔时间T T（E(T)=1/E(T)=1/）服从负指数分布）服从负指数分布 通常顾客流假设为通常顾客流假设为PoissonPoisson流，即在长为流，即在长为t t的时间段内到达的顾的时间段内到达的顾客人数客人数 ，假设服务机构对一个顾客的服务时间假设服务机构对一个顾客的服务时间（E()=1/E()=1/）服从负指数分布）服从负指数分布 不加证明

11、的得到：不加证明的得到：系统的状态为系统的状态为n n（即系统中有（即系统中有n n个顾客）的概率：个顾客）的概率： 1,0,1,2,nnPn 1sLqL1sWqW， 运行指标之间的关系（运行指标之间的关系（LittleLittle公式）：公式）：ssLWqqLW1sqWWsqLL（也适用于多个服务台的情形！）（也适用于多个服务台的情形！）例例1 1：某工厂平均每天有一台机器发生故障而需要：某工厂平均每天有一台机器发生故障而需要修理，机器的故障数服从修理，机器的故障数服从PoissonPoisson分布。每台机器分布。每台机器每停工一天损失每停工一天损失2020元。现有元。现有2 2个修理工个

12、修理工A A和和B B，A A每天每天平均能修理平均能修理1.21.2台机器，工资为台机器，工资为3 3元；元；B B每天平均能每天平均能修理修理1.51.5台机器，工资为台机器，工资为1010元。两个工人修理机器元。两个工人修理机器的时间设为指数分布，问工厂应录用哪位工人？的时间设为指数分布，问工厂应录用哪位工人？ 例例2 2：某医院某科室有一位医生值班，每小：某医院某科室有一位医生值班，每小时平均有时平均有4 4个病人，医生每小时平均平均可个病人，医生每小时平均平均可诊治诊治5 5个病人。如要满足个病人。如要满足99%99%以上的病人有座以上的病人有座位，至少应设多少个座位？如果每小时可诊

13、位，至少应设多少个座位？如果每小时可诊治治6 6个病人，可减少多少个座位？病人平均个病人，可减少多少个座位？病人平均等待时间是多少？等待时间是多少？ qwaitTWPSloadpeb,waitPload S1TloadRTRT,ssqWLL顾客的平均等待时间：顾客的平均等待时间：其中每一个顾客等待的概率：其中每一个顾客等待的概率：，S S表示服务台的个数，表示服务台的个数，记再由再由LittleLittle公式，可得其余系统指标公式，可得其余系统指标例例3 3：设打印室有：设打印室有3 3名打字员，平均每个文件名打字员，平均每个文件的打印时间为的打印时间为10min10min，而文件的到达率为每，而文件的到达率为每小时小时1515件，试求该打印室的主要数量指标。件，试求该打印室的主要数量指标。例例4 4：某售票点有两个售票窗口，顾客按每分钟：某售票点有两个售票窗口，顾客按每分钟8 8人人的的PoissonPoisson流到达，每个售票窗口的售票时间均服从流到达，每个售票