第九章 排队论 (1)

《第九章 排队论 (1)》由会员分享，可在线阅读，更多相关《第九章 排队论 (1)（67页珍藏版）》请在文档大全上搜索。

1、第第9章章 排队论排队论南京航空航天大学南京航空航天大学排队是我们在日常生活中经常遇到的现象，例如排队是我们在日常生活中经常遇到的现象，例如病人到医院看病、客户到银行汇款、城市拥堵病人到医院看病、客户到银行汇款、城市拥堵路段的汽车排队、电话占线等。排队现象产生路段的汽车排队、电话占线等。排队现象产生的原因之一是要求服务的数量超过了服务机构的原因之一是要求服务的数量超过了服务机构的容量，也就是有部分的服务对象不能立即得的容量，也就是有部分的服务对象不能立即得到服务；原因之二是系统服务对象到达和服务到服务；原因之二是系统服务对象到达和服务时间均存在随机性。前者可以通过增加服务机时间均存在随机性。前

2、者可以通过增加服务机构的容量来解决排队现象，但无休止地增加服构的容量来解决排队现象，但无休止地增加服务机构的容量会导致追加投资并可能发生系统务机构的容量会导致追加投资并可能发生系统资源长时间闲置。后者，也就是系统服务对象资源长时间闲置。后者，也就是系统服务对象到达和服务时间均存在随机性，致使无法准确到达和服务时间均存在随机性，致使无法准确预测估算排队拥堵的具体情况。所以，在服务预测估算排队拥堵的具体情况。所以，在服务系统中的排队现象几乎不可避免。系统中的排队现象几乎不可避免。9.1排队论的基本概念排队论的基本概念排队论是通过对服务对象到来及服务时排队论是通过对服务对象到来及服务时间的统计研究，

3、得出这些数量指标（等间的统计研究，得出这些数量指标（等待时间、排队长度、忙期长短等）的统待时间、排队长度、忙期长短等）的统计规律，然后根据这些规律来改进服务计规律，然后根据这些规律来改进服务系统的结构或重新组织被服务对象，使系统的结构或重新组织被服务对象，使得服务系统既能满足服务对象的需要，得服务系统既能满足服务对象的需要，又能使服务机构的费用最经济或某些指又能使服务机构的费用最经济或某些指标最优。标最优。9.1.1排队过程的一般表示排队过程的一般表示排队系统示意图排队系统示意图一般的排队系统有三个基本组成一般的排队系统有三个基本组成部分部分： 输入过程输入过程 排队及排队规则排队及排队规则服

4、务机构服务机构输入过程输入过程主要包括：主要包括：l顾客相继到达系统的时间间隔顾客相继到达系统的时间间隔l顾客到达系统的方式（顾客可能单个顾客到达系统的方式（顾客可能单个到达，也可能成批到达）到达，也可能成批到达）l顾客源情况顾客源情况 输入过程说明顾客按怎样的规律到达服务系统输入过程说明顾客按怎样的规律到达服务系统的。它可用一定时间内顾客到达的数量或前后两的。它可用一定时间内顾客到达的数量或前后两个顾客相继到达的间隔时间来描述。按照一定时个顾客相继到达的间隔时间来描述。按照一定时间内顾客到达数量或前后两个顾客相继到达的间间内顾客到达数量或前后两个顾客相继到达的间隔时间类型的不同，输入过程可以

5、划分为隔时间类型的不同，输入过程可以划分为确定型确定型和随机型两种和随机型两种：如在自动装配线上装配的各部件：如在自动装配线上装配的各部件就必须是按确定时间间隔到达装配点，定期的航就必须是按确定时间间隔到达装配点，定期的航班、长途客车等都是确定型的；顾客到商店购买班、长途客车等都是确定型的；顾客到商店购买商品、到医院就诊的病人等都是随机型的商品、到医院就诊的病人等都是随机型的。在排。在排队论中，讨论的输入过程主要是随机型的。队论中，讨论的输入过程主要是随机型的。 随机型的输入是指在时间随机型的输入是指在时间t内顾客到达数量内顾客到达数量n(t)服从一定的概率分布。服从一定的概率分布。如服从泊松

