搜索
系统工程原理(2060120023)3-14周：周四5-8节，研教楼-201室荣莉莉、夏昊翔大连理工大学管理与经济学部管理科学与工程学院系统工程研究所夏昊翔hxxia@dlut.edu.cn84706689(o)第11章随机服务系统第1节随机服务系统概念•随机服务系统是一类研究得较多的离散事件动态系统。现实中很多问题可以使用随机服务系统加以描述和分析。•火车站买票，顾客-售票员；•船靠码头卸货，船-码头卸船机；•计算机任务处理，任务-计算机；等等。•这类系统的特点：•随机性：顾客到来的时间与服务者提供服务的时间都是随机的；•排队：顾客排队等待服务；（因此，随机服务系统理论也称为排队论）排队论（queuing),也称随机服务系统理论，是运筹学的一个主要分支。1909年，丹麦哥本哈根电子公司电话工程师A.K.Erlang的开创性论文“概率论和电话通讯理论”标志此理论的诞生。排队论的发展最早是与电话、通信中的问题相联系的，并到现在是排队论的传统的应用领域。近年来在计算机通讯网络系统、交通运输、医疗卫生系统、库存管理、作战指挥等各领域中均得到应用。•排队是指在服务机构处要求服务对象的一个等待队列。•排队系统是指一个具有排队等待现象的服务系统。•排队论是指定量的研究排队问题，寻找系统内在规律，寻找供求关系平衡的最优方案。•现实世界中排队的现象比比皆是，但有如下共同特征:•(1)有请求服务的人或物，如候诊的病人，请求着陆的飞机等，我们将此称为“顾客”。•(2)有为顾客提供服务的人或物，如医生、飞机跑道等，我们称为“服务员”。由顾客和服务员就组成服务系统。•(3)顾客随机地一个一个(或者一批一批)来到服务系统，每位顾客需要服务的时间不一定确定的，服务过程的这种随机性造成某个阶段顾客排长队，而某些时间服务员又空闲无事。各种形式的排队系统各种形式的排队系统各种形式的排队系统各种形式的排队系统各种形式的排队系统随机服务系统研究目的与方法•面对拥挤现象，人们通常的做法是增加服务设施，但是增加的数量越多，人力、物力的支出就越大，甚至会出现空闲浪费，如果服务设施太少，顾客排队等待的时间就会很长，这样对顾客会带来不良影响。•如何做到既保证一定的服务质量指标，又使服务设施费用经济合理，恰当地解决顾客排队时间与服务设施费用大小这对矛盾，就是随机服务系统理论——排队论所要研究解决的问题。•因此，研究随机服务系统的基本目的在于合理设计实际的随机服务系统，在保证服务质量的同时使服务系统的开支最小。•由于随机因素在服务系统中起着根本性的影响，所以研究随机服务系统时，需要采用研究随机现象规律性的概率论的方法。随机服务系统研究的基本问题1.排队系统的统计推断:即通过对排队系统主要参数的统计推断和对排队系统的结构分析，判断一个给定的排队系统符合于哪种模型，以便根据排队理论进行研究。2.系统性态问题:即研究各种排队系统的概率规律性，主要研究队长分布、等待时间分布和忙期分布等统计指标,包括了瞬态和稳态两种情形。3.最优化问题：即包括最优设计(静态优化)，最优运营（动态优化）。排队问题求解(主要指性态问题)求解一般排队系统问题的目的主要是通过研究排队系统运行的效率指标，估计服务质量，确定系统的合理结构和系统参数的合理值，以便实现对现有系统合理改进和对新建系统的最优设计等。排队问题的一般步骤：1.确定或拟合排队系统顾客到达的时间间隔分布和服务时间分布(可实测)。2.研究系统状态的概率。系统状态是指系统中顾客数。状态概率用Pn(t)表示,即在t时刻系统中有n个顾客的概率，也称瞬态概率。求解状态概率Pn(t)方法是建立含Pn(t)的微分差分方程，通过求解微分差分方程得到系统瞬态解，由于瞬态解一般求出确定值比较困难，即便求得一般也很难使用。因此我们常常使用它的极限(如果存在的话)：nttnp)(plim稳态的物理意义见右图，系统的稳态一般很快都能达到，但实际中达不到稳态的现象也存在。值得注意的是求稳态概率Pn并不一定求t→∞的极限,而只需求Pn’(t)=0即可。过渡状态稳定状态pnt排队系统状态变化示意图称为稳态(steadystate)解，或称统计平衡状态(StatisticalEquilibriumState)的解。第2节随机服务系统特征和基本排队模型共同特征：(1)请求服务的人或者物——顾客；(2)有为顾客服务的人或者物，即服务员或服务台；(3)顾客到达系统的时刻是随机的，为每一位顾客提供服务的时间是随机的，因而整个排队系统的状态也是随机的。ServerQueueArrival每个顾客由顾客源按一定方式到达服务系统，首先加入队列排队等待接受服务，然后服务台按一定规则从队列中选择顾客进行服务，获得服务的顾客立即离开。基本排队过程排队结构服务机构顾客源顾客到达排队规则服务规则离去图1排队系统示意图随机服务系统的基本组成随机服务系统一般有三个基本组成部分：1.输入过程；2.排队规则；3.服务机构。输入过程(顾客按照怎样的规律到达);排队规则(顾客按照一定规则排队等待服务);服务机构(服务机构的设置,服务台的数量,服务的方式,服务时间分布等)排队长度服务者1服务者2服务者n顾客到达几个关键时间指标：1）顾客到来的时间间隔2）排队时间3）系统服务时间随机服务系统的性质由三个部分决定：顾客到来的规律、排队规律、服务机理。1．输入过程这是指要求服务的顾客是按怎样的规律到达排队系统的过程，有时也把它称为顾客流。一般可以从3个方面来描述—个输入过程。(1)顾客总体数，又称顾客源、输入源。这是指顾客的来源。顾客源可以是有限的，也可以是无限的。(2)顾客到达方式。这是描述顾客是怎样来到系统的，是单个到达，还是成批到达。(3)顾客流的概率分布，或称相继顾客到达的时间间隔的分布。这是求解排队系统有关运行指标问题时，首先需要确定的指标。顾客流的概率分布一般有定长分布、二项分布、泊松流(最简单流)、爱尔朗分布等若干种。输入过程随机服务系统的输入就是顾客的到来，由于到来规律的不同，所以有各种类型的输入过程。一般用两个顾客到达的时间间隔τ来描述系统的输入特点。主要输入过程类型：（1）定长输入顾客有规律地等间隔到达，假如每隔时间α到一个，这时候相继两个顾客到达的相隔时间τ的分布函数为：tttptA,0,1}{)(例如：生产线上的产品从传送带过来进入包装箱的情况（2）泊松输入前面讲到的定长输入过程是一个确定性过程，更多情况下输入过程是随机的。τ是随机变量。最常见的顾客到来规律按照泊松分布到来，称这样的输入过程为泊松输入。泊松输入满足以下条件：1）平稳性：在每个时间段[a,a+t]内k个顾客到达的概率与a无关，只与t,k有关；2）无后效性：不相交的时间段到达的顾客数相互独立；3）普通性——在把时间段分的足够小的话，每个时间段最多到达一个顾客；4）有限性：任意有限区间到达有限个顾客的概率为1。!)(}{ketkXptk（k=0，1，2，…）在泊松输入下，在时间长度为t的时间段里面到达k个顾客的概率被定义为泊松分布：其分布函数为负指数分布：0,00,1}{)(ttetptAt这种输入是应用最广泛的，而且是最容易处理的。0-t这个时间段内顾客到达的平均数：111)!1()(!)()(kktktktekttektktN因此，单位时间里面顾客到达的平均数为λ，称为平均到达率。平均到达的时间间隔为：1)1()(000dtteetdttdptt其它输入（3）爱尔朗（Erlang）输入它的到达间隔相互独立，具有相同的分布a(t)=λ(λt)k-1e-λt/(k-1)!,t≥0（4）一般独立输入到达间隔相互独立、相同分布，其分布函数A(t)可以是任意一个函数，上面的几种输入都可看作是它的特例。（5）成批到达的输入每次到来的不一定是一个顾客，而可能是一批顾客，数目n是一个随机变量，分布为p{n=k}=ak,k=0,1,2,……到达时间间隔则可能是上述几类输入中的一种。2．排队规则这是指服务台从队列中选取顾客进行服务的顺序。一般可以分为损失制、等待制和混合制等3大类。(1)损失制这是指如果顾客到达排队系统时，所有服务台都被先到的顾客占用，那么他们就自动离开系统永不再来。典型例子如电话服务。(2)等待制这是指当顾客来到系统时，所有服务台都不空，顾客加入排队行列等待服务。等待制中，服务台在选择顾客进行服务时常有如下四种规则：1)先到先服务。按顾客到达的先后顺序对顾客进行服务。最通常的情况。2)后到先服务。堆栈3)随机服务。即当服务台空闲时，不按照排队序列而随意指定某个顾客接受服务。每一顾客被接待的概率相同4)优先权服务。分轻重缓急，如加急电报5）多个服务台情况：可派成几队，或一队。(3)混合制这是等待制与损失制相结合的一种服务规则，一般是指允许排队，但又不允许队列无限长下去。具体说来，大致有三种：1)队长有限。当排队等待服务的顾客人数超过规定数量时，后来的顾客就自动离去，另求服务，即系统的等待空间是有限的。2)等待时间有限。即顾客在系统中的等待时间不超过某一给定的长度T，当等待时间超过T时，顾客将自动离去，并不再回来。3)逗留时间(等待时间与服务时间之和)有限。3．服务机理服务机理是随机服务系统的第三个要素，包括：服务者的个数、单个服务还是成批服务、以及服务的时间分布(1)服务台数量及构成形式。从数量上说，服务台有单服务台和多服务台之分。从构成形式上看，服务台有：①单队—－单服务台式；②单队-－多服务台并联式；③多队—－多服务台并联式；④单队—－多服务台串联式；⑤单队—－多服务台并串联混合式，以及多队多服务台并串联混合式等等。112n....12n。。。单队单服务台多队多服务台（并列)单队多服务台（并列）12n...12312单队多服务台（串列）混合形式(2)服务方式。这是指在某一时刻接受服务的顾客数，它有单个服务和成批服务两种。(3)服务时间的分布。服务时间分为确定型和随机型。在多数情况下，对每一个顾客的服务时间是一随机变量。1定长分布：每一个顾客服务时间都是常数。类似于输入过程的定长分布情况。2负指数分布：各顾客的服务时间相互独立，具有相同分布。0,00,1)(xxexBux同样类似于泊松输入的分析，平均服务时间为1/μ。3爱尔朗分布：xkkekxkkxb)!1()()(1平均服务时间为1/μ。当k=1时就转化为负指数分布，k→∞时就得到长度为1/μ的定长分布。4一般服务分布：服务时间相互独立，分布相同，分布函数可能是任意函数。5多服务台情况。6服务时间依赖于队长的情况。第3节随机服务系统的一般描述从一般意义上讲，随机服务系统可以采用如下符号表示：①/②/③/④/⑤/⑥（A/B/C/K/m/Z)①代表输入过程（时间分布）、②代表服务时间分布、③是服务者数目、④是系统中允许的最大顾客数、⑤是能够到来的顾客数、⑥是排队规则。各符号的具体内涵：①——表示顾客相继到达间隔时间分布，常用下列符号：M——表示到达的过程为泊松过程或负指数分布；D——表示定长输入；EK——表示K阶爱尔朗分布；G——表示一般相互独立的随机分布。②——表示服务时间分布，所用符号与表示顾客到达间隔时间分布相同。③——表示服务台(员)个数：“1”表示单个服务台，“s”(s1)表示多个服务台。④——表示系统中顾客容量限额，或称等待空间容量。如系统有K个等待位子，则，0K∞，当K=0时，说明系统不允许等待，即为损失制。K=∞时为等待制系统，此时一般∞省略不写。K为有限整数时，表示为混合制系统。⑤——表示顾客源限额，分有限与无限两种，∞表示顾客源无限，一般∞也可省略不写。⑥——表示服务规则，常用下列符号FCFS：表示先到先服务的排队规则；LCFS：表示后到先服务的排队规则；PR：表示优先权服务的排队规则。举例：