排队系统和离散事件系统

队列的应用：单服务台排队系统的模拟一、三个模拟1.离散事件模拟系统在排队系统中，主要有两类事件：顾客的到达事件和服务完毕后顾客的离去事件，整个系统就是不断有到达事件和离开事件的发生，这些事件并不是连续发生的，因此这样的系统被称为离散事件模拟系统。

（1）事件处理过程如果服务员没空，就去队列中排队；否则就为这个顾客生成服务所需的时间t，表示服务员开始为它服务，所需的服务时间是t。

每当一个离开事件发生，就检查有没有顾客在排队，如果有顾客在排队，则让队头顾客离队，为它提供服务，如果没有顾客排队，则服务员可以休息。

（2）如何产生顾客到达事件和离开事件在一个排队系统中，顾客的到达时间和为每个顾客服务的时间并不一定是固定的。

但从统计上来看是服从一定的概率分布。

假设到达的间隔时间和服务时间都满足均匀分布，则可以用随机数产生器产生的随机数。

①以生成顾客到达事件为例子如顾客到达的间隔时间服从[a,b]之间的均匀分布，则可以生成一个[a,b]之间的随机数x，表示前一个顾客到达后，经过了x的时间后又有一个顾客到达。

[a,b]之间的随机数可以按照下面的过程产生：假如系统的随机数生成器生成的随机数是均匀分布在0到RAND_MAX之间，可以把0到RAND_MAX之间的区间等分成b-a+1个，当生成的随机数落在第一个区间，则表示生成的是a，当落在第二个区间，则表示生成的是a+1…当落在最后一个区间，则表示生成的是b。

这个转换可以用rand()*(b-a+1)/( RAND_MAX+1)+a实现，rand 表示系统的随机数生成函数。

2.离散的时间驱动模拟在得到了在x秒后有一个事件生成的信息时，并不真正需要让系统等待x秒再处理该事件。

在模拟系统中，一般不需要使用真实的精确事件，只要用一个时间单位即可，这个时间单位是嘀嗒tick，可以表示1秒，也可以表示1min\1h.沿着时间轴，模拟每一个嘀嗒中发生了什么事件并处理该事件。

模拟开始时时钟是0嘀嗒，随后每一步都把时钟加1嘀嗒，并检查这个时间内是否有事件发生，如果有，则处理并生成统计信息。

离散事件动态系统建模与仿真技术研究离散事件动态系统（Discrete Event Dynamic System，DEDS）是一种用来描述离散事件的数学模型，其在集成电路设计、制造业、物流管理、网络通信等领域中得到了广泛应用。

离散事件动态系统建模和仿真技术是研究这一领域的关键问题之一。

I. 离散事件动态系统简介离散事件动态系统是一种将时间分为离散事件的模型，该模型针对每个事件进行计算，以决定模型的下一个状态。

每个事件的时间戳都是不同的，一次模拟可以包含大量的事件，事件之间可能会有多种关系，这是离散事件模拟的特点。

常见的离散事件动态系统包括排队系统、自动控制系统、网络系统、供应链系统、交通系统等，可以应用于机器人系统、智能交通、虚拟现实等领域。

II. 离散事件动态系统建模离散事件动态系统的建模是指将动态的系统描述成一个离散事件模型的过程，常用的建模框架包括Petri网、DEVS和CTPN等。

Petri网是描述离散事件模型的一种图形化建模语言，其由Petri网元素和变迁组成。

当一个Petri网达到一个使变迁操作成为可能的状态时，变迁将被激活。

Petri网允许对分布式系统进行实时分析和检验，并允许通过变形分析系统行为的改变。

DEVS是离散事件系统建模技术的一种形式化表达，其通过定义系统组件之间的输入输出以及它们之间的转移逻辑来描述系统行为。

DEVS模型一般包含四个部分，输入信号、状态、事件响应函数和状态转移函数。

CTPN是一种图形化建模语言，它通过两个主要元素，控制流程和时间约束，来建模系统的动态行为。

控制流程用于表示系统中的活动和控制流，时间约束表示活动之间的时间上限和下限。

III. 离散事件动态系统仿真离散事件动态系统仿真技术是为了模拟离散事件系统的行为，以便分析和预测其性能。

通常，离散事件动态系统仿真需要从实际系统的模型出发，将系统的模型转换成计算机程序，利用程序模拟实际系统不同的状态和事件，并通过这些状态和事件来推断系统的行为。

第四章 离散事件系统如前所述，根据变量的性质，可分为连续事件系统和离散事件系统。

连续事件系统的状态变量随时间连续变化，其主要特征可通过微分方程描述。

离散事件系统的状态仅在离散的时间点上发生变化，而这些离散时间点一般不确定，即离散事件系统内部的状态变化是随机的，同一内部状态可以向多种状态转变，这种变化只在随机时间点发生，且在一段时间内保持不变。

系统内部状态的变化虽然遵循一定的统计规律，却很难用函数描述。

因此，离散事件系统的建模有其独特性，本章讨论离散事件系统模型及其建模方法。

第一节 离散事件系统模型一、离散事件系统的基本要素离散事件系统的类型虽然多种多样，但它们的主要组成要素基本相同。

从仿真的角度，离散事件系统由实体（entity ）、活动（activity ）、资源（resource ）以及控制（control ）等基本要素构成（见图4-1-1）。