6、分布，则在时间如服从泊松分布，则在时间t内到达内到达n个顾个顾客的概率为客的概率为： 或相继到达的顾客的间隔时间或相继到达的顾客的间隔时间T服从负指服从负指数分布，即数分布，即： 式中式中为单位时间顾客期望到达数量，称为单位时间顾客期望到达数量，称为平均到达率；为平均到达率；1/为平均间隔时间。为平均间隔时间。 排队论的系统输入还要关注顾客源是有限集还是无排队论的系统输入还要关注顾客源是有限集还是无限集。如工厂内待修的机器数显然是有限集，而到某限集。如工厂内待修的机器数显然是有限集，而到某航空售票处购票的顾客源则可以认为是无限的。航空售票处购票的顾客源则可以认为是无限的。 顾客的到达可以是相互

7、独立的，也就是说，以前的顾客的到达可以是相互独立的，也就是说，以前的到达情况对以后顾客的到达没有影响，否则就是有关到达情况对以后顾客的到达没有影响，否则就是有关联的。如工厂内的机器在一个短的时间区间内出现故联的。如工厂内的机器在一个短的时间区间内出现故障（顾客到达）的概率就受已经待修或被修理机器数障（顾客到达）的概率就受已经待修或被修理机器数目的影响。我们主要讨论的是相互独立的情形。目的影响。我们主要讨论的是相互独立的情形。 输入过程可以是平稳的，或称为对时间是齐次的，输入过程可以是平稳的，或称为对时间是齐次的，是指描述相继到达的时间间隔分布和所含参数（如期是指描述相继到达的时间间隔分布和所含

8、参数（如期望、方差）都是与时间无关的，否则成为非平稳的。望、方差）都是与时间无关的，否则成为非平稳的。我们主要讨论的是平稳的情形。我们主要讨论的是平稳的情形。排队及排队规则排队及排队规则（1 1）排队）排队排队规则是指顾客来到排队系统后如何排队等候服务的规则，一般有即时制、等待制和混合制三大类。其中即时制(损失制)是指当顾客到达时，如果所有服务台都已被占用，顾客可以随即离开系统。等待制指顾客到达系统时，所有服务台被占用，顾客就加入排队队列等待服务。而混合制是即时制和等待制相结合的一种排队服务规则。混合制主要分为两种情况：一是队长有限制的情况，即当顾客排队等侯服务的人数超过规定数量（等待空间有限

9、）时，后来的顾客就自动离开，另求服务；二是排队等侯时间有限制的情况，即当顾客排队等候超过一定时间就会自动离开，不能再等。（2 2）排队规则）排队规则最常见的等待制排队规则是：最常见的等待制排队规则是：先到先服务先到先服务FCFS：即按到达次序接受服务，这是：即按到达次序接受服务，这是最常见的情形。最常见的情形。后到先服务后到先服务LCFS：如仓库中存放的货物常常是后：如仓库中存放的货物常常是后放入的先被出库使用。放入的先被出库使用。具有优先权的服务具有优先权的服务PS：如医院对病情严重的病人予：如医院对病情严重的病人予以优先治疗，公交车上对老年人予以优先上车就坐以优先治疗，公交车上对老年人予以

10、优先上车就坐等。等。随机服务随机服务SIRO：指服务员从等待的顾客中随机地选：指服务员从等待的顾客中随机地选取其中一个进行服务而不管到达的先后。如电话交取其中一个进行服务而不管到达的先后。如电话交换台接通呼唤的电话。换台接通呼唤的电话。服务机构服务机构排队系统的服务机构主要包含排队系统的服务机构主要包含：l服务员（服务设施）数量及其连接服务员（服务设施）数量及其连接形式（并联或串联）形式（并联或串联）l顾客是单个接受服务还是成批接受顾客是单个接受服务还是成批接受服务服务l服务时间的分布服务时间的分布各类型排队系统各类型排队系统 服务台的服务时间一般也分成确定型和随机型服务台的服务时间一般也分成

11、确定型和随机型两种。例如，自动冲洗汽车的装置对每辆汽车两种。例如，自动冲洗汽车的装置对每辆汽车冲洗（服务）时间是相同的，因而是确定型的。冲洗（服务）时间是相同的，因而是确定型的。但大多数情况下服务时间是随机型的，对于随但大多数情况下服务时间是随机型的，对于随机型的服务时间，我们需要知道服务时间机型的服务时间，我们需要知道服务时间V的概的概率分布。如果服务时间率分布。如果服务时间V服从负指数分布，则其服从负指数分布，则其分布函数是分布函数是式中式中为平均服务率，为平均服务率，1/1/为平均服务时间。为平均服务时间。9.1.2排队系统的分类排队系统的分类KendallKendall符号的形式符号的