排队论及排队系统优化

以你之姓@ 2023-10-17 15:05 151阅读 0赞

\#\#\#纲要

*  排队现象与排队系统;
 *  排队模型与系统参数;
 *  排队系统时间参数分布规律;
 *  排队系统的生灭过程与状态转移方程;
 *  排队系统分析;
    
     *  单服务台负指数分布模型
     *  多服务台负指数分布模型
 *  排队系统优化分析;
    
    排队论发源于上世纪初。  
    当时美国贝尔电话公司发明了自动电话，以适应日益繁忙的工商业电话通讯需要。这个新发明带来了一个新问题，即通话线路与电话用户呼叫的数量关系应如何妥善解决，这个问题久久未能解决。  
    1909年，丹麦的哥本哈根电话公司A.K.埃尔浪(Erlang)在热力学统计平衡概念的启发下予以解决了。

\#\#1.1排队现象与排队系统  
\#\#\#一、排队现象  
![这里写图片描述][32645f62fe5b20fc0f85ebe1d43704bb.png]

（1） 由于顾客到达和服务时间的随机性，
     现实中的排队现象几乎不可避免；
    （2） 排队过程，通常是一个随机过程，
     排队论又称“随机服务系统理论”；

\#\#\#二、排队系统  
（一）排队服务过程

![这里写图片描述][2f1dfcada24b3d7c8ce98e2a7f15147b.png]  
（二）排队系统的要素及其特征

1.  排队系统的要素：  
    （1） 顾客输入过程；  
    （2） 排队结构与排队规则；  
    （3） 服务机构与服务规则；
2.  排队系统不同要素的主要特征：  
    （1）顾客输入过程  
    ![这里写图片描述][7cd86d72b9f4ac3d4b0f52d4d4ad02f7.png]  
    （2）排队结构与排队规则  
    ![这里写图片描述][4f956a121a8b31d4ef8d4099d3a9a874.png]  
    （3）服务机构与服务规则  
    ![这里写图片描述][d61e5242dd10896ce8e7858a83bf524b.png]
    
    服务台(员)为顾客服务的顺序:
    
     *  a) 先到先服务(FCFS);
     *  b) 后到先服务(LCFS);
     *  c) 随机服务;

*  d) 优先服务;

\#\#1.2排队模型与系统参数  
\#\#\#一、排队模型  
(一)排队模型表示方法  
![这里写图片描述][025f8e86518e875ff013aa043e65aed5.png]  
![这里写图片描述][d882672578c401e55a1b45baab2c5802.png]

——略去后三项，即指 “**X/Y/Z///FCFS**”；
    ——这里仅研究FCFS的情形；

(二)到达间隔和服务时间典型分布

（1）泊松分布           **M** ； 
    （2） 负指数分布         **M** ； 
    （3） k阶爱尔朗分布      **Ek**； 
    （4） 确定型分布         **D**； 
    （5） 一般服务时间分布   **G**；

(三)排队模型示例

——M/M/1，M/D/1，M/ Ek /1； 
    ——M/M/c， M/M/c//m，  
    ——M/M/c/N/ ，。。。

\#\#2.1、系统参数  
\#\#\#(一)系统运行状态参数  
\#\#\#\#1、系统状态 N(t)  
——指排队系统在时刻t时的全部顾客数 N(t)，  
包括“排队顾客数”和“正被服务顾客数”；  
——系统状态的可能值如下：  
（1）系统容量无限制， N(t) =0，1，2，…;  
(2) 系统容量为N时, N(t) =0,1,2,…,N;  
(3) 服务台个数为c/损失制, N(t) =0,1,2,…,c;  
**一般,系统状态N(t)是随机的。**  
\#\#\#\#2、系统状态概率：  
![这里写图片描述][61b627e07ef1ce51d62d28cbc15e6f21.png]

