离散事件建模与仿真

第7章 离散事件系统建模与仿真离散事件系统指的是一组实体为了达到某些目的，以某些规则相互作用、关联而集合在一起。与连续事件系统不同，离散事件系统所包含的事件在时间上和空间上都是离散的。离散事件系统在生产和生活中是很常见的，例如一个超市就是一个离散事件系统，它由顾客和收银员组成。在离散事件系统中，各事件以某种顺序或在某种条件下发生，并且大都是随机性的，所以，其模型很难用某种规范的形式，一般采用流程图或者网络图的形式来定义实体在系统中的活动。这类系统在建模时，只要考虑系统内部状态发生变化的时间点和发生这些变化的原因，而不用描述系统内部状态发生变化的过程。本章将介绍几种常见的离散事件系统和离散事件系统建模方法。 7.1 离散事件系统模型离散事件系统是指系统的状态仅在离散的时间点上发生变化的系统，而且这些离散时间点一般是不确定的。这类系统中引起状态变化的原因是事件，通常状态变化与事件发生是一一对应的。事件的发生没有持续性，可以看作在一个时间点上瞬间完成，事件发生的时间点是离散的，因而这类系统称为离散事件系统。首先看一个典型的离散系统的例子。例7.1 超市服务系统某理发店只有一名理发师。在正常的工作时间内，如果理发店没有顾客，则理发师空闲；如果有顾客，则为顾客理发。如果顾客到达理发店时，理发师正在为其他顾客服务，则新来的顾客在一旁排队等候。显然，每个顾客到达理发店的时间是随机的，而理发师为每个顾客服务的时间也是随机的，进而队列中每个顾客的等候时间也是随机的。下面，结合例7.1介绍一下在离散事件系统仿真中所用到的一些基本概念。(1)实体实体是指有可区别性且独立存在的某种事物。在系统中，构成系统的各种成分称为实体，用系统论的术语，它是系统边界内的对象。在离散事件系统中，实体可分为两大类：临时实体和永久实体。临时实体指的是只在系统中存在一段时间的实体，这类实体由系统外部到达系统，在系统仿真过程中的某一时刻出现，最终在仿真结束前从系统中消失。例7.1中，顾客是临时实体，他们按一定的规律到达，经过理发师服务（可能要排队等待一段时间），最终离开系统。那些虽然达到，但未进入理发店的顾客则不能称为该系统的临时实体。永久实体指的是永久驻留在系统中的实体，只要系统处于活动状态，这些实体就存在。例7.1中，理发师是永久实体，只要系统处于活动状态，这些实体就存在。可以这样说，永久实体是系统处于活动的必要条件。临时实体按一定规律出现在仿真系统中，引起永久实体状态的变化，又在永久实体作用下离开系统，如此整个系统呈现出动态变化的过程。(2)事件事件是引起系统状态发生变化的行为，它是在某一时间点上的瞬间行为。从某种意义上说，离散事件系统可以看作是由时间驱动的。例7.1中，可以定义顾客到达为一类事件。因为由于顾客的到达，系统的状态理发师的“状态”可能从闲变到忙，或者另一系统状态排队的顾客人数发生变化（队列人数加1）。一个顾客接受服务完毕后离开理发店系统也可以定义为一类事件顾客离开，此事件可能使理发师的“状态”从忙变为闲。(3)属性实体的状态由它的属性的集合来描述，属性用来反映实体的某些性质。例如理发店服务系统中，顾客是一个实体，性别、身高、年龄、到达事件、离开事件等是他的属性。对一个客观实体，其属性很多，我们在仿真建模中，只需要使用与研究目的相关的一部分就可以了。顾客的性别、身高和年龄与理发店服务关系不大，则在理发店服务系统中不必作为顾客的一个属性，而到达事件、服务事件和离开事件是研究理发店服务效率的重要依据，是理发店服务系统仿真中顾客的属性。(4)状态在某一确定时刻，系统的状态是系统中所有实体的属性的集合。(5)活动实体在两个时间之间保持某一状态的持续过程称为活动。离散事件系统中的活动，通常表示两个相邻事件之间所经历的过程。活动因某一事件的发生而开始，因下一事件的发生而结束，活动的开始与结束都是由事件引起的，因此它标志着实体状态迁移的一个片段。在理发店服务系统中，在“顾客到达”与“服务开始”这两个事件之间存在着一个“排队等候”活动，而在“服务开始”与“服务结束”事件之间存在着一个“理发服务”的活动。从另一个角度来看，排队等候活动的开始和结束，都标志着顾客队列状态发生变化；而理发服务活动的开始和结束，都标志着理发师状态的变化。(6)进程进程由和某类实体相关的若干事件及若干活动组成，它用于描述一个临时实体从进入系统到离开系统所经历的完整过程，包括期间发生的若干事件和若干项活动，以及这些事件和活动之间的逻辑和时序关系。例7.1中，一个顾客到达理发店系统排队理发师为之服务服务完毕后离开理发店系统的过程，可视为一个进程。事件、活动和进程三者之间的关系可用图7-1描述。图7-1 事件、活动和进程三者关系示意图(7)仿真时钟仿真时钟用于表示仿真时间的变化，作为仿真过程的时序控制。它是系统运行时间在仿真过程中的表示，而不是计算机执行仿真过程的时间长度。仿真时钟推进的时间间隔称为仿真步长。将连续模型进行离散化后而成为仿真模型时，仿真时间的变化由仿真步长确定，可以是定步长，也可以是变步长。而在离散事件系统仿真中，在任何两个相邻发生的事件之间，系统的状态不会发生变化，因此仿真时钟可以跳过这段时间，从上一事件发生时刻直接推进到下一时间发生的时刻。仿真时钟的推进方式基本上有两种：固定步长时间推进机制和下次事件时间推进机制。由事件发生的随机性可见，离散事件系统仿真时钟的推进步长是随机的，它取决于系统的当前状态和事件发生的条件。(8)统计计数器离散事件系统的状态随着事件的不断发生也呈现出动态变化过程，但仿真的主要目的不是要得到这些状态是如何变化的。因为这种变化是随机的，某一仿真运行得到的状态变化过程只不过是随机过程的一次取样，因而如果进行另一次独立的仿真运行所得到的状态变化过程可能全是另外一种情况，它们只有在统计意义下才有参考价值。7.2 Petri网建模Petri网是由德国学者Carl Adam Petri（卡尔A佩特里）发明的，它是研究信息系统及其相互关系的数学模型。 Carl Adam Petri于1962年在他的博士论文“Kommunikation mit Automaten”（用自动机通信）中提出了一种用于描述事件和条件关系的网络，这就是最初的Petri网。Petri网是一种用简单图形表示的组合模型，具有直观、易懂和易用的优点，它能较好的描述系统的结构，表示系统中的并行、同步、冲突和因果依赖等关系，并以网图的形式，简洁、直观的模拟离散事件系统，分析系统的动态性质，易于在所构造的模型基础上直接实现控制系统。此外，Petri网还有严格而准确定义的数学对象，可以借助数学工具，得到Petri网的分析方法和技术，并用于有限状态机、数据流计算、通讯协议、同步控制、生产系统、形式语言和多处理器系统的建模中，成为离散事件系统的主要建模工具。经过40多年的发展，Petri网理论日益完善，它在机械设计与制造（如柔性制造系统），计算机科学技术（如操作系统、并行编译、网络协议、人工智能等），自动化科学技术（如离散事件动态系统、混杂系统等），以及其他许多科学技术领域都得到了广泛的应用。由于Petri网能表达并发的事件，研究领域趋向认为Petri网是所有流程定义语言之母。7.2.1 Petri网的基本概念1.基本术语(1)资源资源指的是与系统状态发生变化有关的因素。例如原料、零部件、产品（产品或半产品）、工具、设备、数据以及信息等。(2)状态元素资源按照在系统中的作用分类，每一类放在一起，则这一类抽象为一个相应的状态元素。(3)库所状态元素就称为库所。它表示一个场所，并且在该场所存放了一定的资源。(4)变迁变迁指的是资源的消耗、使用以及对应状态元素的变化。(5)条件如果一个库所只有两种状态：有标记和无标记，则该库所称为条件。(6)事件涉及条件的变迁称为事件。(7)容量库存所能够存储资源的最大数量称为库所的容量。2.Petri网的数学结构定义7.1 满足下列条件的三元组，称作一个Petri网：1）2）3）4）其中可以看出，和是两个不相交的集合（一般情况下可假定它们为有限集），它们是Petri网的基本元素集。的元素称为-元或库所(Place)，也称为位置，的元素称为-元或变迁(Transition)，是Petri网的流关系(Flow Relation)。用图形来表示一个Petri网时，把一个-元画成一个小圆圈（“”），一个-元画成一个小矩形（“”）。对，若，则从到画一条有向边。有向边只存在于“”和“”之间，任意两个“”之间或任意两个“”之间都没有有向边相连接。并且一个Petri网中没有孤立结点。定义7.2 设为一个Petri网。对于，记称为的前集或输入集，为的后集或输出集。为元素的外延。显然，一个库所的外延是变迁集的一个子集，一个变迁的外延是库所集的一个子集。对，的外延都不可能是空集（否则就是一个孤立结点）。例7.2 图7-2为一个简单的Petri网的图形表示，其中：库所集变迁集流关系图7-2 一个简单的Petri网示例定义7.3 设为一个Petri网。1)若为从到的映射，其中，则称为上的容量函数。，表示的容量为无穷；2)映射称为Petri网的一个标识(Marking)。二元组(，)(也即四元组()称为一个标识网(Marked Net)；注意：用图形来表示一个标识网（）时，对 ，若 ，则在表示库所的“”内加上个小黑点（当数值很大时，也可以直接写上数字），并说库所中有个标识（Token）或标记。3)映射称为Petri网的权函数，它对各弧线赋权，用或表示由指向或由指向的有向弧的权重。弧线都用其权重来标注，如果弧线的权重等于1，则标注可以省略。例7.3 图7-3为一个具有W的Petri网图。其中：图7-3 一个具有W的Petri网图3.变迁条件和规则定义 7.4 一个网系统(Net System)是一个标识网，并具有下面的变迁发生规则(Transition Firing Rule):1)对于变迁，如果则说变迁在标识下有发生权（Enabled），记为。2)若，则在标识下，变迁可以发生（Fire），从标识发生变迁得到一个新的标识（记为），对定义7.5 六元组称为一个库所变迁系统(Place/Transition System)，其中1)是一个网，其中称为权函数(Weighted Function)称为容量函数(Capacity Function)是的一个标识，满足条件2)满足变迁发生规则a)对于，的条件为b)若，则对 这里，的发生把标识变成，或记为，叫做的后继标识。注意：1)一个没有任何输入库所的变迁叫做源变迁，一个源变迁的有效是无条件的；2)一个没有任何可输出库所的变迁叫潭变迁，一个潭变迁的启动将消耗标识而不产生任何标识。4.Petri网的类型及其特点(1)Petri网的类型1)基本Petri网在最简单的Petri网系统中，规定网中每一个库所的容量为1。其库所也可以称为条件，变迁称为事件，所以基本的Petri网又称为条件事件系统，简称为C/E系统。2)低级Petri网如果网中每一个库所的容量和权重为大于等于1的任意整数，这样的Petri网称为库所变迁网，简称为PT网。3)定时Petri网考虑事件发生和结束所需的时间。将各事件的持续时间标在库所旁边，这样库所中新产生的标识要经过一段时间后才能加入到Petri网的运行中；另外一种时间标法是将时间标在变迁上，于是经过授权的变迁延迟一段时间后发生，或者变迁发生后，马上从输入库所中移去相应的标识，但在输入库所中延迟一段时间产生标识。4)高级Petri网谓词事件网、着色网以及随机网都属于高级网，高级Petri网可以简化复杂的网络模型，它将某种属性赋予标记，表达更多的信息。随机网把变迁的发生看作一个随机过程。一般将每一个变迁的发生时间当成服从指数分布的随机过程。(2)Petri网的主要特点1)能够很好地描述和表达离散事件动态系统(DEDS)建模中经常遇到的并行、同步、冲突和因果依赖等关系。2)由于Petri网具有良好的数学基础和语义清晰的语法，这为形式化分析提供了良好的条件。到目前为止，已经提出了许多种Petri网的形式化分析方法。3)Petri网使用图形来描述系统，使复杂的系统形象化，易于理解，降低了建模的难度，提高了模型的可读性。4)对于柔性制造系统(FMS)那样的分布式阶梯结构，可以分层次建立Petri图。5)与系统结构关系密切，既可以描述系统内部的数据流，也可以描述系统内部的物流，容易在控制模型的基础上直接实现控制系统。7.2.1 基本网系统与条件事件系统定义 7.6 基本网系统是一个四元组，其中1)是一个网，称为条件集(Condition Set), 为事件集(Event Set)，称为的一个情态(Case)。2)事件在情态有发生权（记作），当且仅当3)若事件在情态发生，产生新的情态（记作），则定义 7.7 设为一个基本网系统。满足下列条件的最小集合(是的幂集)称为的完全情态集(Complete Set of Cases)：1)2)，若存在和使得和则定义 7.8 设为一个基本网系统，是的完全情态集。若是一个简单网，而且1)，使得但2)，使得则称为一个条件事件系统(Condition/Event System)，简记为C/E系统。在条件事件(C/E)系统中，条件用表示，事件用表示，所有成立的条件集合称为事例，在Petri图中利用圆圈中标上一个黑点的图形来表示事例。下面进行具体介绍。1.事件逻辑关系的网图图7-4列出了主要的5种关系。图(a)表示事件和为先后关系；图(b)表示事件和为并发关系；图(c)表示事件和为冲突关系；图(d)表示事件，和为迷惑关系；图(e)表示事件和为死锁关系，事件不可能发生。图7-4 事件的逻辑关系Petri网2.应用举例例7.4 生产者消费者系统的Petri网。图7-5中，表示生产者就绪和正在生产产品；表示仓库；，表示消费者就绪和消费产品。图7-5 生产者消费者系统的Petri网图模型上面介绍了一些基本的Petri网的例子，限于篇幅，有兴趣的读者可以参考相关书籍，了解着色Petri网及层次Petri网的相关知识。7.3 排队系统排队论也称随机服务系统理论，是研究“服务”系统的“服务”与“需求”关系的一种数学理论，是运筹学中以概率论为基础的一个重要分支。排队论是在上个世纪初才发展起来的。1905年丹麦哥本哈根电话公司的工程师Erlang（厄尔兰）最早在电话自动交换机设计上应用了排队论，使电话机既能满足挂通电话的需要又不至于设线过多。排队论在第二次世界大战后得到迅猛的发展，成为随机运筹学与概率论中最有活力的研究课题。它不仅建立了比较完备的理论体系，而且在军事、生产、经济、管理、交通、通信、网络等领域得到了广泛应用。7.3.1 排队系统的基本概念1.排队与排队系统排队系统必须经过三个环节，即到达、排队等候处理（服务）、离去。例如一队顾客在超市购物结束，等待付款，则等待服务（收银员收款）的顾客和正在被服务的顾客与超市构成一个排队系统。其中尚未轮到服务的依次等候的顾客自成一个行列，这个等待服务的顾客行列简称为排队。故排队顾客或排队（等待）时间都是仅指排队本身而言；而排队系统中的顾客或排队系统（消耗）时间，则把正在接受服务的顾客也包含在内。2.实体（顾客）到达模式实体到达模式一般用到达时间间隔来描述，可分为确定性到达和随机性到达。随机性到达采用概率分布来描述，最常用的是泊松到达。平稳泊松过程可描述为：在内到达的顾客数的概率为 (7.1)其中，表示在区间内到达顾客的个数；为到达率。若实体到达满足平稳泊松过程，则到达时间间隔服从指数分布，其密度函数为 (7.2)其中，为到达时间间隔的均值。3.排队系统的排队规则顾客依一定的次序和规则接受服务。(1)损失制：指顾客到达时，如所有服务台都正在被占用，随即离去。(2)等待制：指顾客到达时，如所有服务台正在被占用，就排成队伍，等待服务。服务次序可以采用下列各种规则：1)先到先服务(FIFO)。顾客按照到达次序接收服务，这是最常见的情形；2)后到先服务(LIFO)。例如，乘坐电梯时，顾客总是后进先出的。仓库中堆放的大件物品也是如此。在情报系统中，最后到达的信息往往是更有价值的，因而常常采用后到先服务的规则；3)随机服务(SIRO)。当服务台空闲时，从等待的顾客中随机选取一名顾客进行服务，而不管到达的先后次序，例如电话交换台接通呼叫的电话便是采用这种服务的规则；4)优先权服务(PR)。例如医院中急诊病人优先得到治疗；5)最短处理时间先服务(SPT)。例如设备选择工件时，首先选择所需加工时间最少的工件进行加工。对于个服务台的情形，当顾客到达时，可以按照某种规则在每个服务台前排成一队。可以是：第1，个顾客排入第一个队，第2，个顾客排入第二个队，。或者是：所有顾客排成一个公共的队，每当有一个服务台空闲时，队首的顾客进入服务。也可以是：排成个队，当某个顾客到达时，以概率排入第队，且满足。(3)混合制：当排队过长时，后到的顾客会自动离去，此时可定义队长时就排入队列；若，则到达的顾客将自动离去。另一种是当等待时间或逗留时间（等待时间与服务时间之和）小于某一时间时，顾客将等待；大于时，顾客自动离去。4.排队系统的服务机构排队系统的服务机构指的是同一时刻有多少服务设施可接纳顾客，为每一顾客服务了多少时间。服务设施可以没有服务员，也可以有一个或多个服务员。服务台的个数可以是一个或几个，可以是单个服务，也可以是成批服务。各窗口的服务时间可以是确定型或随机型。若服务时间为随机型，且顾客在系统内逗留的时间均值；顾客排队等候服务的时间均值；服务时间的均值；则=+；为了叙述上的方便，引入下列记号：代表泊松输入或负指数分布，代表定长输入或服务，代表阶爱尔朗分布的输入或服务，代表一般随机分布。5.排队系统的性能指标一般情况下，我们都是用以下三个指标来评价排队系统的性能：(1)顾客在系统内停留的时间；(2)系统中的平均顾客数；(3)服务员利用率；(4)平均队长；(5)平均等待时间；(6)系统中出现大于个顾客的概率。7.3.2 单队列、单服务台（）排队系统的模型与仿真方法排队系统的建模主要取决于服务台的个数和队列的个数，最基本的模型是单队列单服务台模型。可以说排队管理的所有基本问题都出自这一模型，其他更复杂的排队系统模型可以通过这一模型的修改得到。标准的()模型是指适合下列条件的排队系统：(1)到达模式：顾客源是无限的，顾客单个到达，相互独立，一定时间的到达数服从泊松分布；(2)排队规则：单队，且对队长没有限制，先到先服务；(3)服务机构：单服务台，每个顾客的服务时间是相互独立的，服从相同的指数分布。此外，假定到达间隔和服务时间是相互独立的。1.排队系统的模型设顾客随机单个到达，平均到达率为，则两次到达时间的平均间隔为。从单通道接受服务后出来的输出率（即系统的服务率）为，则平均服务时间为。比率叫做利用系数，可确定各种状态的性质。例如并且时间充分，每个状态将会循环出现。当，每个系统是不稳定的，而排队长度将会变得越来越长，没有限制。因此，要保持稳定状态即确保单通道排队能够消散的条件是。利用概率论的知识，我们可以计算出下列系统特征量：1)系统中顾客为人以上的概率为： (7.3)2)系统内顾客的平均人数（包括接受服务的顾客）为： (7.4)3)顾客在系统内的平均时间在时间内到达的顾客平均人数为，由于这个人数与系统内顾客平均人数相等，易得 (7.5)因此为 (7.6)4)系统内的平均排队长度（不包括正在服务中的顾客）为： (7.7)5)系统内顾客的平均等待时间由于，则 (7.8)6)顾客在系统内长于时间的概率 (7.9)2.排队系统的仿真方法下面用一个例子来进行说明。例7.5 高速公路出口收费站。假设某高速公路出口收费站的车辆到达服从泊松分布，平均到达时间间隔为5s，收费员的服务时间服从负指数分布，平均服务时间为4s，在此，只考虑一个服务通道的情况，并且按FIFO(先到先服务)方式服务。在进行该系统仿真时，首先要产生具有给定分布的随机变量。在本例这种简单情况下，可以采用反变换法产生随机变量。输入一些常数和初始数据后，用事件推进法对这一系统进行仿真，其仿真程序的结构流程图如图7-6所示。当仿真运行长度为3000辆车时结束，得到如下输出结果：单通道排队系统(SINGLE-SERVER QUEUEING SYSTEM)平均到达间隔(MEAN INTERARRIVAL TIME)： 5.000s平均服务时间(MEAN SERVECE TIME)： 4.000 s仿真顾客数(NUMBER OF CUSTOMER)： 3000平均排队延误(AVERAGE DELAY IN QUEUE)： 15.563 s平均排队长度(AVERAGE NUMBER IN QUEUE)： 3.181图7-6 排队系统仿真流程图由上面的仿真结果可以看出，平均排队长度为3.181辆，平均每辆车的等待时间为15.563s。为了验证仿真结果是否正确，可以用本节给出的排队系统处于稳定状态时的相应计算公式(7.7)和(7.8)计算出解析解。由已知条件=1/5，=1/4，可求得：=3.2 16.0可见，=3.181，=15.563是很接近稳态理论值的，因而有理由认为仿真结果是可信的。但是，需要注意的是：并不是在任何情况下都能得到这样精确的仿真结果。实际若分别仿真运行完=1000，2000，3000，5000辆车结束，其仿真结果如表7.1所示。表7.1 不同仿真运行长度的仿真结果仿真长度10002000300050003.9163.623.1813.4219.72317.58615.56316.982产生这种现象的根本原因在于离散事件系统的随机性。模型的随机性决定了系统性能取值的随机性。由于每次仿真运行的结果只能是对表征系统性能的随机变量的一次取样，那么当系统比较复杂时，如何对仿真结果的可信性进行判断，在离散事件系统仿真中是十分重要的内容。7.4 库存系统在生产经营活动中，不论是生产所需的原材料仓库，还是销售所需的商品仓库，都需要对其库存进行严格的控制、管理。否则，库存过多会造成资金积压，周转困难。而库存过少会影响生产和销售的进行。库存系统不仅存在于生产和销售中，在商品、器材的管理，银行现金管理，水库库存水量的管理，人才储备及管理等许多方面同样存在。7.4.1 库存系统的基本概念在库存系统中，顾客的需求和订货（即库存的补充）是两个最基本的概念。由于需求和订货的存在，库存呈现动态变化。(1)需求：库存系统的输出。由于满足了顾客的需求，库存量不断减少。需求量的变化有确定性和随机性两种。(2)订货：库存系统的输入。为保证供应，就需要补充库存，以满足系统的需求，称之为订货。(3)滞后时间：一般从发出订货要求到所定货物进入仓库需要一段时间，这段时间即为滞后时间。(4)提前时间：由于滞后时间的存在，对管理者来说，需要提前一段时间订货，这段时间即为提前时间。对于一个库存系统，我们一般要研究的问题是在不同需求情况下的库存策略，主要包括：在不同的需求情况下何时订货，定多少货为宜等。研究库存系统的目的一般是要确定或比较各种库存策略，它包括在不同的需求情况下何时订货，定多少货为宜等。评价库存策略的优劣一般是要用采用此策略后在管理上所花费用的高低来衡量，通常考虑的费用包括以下几个方面：1)订货费：包括货物本身的费用、订货手续费和运输费等。如果缺货时不是向其他厂家或商家去订货，而是自己生产，那么这部分费用称为生产费用。2)保管费：包括仓库，设备、人力、货物保存，损坏变质等支出费用，可折算成每件每日费用或每件每月费用等，一般与货物的数量成正比。3)缺货损失费：由于货物的不足、供不应求，错过销售机会或停工待料等造成的损失，缺货费用与所缺货物数量成正比。7.4.2 库存系统的模型与仿真方法根据需求与订货的规律，库存系统可以分为确定性库存系统和随机性库存系统两大类。不同的库存系统对应的仿真模型不同，下面分别予以介绍。1.确定性库存系统确定性库存系统指的是需求量、需求发生时间是确定性的，订货与订货时间是确定性的，而且从订货到货物入库的时间都是确定性的库存系统。对于这种系统，可以采用解析的方法来进行研究。下面采用“用完订货”的策略分别进行讨论。(1)不允许缺货的批量模型在这个模型中，假设所定货物一次供应；不允许缺货（即缺货费用为无穷大）；订货的提前时间为零；采用订货的策略是：用完后即重新订货，每次订货量与初始水平 相同。因此，该模型只需要考虑订货费和保管费。不允许缺货的库存模型是最简单的确定性库存系统模型，可以用图7-7来进行描述。图7-7 最简单的确定性库存系统库存的初始水平为，库存的年需求量为。如图7.6中，为订货周期，；为每年的订货次数，；平均库存量为。设每次订货费用为，每件货物的保管费，则不难计算出总费用为 (7.10)要满足为最小的管理目标，通过设，求得最佳订货量为 (7.11)将式(7.11)代入式(7.10)，得最少的库存管理总费用为 (7.12)(2)允许缺货的批量模型在这个模型中，假设允许缺货；所定货物一次供应；并考虑订货的提前时间。假定其它的参数不变，库存在得到补充之前允许的缺货量为；每件货物的缺货损失费用为；从一批货到达入库到库存消耗为零的时间间隔为；从库存为零到一批新货到达的时间间隔为；为订货周期（）。这种情况下库存量的变化可以用图7-8来进行描述。图7-8 允许有缺货、有滞后时间的库存量变化曲线经过简单的数学运算，可以求得：在时间内总库存量为；在时间内总缺货量为；在时间内平均库存量为 ，平均缺货量为。易得：库存保管费为 (7.13)缺货费为 (7.14)订货费为 (7.15)年库存管理总费用为+ (7.16)为与的函数，为了使最小，可令， 解得，将上述结果代入式(7.15)，从而，最小总费用为 (7.17)可见，允许缺货时的最小总费用比不允许缺货的最小总费用要小，但是，每次订货量要加大。2.随机性库存系统在大多数情况下，库存模型中的参数不是固定不变的常量。比如某种商品在一天的销售就不是确定的，通过历史资料的统计可以得出它服从一定的分布律，针对这样的参数我们应当采用随机变量描述。随机库存系统的种类有很多种，在此，我们只讨论单周期随机库存模型，它与确定性库存系统的区别只是提前时间与单位时间需求量是两个随机变量。(1)模型的基本假设1)在整个需求期内只订购一次货物，订购量为，订购费用和初始库存量均为0，每单位产品的购价（成本）为。2)需求量为一连续型随机变量，其概率密度为。当货物售出时，每单位产品的售价为。3)需求期结束时，没有卖出的货物不存储而折价卖出，单位售价为。试求订购量，以求期望利润最大。(2)模型的求解在解决上述问题时，若需求量为确定时，其售出货物数取决于需求量和订购量，即售出货物数为则此时利润为需求量和订购量的函数 (7.18)但实际上为随机变量，故对于给定的，其期望利润为 (7.19)为求最优订购量，对上式求关于的一阶导数和二阶导数，可得 (7.20)可转化为 (7.21)综合上述二式，表明具有最大的期望利润。3.库存系统的仿真算法前面介绍的随机库存系统，原则上按照最优原理可以求出最佳订货点和库存水平，但是采用期望值来确定模型中的随机变量，或者得到随机变量的概率分布函数则不是容易的事情。因此，一般要借助计算机仿真来实现库存问题。在仿真中，我们首先需要做的是定义模型中的事件，时间的定义依赖于系统状态的描述。库存量可以用来描述系统状态，若所定货物到达仓库，库存量增加，因此可以定义货物到达为一类事件；雇主或客户订货增加会引起库存量的减少，故定义需求到达为一类事件；模型中我们可以将仿真时间运行长度定义为程序事件，故仿真时间运行长度可定义为一类事件；另外，发生货物入库的条件是订货，因此，订货亦可以定义为一类事件。整个仿真过程可以分为两步：首先是规定模型中定义事件的类型及随机发生器的种子；然后是模型的运行过程。后者又有两大块内容。第一是交互式输入模型参数，包括初始库存水平、仿真运行长度、策略数、最大需求量、平均需求时间、每件订货费用、保管费、缺货损失费、需求分布函数等；第二是仿真的流程操作，即先对模型进行初始化，然后调用定时模块确定下一最早发生的事件类型，并分别转向对应事件类型的处理，仿真时钟也随着不断推进。例7.6 某自行车商店的仓库管理员采取一种简单的订货策略，当库存量降低到辆自行车时就向厂家订货，每次定辆，如果某一天的需求量超过了库存量，商店就有销售损失和信誉损失，但是如果库存量过多，将会导致资金积压和保管费增加。若现在已有如表7.2的五种库存策略，试比较选择一种策略以使所花费的费用最少。表7.2 五种库存策略的比较方案编号重新订货点/辆重新订货量/辆方案1125150方案2125250方案3150250方案4175250方案5175300这个问题的已知条件是：(1)从发出订货到收到货物需隔3天。(2)每辆自行车保管费为0.75元/天，每辆自行车的缺货损失为1.80元/天，每次订货费为75元。(3)每天自行车的需求量是在099之间均匀分布的随机数。(4)原始库存为115辆，并假设第一天没有发出订货。这一问题用解析法讨论比较麻烦，但用计算机按天仿真仓库货物的变动情况却很方便。我们以150天为例，依次对这五种方案进行仿真，最后比较各方案的总费用，从而可以做出策略选择。输入一些常数和初始数据后，以一天为时间步长进行仿真。首先检查这一天是否是预定到货日期，如果是，则原有库存量加，并把预定到货量清为零；如果不是，则库存量不变，接着仿真随机需求量，这可用计算机语言中的随机函数得到。若库存量大于需求量，则新的库存量就是原库存量减去需求量；反之，则新库存量变为零，并且要在总费用上加一短缺损失。然后检查实际库存量加上预定到货量是否小于重新订货点，如果是，则需要重新订货，这时就加一次订货费。如果重复运行150天，即可得所需费用总值，这一过程流程图如图7-9所示。图7-9 库存问题仿真流程图按照图7-9的流程编写程序，上机运行后得到这五种库存策略的总费用如表7.3所示。表7.3 五种策略的总费用表方案编号方案1方案2方案3方案4方案5总费用/元38679.7531268.2529699.2526094.0027773.25比较这五种方案的总费用，可以看出方案4最佳，即库存管理人员应取最低订货点为175辆、每次订250辆自行车的方案。这时在150天中的总费用是26094元。7.5 加工系统随着加工制造系统向自动化、复杂化、大规模化的方向不断发展，对仿真的需求也越来越强烈。调度问题是加工制造系统的一个重要问题，有效的调度能够提高设备利用率，缩短生产周期，减少交货延迟，降低库存和生产成本。离散事件系统仿真是研究、解决加工制造系统生产调度问题的一种有效方法，采用的模型主要有数学规划模型、Markov模型、排队网络模型和Petri网模型。加工系统主要由数控机床、加工中心等加工设备(有的还带有工件清洗、在线检测等辅助与检测设备)构成，系统中的加工设备在工件、刀具和控制三个方面都具有可与其它子系统相连接的标准接口。柔性制造系统(Flexible Manufacturing System，简称FMS)是一个由计算机集中控制和管理的制造系统，具有多个半独立的工位和一个物料储存运输系统的体系,能自主地高效率地同时完成多品种中小批量零件的生产任务。它按照成组的加工对象确定工艺过程，选择相适应的数控加工设备和工件、工具等物料的储运系统，并由计算机进行控制，故能自动调用并实现一定范围内多种工件的成批高效生产（即具有“柔性”），并能及时地改变加工产品以满足市场需求。一个柔性制造系统一般包括以下要素：标准的数控机床或柔性制造单元。我们又把具有自动上下料功能或具有多个工位, 具有加工型及装配型的数控机床,称之为“制造单元”,它是FMS中的基本制造单元；一个在数控设备和装卡工位之间运送零件和刀具的传递系统；一个发布指令,协调机床、工件和刀具传送装置的监控系统；中央刀具库及其管理系统；自动化仓库及其管理系统。从柔性制造系统的各项柔性含义中可知，加工系统的性能直接影响着柔性制造系统的性能，且加工系统中柔性制造系统又是耗资最多的部分，因此恰当地选用加工系统是实施柔性制造系统成功与否的关键。本节以柔性制造系统为例，介绍加工制造系统的建模方法。7.5.1 加工系统模型例7.7 某柔性制造车间由1个输入输出站和5个工作站组成。目前，1号到5号工作站分别由3、3、4、4、1个同类的机床组成。6个站之间的距离（单位：英尺）如表7.4所示（将输入输出站规定为第6号站位）：表7.4 某柔性制造车间工作站之间的距离工作站12345610901001802002702900100200180270310010001001001804180200100090100520018010090010062702701801001000假定作业到达输入输出站的间隔时间为具有均值为0.25小时的指数型随机变量。到达的作业共有三类，它们到达概率分别为0.3，0.5和0.2。第1、2、3种类型的作业分别有4、3、5道工序需要完成，每道工序必须在指定的工作站上，按照事先规定好的工艺顺序进行。不同类型作业的工艺路线如表7.5所示。于是，第1种作业首先在第3个工作站上加工，然后在第1个、再后来在第2个工作站上加工，最后在第5个工作站上完成最后的工序。表7.5 工艺路线作业类别工作站组别13，1，2，524，1，332，5，1，4，3作业在工作站之间的移动通过运输装置（即自动引导车AGV）完成，该车间仅有一台该运输装置。该运输装置以1.5m/s的速度移动，并以FIFO规则处理作业的请求。当运输装置到达作业制定的工作站而其移动请求队列为空时，则停在该处不动。如果一项作业在特定时间到达指定的工作站，发现该工作站所有的机床都处于“工作”或者“阻塞”（机床已经加工完毕，但运输装置还没有将加工完的作业运走，则称为“阻塞”）状态，则工件就在该工作站加入FIFO队列。机床的服务时间是服从爱尔朗分布的随机变量，其均值依赖于作业类型和机床所属的工作站类型，表7.6列出了每种作业每道工序的平均服务时间。表7.6 工序的