[科普中国]-离散事件动态系统

产生背景

人们在生产活动和社会活动中，经常遇到一类复杂的系统，这类系统中有许多事件时而出现，时而消失，时而动作，时而停止，而启动和停止都发生在一些离散的时刻，并带有一定的随机性。例如，港口中船舶的停靠码头、生产线上机床的启停、电话的接通和断开、计算机系统中某项作业的进行和退出，凡此种种，都带有上述特点，这类系统叫做离散事件动态系统(DEDS)。随着生产和科技的日益发展，以及人类社会交往的日趋频繁，这类系统的数量和种类也越来越多。1

特点这类系统的分析研究，需要考虑下面这些特点：

(1)它是由事件驱动发生变化的，带有不连续性。

(2)但考核它的性能的指标却带有连续特点，例如平均吞吐率、等候时间、利用率等。

(3)随机特点。因为有些驱动系统的事件的到来带有随机特点(如顾客的到来、电讯报文的到达)，此外任务的完成、任务间的衔接等也都有一定的随机性，所以常常需要使用处理概率事件与随机过程的方法和技术。

(4)层次性特点。由于这类系统一般是人造复杂系统，所以多半是按层次组织的，例如在空间跨度上，有单机、机组、生产线、车间、工厂几个层次，在时间跨度上，有小时、班(8小时)、日、周、月、年等层次，在组织结构上更是如此。这样我们不得不对每个层次都建立相应的分析方法，有时需要集成，有时又需要分解，上下还必须协调。

(5)动态性特点。我们必须研究这类系统的动态行为和过渡过程。

(6)计算复杂性。在这类系统中，由于组成单元数目大，事件状态多，所以常有“组合爆炸”的危险，这给分析计算带来了很大困难。1

模型由于DEDS的状态空间缺乏易操作的数学结构，所以难以用传统的基于微分或差分方程的方法来刻画其性质。目前研究的最基本问题仍是系统的建模，当前公认的理论框架包含以下3种模型：

(1)逻辑层次模型：只涉及物理状态和事件之间的关系，属于确定性模型，主要包括形式语言/有限自动机和Petri网，用于定性分析。近年的动向是在确定模型中引入随机因素和时间因素，其中计时Petri网和随机Petri网比较重要；

(2)时间层次模型：不仅涉及事件和状态之间的关系，而且要在物理的时间级上刻画与分析演化过程，主要方法为双子代数(dioid)，网络演算属于这一层次；

(3)统计性能层次模型：起源于对随机服务系统的研究，主要方法是排队论和排队网络，理论分析的基础是过程的马尔可夫性。

此外还有运行分析法、平均值分析法、近似分析法和摄动(perturbation)分析法等，国内对DEDS系统的研究处于国际前列。2

研究方法总体来说，有两大类方法：一类是解析法，一类是模拟仿真(随机仿真)方法。

在解析法中，有随机服务系统理论(或称排队论)的方法、利用皮特利网(Petri Nets)的方法、极小极大代数法、摄动分析法等；模拟仿真方法则是利用计算机进行仿真，产生随机事件，大量进行仿真实验，再进行统计。过去这类问题因属运筹学范围，所以多半在运筹学领域内研究。后来由于涉及动态分析，控制理论范围内也对它进行了研讨。现在看来，仅靠定量分析、利用算法已经不够，还需要发挥人工智能、知识工程的作用，并发挥计算机科学技术的威力。看来在今后若干年内，针对某几类系统的分析方法和工具会日益成熟并获得应用，而关于一般理论的探索，也可能有一个良好的开端。1

研究概况人类科学技术的进步产生了为数众多的人造动态系统，如产品制造系统，计算机通信系统，军事C³1系统等。这些系统难以用传统意义下的微分方程或差分方程来描述。对系统进程起决定性作用的是一批离散事件，而不是连续变量。系统行为所遵循的是一些复杂的人为规则，而不是物理学定律或广义物理学定律。这些动态系统的状态的变化取决于离散的时间值，而不是时间的连续变量|。美国哈佛大学教授Y．C．Ho在20世纪80年代初将这类系统称为离散事件动态系统(Discrete Event Dynamic Systems，DEDS)。复杂DEDS系统的建模，最终可能需要同时借助于运筹学、系统控制理论、人工智能等多学科方法的综合运用。

由于制造系统领域涵盖相当多数量和种类的DEDS系统，近10余年来制造系统的DEDS建模方法和行为特征的研究成为国际制造工程和控制自动化领域一项十分重要的研究课题。DEDS的研究从三个层次上展开：逻辑层次、时间层次和统计层次。它们分别针对不同的需要，建立相应的系统研究模型。经过多年的积累，DEDS已经建立了多层次、多侧面、多种模型的描述、分析体系。随机现象在DEDS系统中非常普遍，无论是在制造系统，计算机系统，还是在通讯系统中，最后都要涉及随机品质评估和优化的问题。随机DEDS研究一直是DEDS领域中最活跃的分支，常常采用的方法主要有排队网络(Queuing Network)方法和摄动分析(Perturbation Analysis，PA)方法。3