——一般，排队系统运行了一定长的时间后，系统状态的概率分布不再随时间t变化，即初始时刻（t=0）系统状态的概率分布(Pn(0) ，n>>0）的影响将消失。

\#\#\#(二)系统运行指标参数  
——评价排队系统的优劣。  
\#\#\#\#1、队长与排队长  
![这里写图片描述][cac64c2ad986bcf8e3c98877e9a15e18.png]

\#\#\#\#2、逗留时间与等待时间  
(1)逗留时间:  
——指一个顾客在系统中的全部停留时间； 期望值，记为 Ws  
(2)等待时间:  
——指一个顾客在系统中的排队等待时间；期望值，记为 Wq

**Ws = Wq + E[服务时间]**

\#\#\#\#3、其他相关指标  
(1)忙 期: 指从顾客到达空闲服务机构起到服务  
机构再次空闲的时间长度；  
(2)忙期服务量：指一个忙期内系统平均完成  
服务的顾客数；  
(3)损失率: 指顾客到达排队系统，未接受服务  
而离去的概率；  
(4)服务强度： = /c ；  
\#\#3 排队系统时间参数分布规律

\#\#\#一、顾客到达时间间隔分布  
\#\#\#\#(一)泊松流与泊松分布  
如果顾客到达满足如下条件,则称为泊松流:  
(1) 在不相互重叠的时间区间内，到达顾客数相互独立(无后效性).  
(2) 对于充分小的时间间隔内，到达1个顾客的概率与t无关，仅与时间间隔成正比 (平稳性)：  
(3) 对于充分小的时间间隔，2个及以上顾客到达的概率可忽略不计 (普通性)。

![这里写图片描述][dc224826d893eec1081c2bd0d0b7551c.png]  
\#\#\#\#(二)泊松流到达间隔服从负指数分布  
![这里写图片描述][b27c72cd6ad969274c6134adb65bf7d8.png]  
\#\#\#二、顾客服务时间分布  
\#\#\#\#(一)负指数分布  
![这里写图片描述][b2f1077a036238668200c4ae9b9caf1d.png]  
\#\#\#\#(二)爱尔朗(Erlang)分布

![这里写图片描述][1e0eb2c3f8ae3cc9fc8ca47d79ceefdd.png]  
\#\#3.1 排队系统的生灭过程

\#\#\#一、排队系统的生灭过程  
\#\#\#\#(一)生灭过程的背景与定义

![这里写图片描述][50751289bf7f03d9a25d36d0cd965279.png]  
\#\#\#\#(二)生灭过程状态变化的性质  
![这里写图片描述][b6451e568942a9f2452c4158d4cfc267.png]  
\#\#\#\#(三) 排队系统的生灭过程  
(1)生灭过程示意  
![这里写图片描述][72af19e698100956a5c3404d3a4fd4c5.png]

(2)生灭过程定义

![这里写图片描述][08e92ea85c92500b7c78494294477f06.png]  
\#\#4 典型排队系统分析  
排队系统性能参数的一般关系 ——Little 公式  
![这里写图片描述][fbfe9e67668a3b12c3e16366a2ad8f37.png]

\#\#4 .1 单服务台负指数分布M/M/1排队系统  
. 模型的条件是：

1、输入过程――顾客源是无限的，顾客到达完全是随机的，单个到来，到达过程服从普阿松分布，且是平稳的；
        2、排队规则――单队，且队长没有限制，先到先服务；
        3、服务机构――单服务台，服务时间的长短是随机的，服从相同的指数分布 。
    
    对于M／M／1模型有如下公式：

![这里写图片描述][69781d37f50ed1aba4b788eed7427cfa.png]  
\#\#\#\#例1  
某医院急诊室同时只能诊治一个病人，诊治时间服从指数分布，每个病人平均需要15分钟。病人按泊松分布到达，平均每小时到达3人。试对此排队系统进行分析。

![这里写图片描述][15147cc1165a555af2e4cc6bd5d48bb3.png]  
![这里写图片描述][f1936bcaa5070de3cdbe9837c35d111f.png]  
![这里写图片描述][924f81d59e631e13aa58f5a04da09037.png]  
![这里写图片描述][b2e5e9ab49b340c514a5b3aa345f2dd8.png]  
![这里写图片描述][7c3c054751c79ce91ca49a5129fccbb1.png]  
![这里写图片描述][82293c5547e27d5b9c827e5d6b959a36.png]

\#\#4 .2 多服务台负指数分布M/M/S排队系统  
![这里写图片描述][683e6cbaf49830269120b78e133aa088.png]

\#\#\#\#1、状态概率  
![这里写图片描述][2226dd64363e6e9ea77f9a9e83282683.png]  
\#\#\#\#2、主要运行指标  
![这里写图片描述][de30afb9dea425f08d04216899223231.png]  
\#\#\#\#3、系统状态N ≥S的概率  
![这里写图片描述][465c20b39face8765a25d990d2dbec1c.png]

\#\#\#\#例2  
承接例1，假设医院增强急诊室的服务能力，使其同时能诊治两个病人，且平均服务率相同，试分析该系统工作情况。  
![这里写图片描述][39cbb03036783ad58ec3e6e21dafcf4c.png]  
![这里写图片描述][b5162e86e5c69f4ee7489e629c011005.png]  
\#\#\#\#例3  
某医院挂号室有三个窗口，就诊者的到达服从泊松分布，平均到达率为每分钟0.9人，挂号员服务时间服从指数分布，平均服务率每分钟0.4人，现假设就诊者到达后排成一队，依次向空闲的窗口挂号，显然系统的容量和顾客源是不限的，属于M/M/S型的排队服务模型。求：该系统的运行指标 ？  
![这里写图片描述][2c24304287e2adb05db1a569f133fb0b.png]  
![这里写图片描述][667839fdce48f6a15457de91f254861a.png]  
![这里写图片描述][4c52ccebd47cca4af90f339858cf9e8f.png]

[32645f62fe5b20fc0f85ebe1d43704bb.png]: https://img-blog.csdnimg.cn/img_convert/32645f62fe5b20fc0f85ebe1d43704bb.png
[2f1dfcada24b3d7c8ce98e2a7f15147b.png]: https://img-blog.csdnimg.cn/img_convert/2f1dfcada24b3d7c8ce98e2a7f15147b.png
[7cd86d72b9f4ac3d4b0f52d4d4ad02f7.png]: https://img-blog.csdnimg.cn/img_convert/7cd86d72b9f4ac3d4b0f52d4d4ad02f7.png
[4f956a121a8b31d4ef8d4099d3a9a874.png]: https://img-blog.csdnimg.cn/img_convert/4f956a121a8b31d4ef8d4099d3a9a874.png
[d61e5242dd10896ce8e7858a83bf524b.png]: https://img-blog.csdnimg.cn/img_convert/d61e5242dd10896ce8e7858a83bf524b.png
[025f8e86518e875ff013aa043e65aed5.png]: https://img-blog.csdnimg.cn/img_convert/025f8e86518e875ff013aa043e65aed5.png
[d882672578c401e55a1b45baab2c5802.png]: https://img-blog.csdnimg.cn/img_convert/d882672578c401e55a1b45baab2c5802.png
[61b627e07ef1ce51d62d28cbc15e6f21.png]: https://img-blog.csdnimg.cn/img_convert/61b627e07ef1ce51d62d28cbc15e6f21.png
[cac64c2ad986bcf8e3c98877e9a15e18.png]: https://img-blog.csdnimg.cn/img_convert/cac64c2ad986bcf8e3c98877e9a15e18.png
[dc224826d893eec1081c2bd0d0b7551c.png]: https://img-blog.csdnimg.cn/img_convert/dc224826d893eec1081c2bd0d0b7551c.png
[b27c72cd6ad969274c6134adb65bf7d8.png]: https://img-blog.csdnimg.cn/img_convert/b27c72cd6ad969274c6134adb65bf7d8.png
[b2f1077a036238668200c4ae9b9caf1d.png]: https://img-blog.csdnimg.cn/img_convert/b2f1077a036238668200c4ae9b9caf1d.png
[1e0eb2c3f8ae3cc9fc8ca47d79ceefdd.png]: https://img-blog.csdnimg.cn/img_convert/1e0eb2c3f8ae3cc9fc8ca47d79ceefdd.png
[50751289bf7f03d9a25d36d0cd965279.png]: https://img-blog.csdnimg.cn/img_convert/50751289bf7f03d9a25d36d0cd965279.png
[b6451e568942a9f2452c4158d4cfc267.png]: https://img-blog.csdnimg.cn/img_convert/b6451e568942a9f2452c4158d4cfc267.png
[72af19e698100956a5c3404d3a4fd4c5.png]: https://img-blog.csdnimg.cn/img_convert/72af19e698100956a5c3404d3a4fd4c5.png
[08e92ea85c92500b7c78494294477f06.png]: https://img-blog.csdnimg.cn/img_convert/08e92ea85c92500b7c78494294477f06.png
[fbfe9e67668a3b12c3e16366a2ad8f37.png]: https://img-blog.csdnimg.cn/img_convert/fbfe9e67668a3b12c3e16366a2ad8f37.png
[69781d37f50ed1aba4b788eed7427cfa.png]: https://img-blog.csdnimg.cn/img_convert/69781d37f50ed1aba4b788eed7427cfa.png
[15147cc1165a555af2e4cc6bd5d48bb3.png]: https://img-blog.csdnimg.cn/img_convert/15147cc1165a555af2e4cc6bd5d48bb3.png
[f1936bcaa5070de3cdbe9837c35d111f.png]: https://img-blog.csdnimg.cn/img_convert/f1936bcaa5070de3cdbe9837c35d111f.png
[924f81d59e631e13aa58f5a04da09037.png]: https://img-blog.csdnimg.cn/img_convert/924f81d59e631e13aa58f5a04da09037.png
[b2e5e9ab49b340c514a5b3aa345f2dd8.png]: https://img-blog.csdnimg.cn/img_convert/b2e5e9ab49b340c514a5b3aa345f2dd8.png
[7c3c054751c79ce91ca49a5129fccbb1.png]: https://img-blog.csdnimg.cn/img_convert/7c3c054751c79ce91ca49a5129fccbb1.png
[82293c5547e27d5b9c827e5d6b959a36.png]: https://img-blog.csdnimg.cn/img_convert/82293c5547e27d5b9c827e5d6b959a36.png
[683e6cbaf49830269120b78e133aa088.png]: https://img-blog.csdnimg.cn/img_convert/683e6cbaf49830269120b78e133aa088.png
[2226dd64363e6e9ea77f9a9e83282683.png]: https://img-blog.csdnimg.cn/img_convert/2226dd64363e6e9ea77f9a9e83282683.png
[de30afb9dea425f08d04216899223231.png]: https://img-blog.csdnimg.cn/img_convert/de30afb9dea425f08d04216899223231.png
[465c20b39face8765a25d990d2dbec1c.png]: https://img-blog.csdnimg.cn/img_convert/465c20b39face8765a25d990d2dbec1c.png
[39cbb03036783ad58ec3e6e21dafcf4c.png]: https://img-blog.csdnimg.cn/img_convert/39cbb03036783ad58ec3e6e21dafcf4c.png
[b5162e86e5c69f4ee7489e629c011005.png]: https://img-blog.csdnimg.cn/img_convert/b5162e86e5c69f4ee7489e629c011005.png
[2c24304287e2adb05db1a569f133fb0b.png]: https://img-blog.csdnimg.cn/img_convert/2c24304287e2adb05db1a569f133fb0b.png
[667839fdce48f6a15457de91f254861a.png]: https://img-blog.csdnimg.cn/img_convert/667839fdce48f6a15457de91f254861a.png
[4c52ccebd47cca4af90f339858cf9e8f.png]: https://img-blog.csdnimg.cn/img_convert/4c52ccebd47cca4af90f339858cf9e8f.png