入门课件2015-20165、排队系统模拟

二.排队系统简介

动态系统是随时间变化的，含有随机因素的系统，其中排队系统是重要而常见的动态系统。

对排队系统进行模拟，首先要清楚它的运行机制。

1.排队过程的一般表示

顾客源排队结构

服务机构

顾客来到顾客离去排队系统

2.排队系统的组成和特征

(1)

输入过程

对于顾客逐个到达随机性输入过程：1)顾客的到达是相互独立（或相互关联）的；

2)

输入过程是平稳的、对时间是齐次的;

指相继到达的时间间隔的分布和所含参数（均值、方差等）不随时间改变。

(2)排队规则即时制或损失制（如，普通市内电话）。

等待制先到先服务（FIFO）

后到先服务（LIFO）

随机服务（KS）

有优先权的服务

队列单列多列（各列间不能相互转移）

不能中途退出(3)服务机构1）排队方式:单队—单服务台多服务台（串列）112n…12n…单队—多服务台（并列）2)服务时间：确定型的与随机型的

排队论讨论相继到达时间和服务时间，二者中至少有一个是随机型的。

随机服务时间的分布中数学期望、方差等参数都不受时间的影响。

3.排队模型的分类三个主要特征顾客相继到达间隔时间的分布(X);

服务时间的分布(Y)；服务台个数(Z)

。用符号

X/Y/Z表示排队模型的类别。

M—指数分布（Markov性）；D—确定型（Deterministic）;EK—K阶爱尔朗分布（Erlang）;GI—一般相互独立(GeneralIndependent)的随机分布；G—一般（General）随机分布。例7.4.1

M/M/1：到达间隔时间服从指数分布，服务时间服从指数分布，单服务台；M/M/C：间隔时间和服务时间都服从指数分布，

C个平行服务台（顾客仅一列）；

CI/G/1：单服务台，有一般分布的相互独立的间隔时间和一般随机服务时间。

4.间隔时间和服务时间的分布

三种常用的理论分布5．排队系统的主要研究指标1）队长：在系统中的顾客数（平均值记为LS）;

排队长（队列长）：在系统中排队等待服务的顾客数（LQ）。

例7.4.2

一个理发店内有两位服务员

A和

B，顾客们随机到达店内，其中60％的顾客仅需剪发，每位花5分钟时间，另外的40％顾客既要剪发又要洗发，每位花费时间8分钟。

理发店是一个动态随机系统，分析系统的运行效率。

三.动态系统模拟实例及模拟方法结合实例介绍随机动态系统的模拟的方法

2)逗留时间：顾客在系统中的停留时间(WS);等待时间：一个顾客在系统中的排队停留时间(WQ)。

（3）忙期（BusyPeriod）:服务机构一次连续工作的时间长度（反映服务员的工作强度）。(1)系统状态（变量）：在任意时刻，为描述系统需要的含有全部信息的变量集合。

例中有三个状态变量：1).等待服务的顾客数；2).A是否正在服务（是或否）；3).B是否正在服务。(2)实体：需要明确描述的系统对象或组成部分。

实体是系统的可分离部分，或许是系统的永久部分，如服务员、设备装置等。或许可进入和退出系统。1.系统模拟的部分术语

例如商店的顾客，港口的轮船，或发往电力调度系统的一条指令。

本例中的实体？

(3)事件：使系统状态发生变化的瞬时现象。

如例中事件：一名新顾客的到达；A开始服务；

A结束服务；B开始服务；B结束服务。…

(4)活动：两个事件间的持续时间。

常数或随机变量

例中有下述活动：

1)顾客排队时间，即顾客到达至接受服务的持续时间；2)顾客们到达的间隔时间；3)A的服务时间和B的服务时间。

注：事件在时间轴上占据一个点，而活动则占据时间轴上的一段。到达间隔时间排队时间服务时间通常是具有某种分布的随机变量(5)特征（属性）：给定实体的性质。例如一条指令的长短，卡车是满载还是空载。

在模拟中实体的特征可以保持不变，也可以改变;一个实体可能有多种特征。

