吉林大学远程教育 运筹学课件8.1.ppt

运 筹 学 第八章 排队论 §1 排队服务系统的基本概念 在生产和日常生活中，经常可以碰到各种各样的服务系统。如上下班乘公共汽车，公共汽车与乘客构成一个服务系统；到商店买东西，售货员与顾客也构成一个服务系统，都有等候服务的问题。 有些场合下，服务系统的构成没有那么明显。如从长春往北京打电话，由于长春、北京之间同一时间内允许通话对数是有限的，因此，要求通话的人数超过这个限度时，就要排队等候。虽然打电话的人分散在全市各处，彼此互不见面，但他们与长话台一起构成一个服务系统。他们在长话台前排成一个无形的队伍，就如同排队等候公共汽车的乘客队伍一样。 一般在一个排队服务系统中总是包含一个或若干个 “服务设施” ，有许多“顾客”进入该系统要求得到服务，服务完毕后即自行离去。倘若顾客到达时，服务系统空闲着，则到达的顾客立即得到服务，否则顾客将排队等待服务或离去。 1.1 排队系统 现实中的排队现象是多种多样的，一般排队系统都有下述三个基本组成部分（图10-1）。 客等，他们的到达都是随机的。 ⑶顾客的到达方式可能是一个一个的，也可能是成批的。我们将只研究单个到达的情形。 2.排队规则 ⑴顾客到达时，如果所有服务台都被占用，则顾客离开服务系统，这种方式称为即时制或损失制。例如旅客到旅店住宿就属于这种方式。另外一种情形，当服务台被占用时，后来的顾客就排队等待服务，称为等待制。 ⑵有的服务系统对进入排队系统的顾客数有一定限制，象理发店供等待服务的顾客坐的椅子的座位数是有限的。大多数服务系统可以认为系统对顾客是没有限制的。 ⑶在多服务台情况下，队列的数目可以是单列，也可以是多列。 ⑷等待服务的次序，最常见的是先到先服务；还有带优先权的服务，如加急电报、医院的急诊等；随机服务，指服务台随机对等待的顾客进行服务；后到先服务，如乘坐电梯的顾客先入后出，后入先出。 3.服务机构 ⑴从服务设施的数量上可分为单服务台与多服务台。 ⑵在多服务台情形，服务台可能是并列的，也可能是串列的。并列服务系统可以同时对多个顾客进行服务，而串列情况下，每个顾客要依次经过各个服务台的服务才能离开系统。图10-2中（a）是多队多台并列情形；（b）是单队多台并列情形；（c）是单队多台串列情形。 ⑶服务时间可以分成确定型和随机型两种情形。自动机床对零件的加工时间是确定型的，大多数情况服务时间是随机型的。 1.2 排队模型的分类 按照排队系统组成部分的主要特征可以对排队模型进行分类。1971年排队论符号标准化会议决定，排队模型分类符号为： X/Y/Z/A/B/C 其中 X处填写顾客相继到达时间间隔的分布； Y处填写服务时间的分布； Z处填写并列的服务台数量； A处填写系统容量限制； B处填写顾客源数量； C处填写服务次序，如先到先服务FCFS；后到先服务LCFS等，如果略去该项则表示先到先服务。 表示相继到达间隔时间和服务时间的各种分布符号是： M ——负指数分布（Markov） D ——确定型分布（Deterministic） Ek——k阶爱尔朗分布（Erlang） GI——一般独立分布的时间间隔（General Independent） G——一般服务时间的分布（ General ） 例如：M/M/1/∞/∞表示顾客相继到达的间隔时间为负指数分布，服务时间为负指数分布，单服务台，系统对顾客无限制，顾客源无限，先到先服务的服务模型。 1.3 排队模型的参数 在排队系统的分析计算中，要用到下面一些概念和符号： ⑴Pn（t）——在时刻t系统中恰好有n个顾客的概率。 ⑵N（t）——在时刻t服务系统中的顾客数。 ⑶稳定状态——当一个排队服务系统开始运转时，系统状态很大程度上取决于系统的初始状态和运转经历的时间，但过去一段时间后，系统的状态将独立于初始状态及经历的时间，这时称系统处于稳定状态。在稳定状态下，系统处于某一状态的概率是一个常数。所以Pn（t）可写为Pn。由于对系统的瞬时状态分析比较困难，所以排队论中主要研究系统处于稳定状态的工作情况。 ⑷λn——当系统有n个顾客时，新来顾客的平均到达率（单位时间到达的顾客数），则1/ λn表示相邻两个顾客到达的平均间隔时间。如60分钟内到达30个顾客，则平均到达率λn