系统工程原理12-9夏昊翔ppt课件

.,1,系统工程原理(2060120023)3-14周：周四5-8节，研教楼-201室,荣莉莉、夏昊翔大连理工大学管理与经济学部管理科学与工程学院系统工程研究所夏昊翔hxxia84706689(o),.,2,第11章随机服务系统,第1节随机服务系统概念随机服务系统是一类研究得较多的离散事件动态系统。现实中很多问题可以使用随机服务系统加以描述和分析。火车站买票，顾客-售票员；船靠码头卸货，船-码头卸船机；计算机任务处理，任务-计算机；等等。这类系统的特点：随机性：顾客到来的时间与服务者提供服务的时间都是随机的；排队：顾客排队等待服务；（因此，随机服务系统理论也称为排队论）,.,3,排队论（queuing),也称随机服务系统理论，是运筹学的一个主要分支。1909年，丹麦哥本哈根电子公司电话工程师A.K.Erlang的开创性论文“概率论和电话通讯理论”标志此理论的诞生。排队论的发展最早是与电话、通信中的问题相联系的，并到现在是排队论的传统的应用领域。近年来在计算机通讯网络系统、交通运输、医疗卫生系统、库存管理、作战指挥等各领域中均得到应用。,.,4,排队是指在服务机构处要求服务对象的一个等待队列。排队系统是指一个具有排队等待现象的服务系统。排队论是指定量的研究排队问题，寻找系统内在规律，寻找供求关系平衡的最优方案。现实世界中排队的现象比比皆是，但有如下共同特征:(1)有请求服务的人或物，如候诊的病人，请求着陆的飞机等，我们将此称为“顾客”。(2)有为顾客提供服务的人或物，如医生、飞机跑道等，我们称为“服务员”。由顾客和服务员就组成服务系统。(3)顾客随机地一个一个(或者一批一批)来到服务系统，每位顾客需要服务的时间不一定确定的，服务过程的这种随机性造成某个阶段顾客排长队，而某些时间服务员又空闲无事。,.,5,各种形式的排队系统,.,6,各种形式的排队系统,.,7,各种形式的排队系统,.,8,各种形式的排队系统,.,9,各种形式的排队系统,.,10,随机服务系统研究目的与方法,面对拥挤现象，人们通常的做法是增加服务设施，但是增加的数量越多，人力、物力的支出就越大，甚至会出现空闲浪费，如果服务设施太少，顾客排队等待的时间就会很长，这样对顾客会带来不良影响。如何做到既保证一定的服务质量指标，又使服务设施费用经济合理，恰当地解决顾客排队时间与服务设施费用大小这对矛盾，就是随机服务系统理论排队论所要研究解决的问题。因此，研究随机服务系统的基本目的在于合理设计实际的随机服务系统，在保证服务质量的同时使服务系统的开支最小。由于随机因素在服务系统中起着根本性的影响，所以研究随机服务系统时，需要采用研究随机现象规律性的概率论的方法。,.,11,随机服务系统研究的基本问题1.排队系统的统计推断:即通过对排队系统主要参数的统计推断和对排队系统的结构分析，判断一个给定的排队系统符合于哪种模型，以便根据排队理论进行研究。2.系统性态问题:即研究各种排队系统的概率规律性，主要研究队长分布、等待时间分布和忙期分布等统计指标,包括了瞬态和稳态两种情形。3.最优化问题：即包括最优设计(静态优化)，最优运营（动态优化）。,.,12,排队问题求解(主要指性态问题),求解一般排队系统问题的目的主要是通过研究排队系统运行的效率指标，估计服务质量，确定系统的合理结构和系统参数的合理值，以便实现对现有系统合理改进和对新建系统的最优设计等。排队问题的一般步骤：1.确定或拟合排队系统顾客到达的时间间隔分布和服务时间分布(可实测)。2.研究系统状态的概率。系统状态是指系统中顾客数。状态概率用Pn(t)表示,即在t时刻系统中有n个顾客的概率，也称瞬态概率。,.,13,求解状态概率Pn(t)方法是建立含Pn(t)的微分差分方程，通过求解微分差分方程得到系统瞬态解，由于瞬态解一般求出确定值比较困难，即便求得一般也很难使用。因此我们常常使用它的极限(如果存在的话)：,稳态的物理意义见右图，系统的稳态一般很快都能达到，但实际中达不到稳态的现象也存在。值得注意的是求稳态概率Pn并不一定求t的极限,而只需求Pn(t)=0即可。,称为稳态(steadystate)解，或称统计平衡状态(StatisticalEquilibriumState)的解。,.,14,第2节随机服务系统特征和基本排队模型,共同特征：(1)请求服务的人或者物顾客；(2)有为顾客服务的人或者物，即服务员或服务台；(3)顾客到达系统的时刻是随机的，为每一位顾客提供服务的时间是随机的，因而整个排队系统的状态也是随机的。,.,15,每个顾客由顾客源按一定方式到达服务系统，首先加入队列排队等待接受服务，然后服务台按一定规则从队列中选择顾客进行服务，获得服务的顾客立即离开。,基本排队过程,.,16,随机服务系统的基本组成随机服务系统一般有三个基本组成部分：1.输入过程；2.排队规则；3.服务机构。输入过程(顾客按照怎样的规律到达);排队规则(顾客按照一定规则排队等待服务);服务机构(服务机构的设置,服务台的数量,服务的方式,服务时间分布等),.,17,排队长度,服务者1,服务者2,服务者n,顾客到达,几个关键时间指标：1）顾客到来的时间间隔2）排队时间3）系统服务时间,随机服务系统的性质由三个部分决定：顾客到来的规律、排队规律、服务机理。,.,18,1输入过程,这是指要求服务的顾客是按怎样的规律到达排队系统的过程，有时也把它称为顾客流。一般可以从3个方面来描述个输入过程。(1)顾客总体数，又称顾客源、输入源。这是指顾客的来源。顾客源可以是有限的，也可以是无限的。(2)顾客到达方式。这是描述顾客是怎样来到系统的，是单个到达，还是成批到达。(3)顾客流的概率分布，或称相继顾客到达的时间间隔的分布。这是求解排队系统有关运行指标问题时，首先需要确定的指标。顾客流的概率分布一般有定长分布、二项分布、泊松流(最简单流)、爱尔朗分布等若干种。,.,19,输入过程,随机服务系统的输入就是顾客的到来，由于到来规律的不同，所以有各种类型的输入过程。一般用两个顾客到达的时间间隔来描述系统的输入特点。主要输入过程类型：（1）定长输入顾客有规律地等间隔到达，假如每隔时间到一个，这时候相继两个顾客到达的相隔时间的分布函数为：,例如：生产线上的产品从传送带过来进入包装箱的情况,.,20,（2）泊松输入,前面讲到的定长输入过程是一个确定性过程，更多情况下输入过程是随机的。是随机变量。最常见的顾客到来规律按照泊松分布到来，称这样的输入过程为泊松输入。泊松输入满足以下条件：1）平稳性：在每个时间段a,a+t内k个顾客到达的概率与a无关，只与t,k有关；2）无后效性：不相交的时间段到达的顾客数相互独立；3）普通性在把时间段分的足够小的话，每个时间段最多到达一个顾客；4）有限性：任意有限区间到达有限个顾客的概率为1。,.,21,（k=0，1，2，）,在泊松输入下，在时间长度为t的时间段里面到达k个顾客的概率被定义为泊松分布：,其分布函数为负指数分布：,这种输入是应用最广泛的，而且是最容易处理的。,.,22,0-t这个时间段内顾客到达的平均数：,因此，单位时间里面顾客到达的平均数为，称为平均到达率。平均到达的时间间隔为：,.,23,其它输入,（3）爱尔朗（Erlang）输入它的到达间隔相互独立，具有相同的分布a(t)=(t)k-1e-t/(k-1)!,t0（4）一般独立输入到达间隔相互独立、相同分布，其分布函数A(t)可以是任意一个函数，上面的几种输入都可看作是它的特例。（5）成批到达的输入每次到来的不一定是一个顾客，而可能是一批顾客，数目n是一个随机变量，分布为pn=k=ak,k=0,1,2,到达时间间隔则可能是上述几类输入中的一种。,.,24,2排队规则,这是指服务台从队列中选取顾客进行服务的顺序。一般可以分为损失制、等待制和混合制等3大类。(1)损失制这是指如果顾客到达排队系统时，所有服务台都被先到的顾客占用，那么他们就自动离开系统永不再来。典型例子如电话服务。,.,25,(2)等待制这是指当顾客来到系统时，所有服务台都不空，顾客加入排队行列等待服务。等待制中，服务台在选择顾客进行服务时常有如下四种规则：1)先到先服务。按顾客到达的先后顺序对顾客进行服务。最通常的情况。2)后到先服务。堆栈3)随机服务。即当服务台空闲时，不按照排队序列而随意指定某个顾客接受服务。每一顾客被接待的概率相同4)优先权服务。分轻重缓急，如加急电报5）多个服务台情况：可派成几队，或一队。,.,26,(3)混合制这是等待制与损失制相结合的一种服务规则，一般是指允许排队，但又不允许队列无限长下去。具体说来，大致有三种：1)队长有限。当排队等待服务的顾客人数超过规定数量时，后来的顾客就自动离去，另求服务，即系统的等待空间是有限的。2)等待时间有限。即顾客在系统中的等待时间不超过某一给定的长度T，当等待时间超过T时，顾客将自动离去，并不再回来。3)逗留时间(等待时间与服务时间之和)有限。,.,27,3服务机理,服务机理是随机服务系统的第三个要素，包括：服务者的个数、单个服务还是成批服务、以及服务的时间分布(1)服务台数量及构成形式。从数量上说，服务台有单服务台和多服务台之分。从构成形式上看，服务台有：单队单服务台式；单队-多服务台并联式；多队多服务台并联式；单队多服务台串联式；单队多服务台并串联混合式，以及多队多服务台并串联混合式等等。,.,28,.,29,(2)服务方式。这是指在某一时刻接受服务的顾客数，它有单个服务和成批服务两种。(3)服务时间的分布。服务时间分为确定型和随机型。在多数情况下，对每一个顾客的服务时间是一随机变量。1定长分布：每一个顾客服务时间都是常数。类似于输入过程的定长分布情况。2负指数分布：各顾客的服务时间相互独立，具有相同分布。,同样类似于泊松输入的分析，平均服务时间为1/。,.,30,3爱尔朗分布：,平均服务时间为1/。当k=1时就转化为负指数分布，k时就得到长度为1/的定长分布。,4一般服务分布：服务时间相互独立，分布相同，分布函数可能是任意函数。5多服务台情况。6服务时间依赖于队长的情况。,.,31,第3节随机服务系统的一般描述,从一般意义上讲，随机服务系统可以采用如下符号表示：/（A/B/C/K/m/Z)代表输入过程（时间分布）、代表服务时间分布、是服务者数目、是系统中允许的最大顾客数、是能够到来的顾客数、是排队规则。各符号的具体内涵：表示顾客相继到达间隔时间分布，常用下列符号：M表示到达的过程为泊松过程或负指数分布；D表示定长输入；EK表示K阶爱尔朗分布；G表示一般相互独立的随机分布。,.,32,表示服务时间分布，所用符号与表示顾客到达间隔时间分布相同。表示服务台(员)个数：“1”表示单个服务台，“s”(s1)表示多个服务台。表示系统中顾客容量限额，或称等待空间容量。如系统有K个等待位子，则，0K1)个服务台；系统等待空间容量无限(等待制)；顾客源无限；采用先到先服务规则。一般情况下不限制顾客数，采用先到先服务排队规则，这样系统可简写为前三项/（A/B/C）。M/M/s即Poisson输入、负指数服务时间分布、S个服务台的等待制排队模型。M/M/1表示指数输入和指数服务分布、一个服务者。M/G/n表示指数输入、一般服务分布、n个服务者。M/G/1即Poisson输入，一般服务时间分布，单个服务台的等待制排队模型。,.,34,其他模型,M/M/c/K/K顾客来源是有限的服务系统.例如：一个饭店有X张桌子和Y个服务生服务来源有限的顾客.M/D/1服务时间不变的服务系统.D/M/1确定性到达模式,及指数分布服务时间.例如：医生赴约治病的时间表.M/Ek/1服务服从Erlang分布.例如：用相同平均时间去完成一些程序。,.,35,随机服务系统的主要数量指标,描述一个排队系统运行状况的主要数量指标有：1队长和排队长(队列长)队长是指系统中的顾客数(排队等待的顾客数与正在接受服务的顾客数之和)。排队长是指系统中正在排队等待服务的顾客数。队长和排队长一般都是随机变量。这是双方都关心的，也是系统设计者关心的。,.,36,2等待时间和逗留时间从顾客到达时刻起到他开始接受服务止这段时间称为等待时间。等待时间是个随机变量。从顾客到达时刻起到他接受服务完成止这段时间称为逗留时间，也是随机变量。这是顾客最关心的，希望越短越好。3.忙期和闲期忙期是指从顾客到达空闲着的服务机构起，到服务机构再次成为空闲止的这段时间，即服务机构连续忙的时间。这是个随机变量，是服务员最为关心的指标，因为它关系到服务员的服务强度。与忙期相对的是闲期,即服务机构连续保持空闲的时间。在排队系统中，忙期和闲期总是交替出现的。这些量都是随机变量，常常要求取它们的分布及平均值。,.,37,4数量指标的常用记号(1)主要数量指标L平均队长，即稳态系统任一时刻的所有顾客数的期望值；Lq平均等待队长，即稳态系统任一时刻等待服务的顾客数的期望值；W平均逗留时间，即(在任意时刻)进入稳态系统的顾客逗留时间的期望值；Wq平均等待时间，即(在任意时刻)进入稳态系统的顾客等待时间的期望值。,.,38,(2)其他常用数量指标s系统中并联服务台的数目；平均到达率；1平均到达间隔；平均服务率；1/平均服务时间；N稳态系统任一时刻的状态（即系统中所有顾客数）；U任一顾客在稳态系统中的逗留时间；Q任一顾客在稳态系统中的等待时间；,.,39,系统状态=排队系统顾客的数量。N(t)=在时间t排队系统中顾客的数量。队列长度=等待服务的顾客的数量。Pn(t)=在时间t,排队系统中恰好有n个顾客的概率。s=服务台的数目。,.,40,服务强度，即每个服务台单位时间内的平均服务时间，般有=(s)。这是衡量排队系统繁忙程度的重要尺度。当趋近于0时，表明对期望服务的数量来说，服务能力相对地说是很大的，这时，等待时间一定很短，服务台有大量的空闲时间。如服务强度趋近于1，那么服务台空闲时间较少而顾客等待时间较多。一般都假定平均服务率大于平均到达率，即/0有：(1)到达(生)：在(t，t+t)内系统出现一个新的到达的概率为,的常数；没有发生新的到达的概率为,；出现多于一个以上的新的到达概率为0(t)。,的常数，没有消失的概率为,消失多于一个以上的概率为0(t)。则称系统状态随时间而变化的过程X(t)为一个生灭过程。,(2)消失(灭)：在(t，t+t)内，系统消失一个的概率为,.,48,2.生灭过程微分差分方程组设,表示系统在时刻t的状态X(t)=n的概率即,，,状态为n的概率近似于以下四个概率之和：(1)P系统在时刻t时为n，而在t内没有到达也没有消失=,(2)P系统在t时为n-1而在t内有一个到达并且没有一个消失=,(3)P系统在t时为n+1，而在t内没有到达而有一个消失=,则系统在时刻t+t的,(4)P系统在t内发生多于一个的到达或消失=0(t)应用全概率公式有,.,49,当时类似地，当S为有限集时，对有令t0得当系统状态S为有限集时，生灭过程的微分差分方程组为,.,50,当系统状态S为可数集时，生灭过程微分差分方程组为若能求解这组方程，则可得到在时刻t系统状态概率分布称为生灭过程的瞬时解，一般这种瞬时解是难以求得的。,.,51,可以证明，前述的生灭过程存在统计平衡态，即系统各个状态（K1个）的概率分布:pi=常数（i=0,1,K)即：,3.统计平衡下的极限解实际应用中，关心的是时方程的解，称为生灭过程微分差分方程组的极限解。,.,52,令得当S为有限状态集时：当S为可数状态集时：从而可以求得概率分布列,.,53,第5节典型随机服务系统模型和理论结果,.,54,1、M/M/1系统分析,通过分析排队队长无限、泊松输入、指数服务分布的随机服务系统来了解随机服务系统分析的基本方法。下面介绍满足生灭过程典型排队M/M/1与M/M/S的结果1）在时间区段(t,t+t)内，当系统在t时刻的状态为i（已经有i人在系统中，包括排队的和接受服务的）又有一个新的顾客到来的概率为it；2）在时间区段(t,t+t)内，当系统在t时刻的状态为i而有一个顾客离去的概率为it；3)两个以上顾客同时到来或者离去的概率为高阶无穷小可忽略,这一情况与生灭过程一致，可以用生灭过程进行分析。,.,55,MM1模型,一个基本的排列模型。一个服务台,到达率和服务率都服从指数分布。模型的条件是：1、输入过程顾客源是无限的，顾客到达完全是随机的，单个到来，到达过程服从普阿松分布，且是平稳的；2、排队规则单队，且队长没有限制，先到先服务；3、服务机构单服务台，服务时间的长短是随机的，服从相同的指数分布。,.,56,M/M/1系统分析,假定：对于所有状态i而言，到达率为常数，即i=对所有状态i而言，服务率为常数，即i=(3),保证队列不会越排越长。单位时间内平均到达顾客数（即到达率），即顾客平均到达时间1/服务率：单位时间平均服务完的顾客数，每个顾客平均服务时间1/。定义为服务强度。,.,57,对于M/M/1系统，其平衡点的主要指标有：,系统中有n个顾客的概率：,平均队长（系统中平均顾客数）：,平均排队长度：,每个顾客在系统中平均所花时间：,每个顾客排队所花费的平均时间:,.,58,M/M/1举例,.,59,例1,某医院急诊室同时只能诊治一个病人，诊治时间服从指数分布，每个病人平均需要15分钟。病人按泊松分布到达，平均每小时到达3人。试对此排队队系统进行分析。解:对此排队队系统分析如下：（1）先确定参数值：这是单服务台系统，有：故服务强度为：,.,60,（2）计算稳态概率：这就是急诊室空闲的概率，也是病人不必等待立即就能就诊的概率。而病人需要等待的概率则为：这也是急诊室繁忙的概率。,.,61,（3）计算系统主要工作指标。急诊室内外的病人平均数：急诊室外排队等待的病人平均数：病人在急诊室内外平均逗留时间：病人平均等候时间：,.,62,（4）为使病人平均逗留时间不超过半小时，那么平均服务时间应减少多少？由于代入=3，解得5，平均服务时间为：15123min即平均服务时间至少应减少3min,.,63,(5)若医院希望候诊的病人90%以上都能有座位,则候诊室至少应安置多少座位?设应该安置个座位,加上急诊室的一个座位,共有+1个。要使90%以上的候诊病人有座位，相当于使“来诊的病人数不多于+1个”的概率不少于90%，即,.,64,两边取对数（x2）lglg0.1因1，故所以6即候诊室至少应安置6个座位。,.,65,2、M/M/S模型,此模型与M/M/1模型不同之处在于有S个服务台，各服务台的工作相互独立，服务率相等，如果顾客到达时，S个服务台都忙着，则排成一队等待，先到先服务的单队模型。整个系统的平均服务率为s，*/s，（*1）为该系统的服务强度。,.,66,1、状态概率,.,67,2、主要运行指标3、系统状态NS的概率,.,68,M/M/s举例,.,69,例2承接例1，假设医院增强急诊室的服务能力，使其同时能诊治两个病人，且平