例中每个顾客只有一个特征：需要服务的种类。

还可以考虑顾客的其他特征，如性别，是否有优先权等等。时间步长法面向事件法（1）时间步长法（固定时间增量法）

人们去考察某一对象系统的状态和活动变化过程时，通常总是随时间的进程来逐步考察和分析。基本步骤为：

1）选取对象系统的一个初始起点作为模拟时钟的零点；2）选定一个合适的时间步长。

2.动态系统模拟的两种方法3)从模拟时钟的零点开始，每推进一个时间步长：对系统的活动和状态按照预定的规则和目的进行考察、分析、计算、记录直到预定模拟结束时刻为止。0Δtt结束时刻

续例7.4.2

一个理发店内有两位服务员

A和

B，顾客们随机到达店内，其中60％的顾客仅需剪发，每位花5分钟时间，另外的40％顾客既要剪发又要洗发，每位花费时间8分钟。*1任一分钟内到达一位顾客的概率p=0.5。

模拟的假定条件：概率

p可以是(0,1)上的任意实数。*2同一分钟内不会有一个以上顾客到达。

如果观察到一分钟内有一位以上顾客来到，就应将时间步长取得更短一些。*3如果店里两名服务员都空闲，则由顾客随意选择一位服务员。*4先到先服务(FIFO)的排队规则。

*5顾客都会耐心等待服务，而且服务员都不能休息。

用时间步长法对理发店系统进行模拟。

通过假设进一步明确理发店系统的运行，为模拟工作做好准备。

对理发店系统进行了部分简化，是一种理想化的模拟。基于解决实际问题的目标，在模拟模型中可以考虑更复杂的情形。

根据假设模拟变量处理如下

1）取时间步长Δt=1(分钟)，在任一分钟内有一名顾客到达的概率是0.5；

2）每位顾客服务时间取为两类顾客的平均服务时间：5×0.6＋8×0.4=6.2（分）。

模拟过程时间步长法自然易理解，但需加快模拟速度。（2）面向事件法（可变时间增量法）

采用不等时间间隔步长的，仅在人们关心的事件发生的时间点上考察系统的状态变化，从而加快模拟的求解过程。

基本思想：对对象系统的一系列不同性质的事件，按照发生时间的先后顺序逐个进行考察。0t模拟方法：编制计算机程序时设置一面“模拟钟”，当有一个事件发生时，才向前走一步，模拟钟走过一步后，自动地寻找下一个最先使系统状态发生变化的事件。时间是可变的停止模拟过程的两种方式：事先规定运行时间;设置为某个特定事件发生;

两种模拟方法的比较：1.如果一个系统的事件出现无明显的规律，常采用面向事件法，可以节约计算机运算时间。2.如果对象系统中事件发生得非常频繁，而且具有一定的规律，为获取较多的信息，可采用时间步长法。模拟思路必须清晰，对模拟的系统对象的运行机制、模拟变量做到心中有数。3.系统运行机制的描述(1)

列出实体、实体特征、状态，活动：*需明确模拟的实体以及允许并行的实体个数；*对每个活动写出初始状态，活动的持续时间；

*写出模拟的初始状态和结束时间（或结束状态)

例：理发店系统,系统的有关模拟变量、因素如下：

实体：

顾客(特征:P(单剪)=0.6；P(洗和剪)=0.4)，

服务员A，服务员B。活动：

到达间隔时间(指数分布,均值为3分钟);

队列（队长无限制），

A的服务时间(剪发5分钟；洗和剪8分钟)

；B的服务时间(剪发5分钟；洗和剪8分钟)

；事件：

顾客到达，A开始服务，A结束服务，B开始服务，B结束服务。初始状态：

队长=0；A空闲，B空闲。

第十个顾客到达。

结束状态：注：采用面向事件法时，应重点考虑活动,即两件事件之间的持续时间。

(2)

写出系统的运转规则。

对系统的排队规则或其他运转规则给出明确说明.