（一）实体（entity ）构成系统的各种成分称为实体。

实体是经过系统处理的事项。

例如产品、顾客、文件等等。

实体用诸如成本、形状、优先权、质量等特征予以定义。

实体可分为：1． 生命体（如顾客、病人等）； 2． 无生命体（如文件、纸币、帐单等）；3． 无法感知的事物或无形物（如电话、电子邮件等）。

与实体相关的一个重要概念是属性（attributes ），属性反映实体的某些性质，其集合描述实体的状态。

例如，在超市服务系统中，顾客是一个实体，性别、身高、年龄、到达时间、服务时间和离开时间等是他的属性。

一个客观实体有很多属性，对特定系统而言，并非所有属性与所研究问题有关，如顾客的性别、身高、年龄与超市服务的关系不大，则不必作为顾客的一个属性，而顾客到达时间、服务时间和离开时间是研究超市服务效率的重要依据，则是超市服务系统中的顾客属性。

（二）活动（activity ）导致系统状态发生变化的过程称为活动。

例如，对顾客的服务、对设备的一次大修、更换设备某一部件，在仿真中均属于一项活动。

离散事件系统建模与仿真离散事件系统（Discrete Event System，DES）是由若干个离散事件组成的动态系统，其状态在离散时间点上发生改变。

通常情况下，离散事件系统包含若干个事件交互的组件，这些组件在某些时刻可以发出事件和接收事件，从而引起系统状态的改变。

离散事件系统的建模和仿真是一项重要的技术，可以帮助我们理解和优化离散事件系统的行为。

离散事件系统的建模是指将离散事件系统抽象成为数学模型，以便于进行分析和仿真。

离散事件系统的建模可以采用多种形式，例如时序图（Sequence Diagram）、Petri网（Petri Net）、有限状态自动机（Finite State Automaton）、队列网络（Queueing Network）等。

不同的建模形式在描述离散事件系统行为时有不同的优缺点，需要根据具体问题的需求进行选择。

时序图是描述离散事件系统动态行为的一种图形化语言。

时序图中，系统的状态用矩形时间段表示，两个状态之间的转换用箭头表示，箭头的标签表示事件类型。

时序图的优点是简单易懂、易于绘制，适合描述事件序列。

但时序图的缺点是描述状态之间的关系比较困难，不易于表示并发事件。

Petri网是一种独特的模型，由传统有向图和各类有限状态自动机组合而成。

Petri网的节点表示状态，变迁则表示事件。

有向边称之为弧，其分为两类：前向弧和后向弧。

前向弧将变迁连接到状态，后向弧则将状态连接到变迁。

使用Petri网进行离散事件系统的建模可以描述事件之间的因果关系，能够直观地反映各事件之间的并发关系和互斥关系。

但是，Petri网模型通常较复杂，不利于模型的分析和优化。

有限状态自动机是一类重要的离散事件系统建模形式，通常使用状态转移图或状态转移表来描述系统行为。

有限状态自动机的节点表示状态，边表示状态之间的转移关系，标签表示事件的类型。

有限状态自动机可以用于描述不同类型的系统行为，例如决策过程、控制逻辑、协议规范等。

单服务台排队系统离散事件系统仿真实验在单服务台排队系统中，存在一个服务台和一些顾客。

顾客根据一定的到达规律到达系统，并进行排队等候服务。

每个顾客需要一定的时间来接受服务，然后离开系统。

在整个过程中，需要记录每个顾客的到达时间、完成时间、等候时间等信息，以评估系统的性能。

以下是进行单服务台排队系统离散事件系统仿真实验的步骤：1.制定实验目标和假设：明确实验的目标和假设，例如评估平均等候时间、系统的利用率等。

2.定义实验参数：设置模拟的时间段、顾客到达的规律、服务时间分布等。

可以根据实际情况选择不同的参数值。

3.创建顾客队列：使用队列数据结构来表示顾客队列，顾客到达时将其加入队列中。

4.初始化系统状态：初始化服务台为空闲状态，设置初始时钟为0。

5.模拟顾客到达：根据到达规律随机生成顾客到达的时间，并将其加入队列。

6.模拟服务过程：当服务台空闲时，从队列中取出下一个顾客进行服务。

根据服务时间分布生成一个随机的服务时间，将服务结束时间设置为当前时钟加上服务时间。

7.记录统计信息：记录每个顾客的到达时间、服务开始时间、完成时间、等候时间等信息。

同时记录系统的状态信息，如系统空闲时间、顾客总数等。

8.更新系统状态：更新服务台的状态，如果队列为空，则服务台为空闲状态，否则继续进行下一个顾客的服务。

9.终止条件判断：判断是否继续模拟，可以根据实验目标设定条件，如模拟时间达到一定阈值或顾客数量达到一定数量。

10.实验结果分析：根据记录的统计信息，计算实验结果，如平均等候时间、系统的利用率等。

通过对比不同参数设置下的实验结果，评估系统的性能情况，并对系统设计进行优化。

在实验过程中，需要注意选择合适的离散事件系统仿真工具，如MATLAB、Python等，进行系统的建模和实验的实施。

同时，应合理选择实验参数和统计指标，以保证实验结果的可靠性和可解释性。

通过进行单服务台排队系统离散事件系统仿真实验，可以评估系统的性能，并对系统设计进行优化，提高系统的效率和顾客的满意度。