运筹学——排队论

1第12章排队论排队系统的理论。所构成的服务机构及其排队现象理论）是研究由顾客、排队论（随机服务系统些常见实例：随机服务系统实体的一顾客服务机构系统服务类型储户出纳员或自动柜员机银行储蓄飞机机场跑道飞机着陆或起飞电话呼唤交换台电话通话进港货轮港口码头卸货或装货加工工作工段工序安排用户任务处理机计算机系统故障机器维修工及各种维修设备机器维护2。排队理论进行分析研究以便根据系统符合于哪种模型，：判断给定的一个排队）排队系统的统计推断（系统的最优运营；现有排队者指最优设计，后者指态最优和动态最优，前）最优化问题：分为静（的分布和忙期分布等；等待时间，主要研究队长分布、排队系统的概率性规律）性态问题：研究各种（排队论的研究内容：3213顾客源（总体）服务机构排队结构第1节基本概念、排队过程的一般表示1排队规则排队系统离去顾客到来服务规则排队过程的一般模型4则称为非平稳的。都是与时间无关的，否期望值、方差等和所含参数隔时间分布和的，是指相继到达的间的，或称对时间是齐次）输入过程可以是平稳关联的。互独立的，也可以是有）顾客的到达可以是相的间隔时间分布。顾客到达数或相继到达需要知道单位时间内的于随机的情形，也可以是随机型的。对时间可以是确定型的，）顾客相继到达的间隔单个的情形）。批的（我们这里只研究是单个的，也可能是成）顾客到来的方式可能。限的，也可能是无限的）顾客的总体可能是有非互斥）：能有下列几种情况（并达排队系统的过程，可）输入过程：即顾客到（各部分的特征如下：服务机构排队规则输入过程排队系统的基本组成征、排队系统的组成和特)(54321125被服务为止。，必须坚持到以退出，有的不能退出能。列中的顾客有的可以互相转移，有的则不顾客有的可列。多列时，各列间的以是单列，也可以是多）从队列的数目看，可无限的）两种情形。制（即认为容量可以是）可分为有限制和无限客数允许进入排队系统的顾容量（即因，系统的象的）的限制或其他原体的处所，也可以是抽）由于空间（可以是具有优先权的服务随机服务后到先服务先到先服务可以采用下列各种规则为顾客进行服务的次序对于等待制或混合制，等待制、混合制。：即时制（损失制）、）排队规则可分为三类序接受服务。客按照一定的规则和次）排队规则：到达的顾（32:126以是混合的。列，可以是串列，也可台情形，它们可以是并）对于多服务员台。个服务员台，也可以有一个或多务员）服务机构可以没有服）服务机构（/2//13单服务台—单队多服务台（并列）—单队112cc21多服务台（并列）—多队多服务台（串列）多服务台（混合）c12322117受时间的影响。期望值、方差等参数不布是平稳的，即分布的）总假定服务时间的分道其概率分布。型的服务时间，需要知和随机型的。对于随机）服务时间分为确定型行，也可以成批进行。）服务方式可以单个进543数。）（并列）服务台的个（）服务时间的分布；（间的分布；）相继顾客到达间隔时（）年，的三个特征进行分类（按排队系统中影响最大、排队模型的分类321:Kendall.G.D195338客是一队）个并列服务平台，但顾（，）服务时间的分布一般（—）的间隔时间的分布一般相互独立（—）分布阶爱尔朗（—）确定型（—的首字母）为负指数分布（—例如：。分别表述上述三个特征其中，记号表示：相应的模型用ccMDMMGGIkEDMMZYXZYXk//1//generaltindependengeneralerlangticdeterminisMarkov,,//Kendall9FCFS/////LCFSserved,firstcome,lastFCFSserved,firstcome,first,,/////Kendall1971ZYXCmBNAZYXCBAZYX即指约定：略去后三项时，）后到后服务（），（服务规则，如先到服务—顾客源数目—系统容量限制—项的意义如下：的意义如前所述，后三其中，记号扩充为：年10繁的时间长度）忙期：服务机构连续（服务时间等待时间逗留时间，其期望值记为系统中排队等待的时间等待时间：一个顾客在其期望值记为在系统中的停留时间，）逗留时间：一个顾客（正被服务的顾客数队列长队长顾客数，其期望值记为系统中排队等待服务的队列长（排队长）：在客数，其期望值记为）队长：在系统中的顾（本数量指标为：判断系统运行优劣的基究设计改进措施等。系统结构是否合理、研优值，以决定量，确定系统参数的最运行效率，估计服务质目的：研究排队系统的、排队系统的求解3][][][2][][][13qsqsWWLL11）的解。（态）解，或称统计平衡状（（如果存在）称为稳态）解（分方程，其解成为瞬态的关系式一般为微分差含的概率。、系统状态为表示在时刻台数）时，（表示正在繁忙的服务为）即时制，服务台个数（时，为）队长有限制，最大数（）队长没有限制时，（：个顾客，其可能的值为即是指系统中有系统的状态为statemequilibriulstatisticastatesteady)(lim;statetransient)()(,,2,1,03,2,1,02,2,1,01nntnnPtPtPnttPcncNnNnnn12第2节到达时间间隔的分布和服务时间的分布的参数值。种理论分布，并估计它合于哪统计学的方法确定系统的经验分布，然后按照时间间隔和和服务时间客到达要根据原始资料作出顾排队系统的参数，首先要解决排队问题，确定天）（艘总天数到达总数平均到达率，从而其中，到达总数）。表（见得到船舶到达数的分布给出的资料进行整理，例举例说明：对课本得到经验分布。对原始资料进行整理，、经验分布/48.336512711271110296424311203-12P3101P309113:1iiiiwt和排队等待的时间隔顾客相继达到的时间间而计算出对顾客的服务时间，从记录顾客到达的时刻和另外，原始资料中还应is1iiiwit1iw0,00,11iiiiiiiiiiiiitswtswtswwt当当等待时间：隔：顾客相继到达的时间间0)2(iiitsw当0)1(iiitsw当1iisiiwit空闲14平均服务率平均服务时间平均到达率平均间隔时间：布数据，并进一步计算分布数据和服务时间分得到顾客到达时间间隔整理，公式，将原始资料进行间隔与等待时间的计算中得出的顾客到达时间根据例：见课本例1P3102）、泊松流（flowPoission2生的次数等。的故障数，自然灾害发呼叫的次数，机器出现达的人数，电话机接到定时间内到，如某一服务设施在一内随机事件发生的次数布适合于描述单位时间发生率。泊松分积）内随机事件的平均是单位时间（或单位面泊松分布的参数年发表，于由法国数学家泊松分布1838PoissionDenisSimeon)ondistributiPoission(15)0,(})()({),(0),[),()0(),0[)(2112212121nttntNtNPttPnnttttPtttNnn个顾客到达的概率，即）（内有为在时间区间，内到达的顾客数为在时间区间设泊松流的定义：)(),(22),[3)(),(),[21),(2121tΔotΔttPtΔtttΔλtΔotΔλtΔttPtΔttΔtttΔttPnnn至于可以忽略，即极小，以个以上顾客到达的概率个及内有，在时间区间）对充分小的（的方差。单位时间内顾客到达数也表示达的平均顾客数，同时，它表示单位时间内到是常数，称为概率强度其中，成正比，即时间区间长无关，而与率与时刻内有一个顾客到达的概，在时间区间）对充分小的（后效性）；独立的（该性质称为无间内顾客到达数是相互）在不相重叠的时间区（流：称顾客的到达形成泊松满足下列三个条件时，当16tλtNVartλtNEtNntPtPnn)]([)]([)(t),0()(期望和方差分别为服从泊松分布，其数学机变量个顾客的概率，并称随的时间区间内到达表示长为，得到之间的关系方程并求解与通过建立)()(ttPtPnn,2,1,0,0!)()(ntenttPtnn布进行初步的识别。经验分布是否是泊松分征，可以由此对一个泊松分布的一个重要特期望值和方差相等，是17）、负指数分布（ondistributilexponentianegtive31,1][,1][0,00,1)(0,00,)(2TVarTEttetFTTttetfTtTtT分布函数是服从负指数分布。则称的概率密度若是随机变量18表示。记号中都用）是等价的。故在参数为与输入过程为泊松流（），数分布（密度函数为时间是独立且为同负指因此，相继到达的间隔必定服从负指数分布。隔时间时，顾客相继到达的间）当输入过程是泊松流（纯随机的。种情形下顾客的到达是无关；这一个顾客到来所需时间到来所需的时间与过去则该性质说明一个顾客达的间隔时间，表示排队系统中顾客到柯夫性）。若）无记忆性（或称马尔（负指数分布的性质：MteTTtKendall0,21的意义正好相符。隔时间，这与相继顾客到达的平均间就表示达的顾客数，因此，表示单位时间内平均到对于泊松流，1][1TE19均服务率。完成的顾客数，称为平表示单位时间内被服务务时间，表示一个顾客的平均服的期望值和密度函数分别为。这时设它的分布函数有时也服从负指数分布）统的两顾客的间隔时间也即在忙期相继离开系对一顾客的服务时间（的分布服务时间,1)()(,1)(vEvetfetFvtvtv20）、爱尔朗分布（ondistributiErlang42121211][,1][)!1()()()(,,,kTVarTEkTekktktbvvvTkkvvvktkkkk且阶爱尔朗分布。服从称的概率密度是可以证明的负指数分布，则参数个相互独立、服从相同是设21第3节单服务台负指数分布排队系统的分析顾客源：顾客的总体排队系统的顾客数系统的容量：允许进入）顾客源为有限：（）系统容量有限制：（模型：）标准的（服从负指数分布）：时间入过程为泊松流，服务服务台的排队系统（输讨论以下三种情形的单mMMNMMMMMM//1//3//1//2//1//1//122//1//1//1MMMM模型：、标准的服从相同的负指数分布务时间是相互独立的，单服务台，各顾客的服—服务机构先到先服务单队，且队长无限制，—排队规则到达过程已平稳泊松分布，定时间内的到达数服从个到来，相互独立，一顾客源为无限，顾客单—输入过程件的排队系统：该模型是指适合下列条其实际意义见下页。远）（否则队列将排至无限其中，的概率为态下，系统的状态为以得出，在统计平衡状利用随机过程的知识可,111,)1(10nPPnnn23的实际意义：利用率。程度，称为服务机构的刻画了服务机构的繁忙）（沿用至今）；电话理论时用的术语，早期研究），或称为话务强度（务强度（间隔时间之比，称为服的平均务时间与相继顾客到达表示一个顾客的平均服）（服务的平均数之比）；顾客到达的平均数与被同的时间区间内服务率之比（即：在相表示平均到达率与平均）（不同的解释：的表达式不同，可以有根据013intensitytraffic)/1/()/1(21P24标：模型的几个主要数量指标准的1//MM1)1()1(2)10(1)1(12011110ssnnnnnnqsnnnnsLPLPnPPnLLnnPL值）顾客数（队列长的期望）在队列中等待的平均（或数（队长期望值））在系统中的平均顾客（25141][13sqs间的期望值）在队列中顾客等待时（的负指数分布