1)在理发店系统中规定顾客的排队规则是FIFO;2)任何人无优先权;3)第一名顾客一定接受A服务员的服务。1）画出模拟过程的流程图

流程图显示模拟必须遵循的路径，能帮助编写计算机程序.(P102图6.9是理发店系统的模拟流程图)。2）产生随机数进行模拟

按照需要产生一系列RND随机数

r1，r2，…，rn,

用来模拟系统的事件和活动。注意：不能重复使用同一个随机数。4.模拟准备工作分析与问题思考：

1.模拟模型中用指数分布随机变量模拟顾客的到达间隔时间，能否用其他随机分布？2.为顾客的服务时间由理发方式确定为两个常数，若服务时间是随机变量如何模拟？7.5模拟模型的应用模拟目的描述一个现有的系统探索一个假设的系统设计一个改进的系统描述一个现有的系统

例.一家工厂发现最近订货增加，不知按现有生产条件是否能按合同及时交货？

可通过模拟模型模拟现有生产情况，分析从原料的订货、交货、生产工序的安排以及劳动力的组织等各因素对及时交货的影响，找出薄弱环节。

对其进行定量分析和相应的改进。探索一个假设的系统例.某医院准备建立一个计算机管理的药品库存系统，目标：保障医院日常所需药品的供应，同时避免因药物过期失效或占用过量资金造成的经济损失。

经模拟，可对各种不同的库存水平进行比较，优选出合理的存储方案。使系统在建立之前就有科学的依据。设计一个改进的系统

例.

工厂生产的某种产品由多种零配件装配而成，可建立一个模拟模型，寻求一种较好的零件加工顺序和机器设备的分配方法，提高设备利用率。模拟模型是现代化企业管理的有效工具

为描述、探索、设计一个系统,对模拟模型及模拟结果常进行下述分析工作：

1.收集系统长期运转的统计值

例如，理发店系统模拟中感兴趣的有平均队长，最大队长，顾客的平均等待时间，两位服务员工作时间百分比等等。

又如，模拟港口的运转是为了研究港口是否出现拥挤情况，希望了解港口的服务率等指标。2.

比较系统的备选装置

要改变一个现实中的复杂系统的部分装置

费时间和资金

借助于模拟模型，可迅速而容易地改变系统。3.研究参数变化对系统的影响

仅需对结果进行分析检验，就能确定是否对现实系统执行这种改变。

例如，新产品的研制和投产是十分重要而带有风险性的决策性问题，若失败其后果往往是十分严重的。

解决方案：经各方面的调查和分析，把不确切的因素考虑进模型中去,变换有关的参数进行多次模拟试验,全面地认识这些不确切因素所起的作用。4.研究改变假设对系统的影响

例.

理发店系统模拟问题中，做了较多的简化假设，如果对假设做一些改变，就能得到不同的模拟模型，可分析假设改变引起的变化。5.寻求系统的最佳工作条件

一个系统可能有若干种不同的运行调度方案，想找出“最佳”方案。

例.理发店系统从顾客的观点出发，关心平均等待服务时间，平均队伍长度等

从店主的立场关心的是服务员的空闲时间，顾客离去率等等。

在某种评价最佳调度的执行标准下，寻求最佳方案：配置合适的服务员人数，规定服务员的工作时间等。模拟次数的确定的几点注意：建立模拟模型模拟模型的详尽程度

初始状态对模拟模型的影响

1.模拟模型的几次运行不能充分描述现实系统的性质与规律。应该做足够多次(合适)的模拟运行后，对结果进行分析。

2.构造一个系统的模拟模型，要抓住系统中的主要因素。模拟模型并非越现实，越详尽越好。*包罗万象的模拟模型在计算机上实现十分困难;*

增大运算工作量；*事无巨细通通包罗，势必分不清主次，造成对模拟结果分析的困难。

原则：牢记建模目标，根据实际问题需要来确定模拟模型应详尽到何种程度。

3.尽量消除初始状态对模拟模型运算结果的影响。

许多系统一旦进入典型的工作状态就能长时期或无限制地运转下去，称其进入稳定状态。达到