一类petri网中基本信标的快速求解算法

《一类petri网中基本信标的快速求解算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第一章绪论1．1研究背景与意义Petri网是描述系统的一种图形和数学模型工具，它适用于描述和研究并发、异步、分布、不确定性和随机的信息系统。Petri网理论首先是用一个Petri网作为一个系统的模型一系统的数学表示，然后对这个Petri网进行分析，可以揭示出被模拟的系统的组织结构和动态行为、系统中可能发生的各种状态变化以及变化之间的关系。这些信息可以用来对被模拟的系统进行评估并提出改进系统的建议。Petri网的概念最早是在1962年CarlAdamPetri的博士论文中提出来的。作为一种控制系统的设计手段，从20世纪70年代开始，Petri网以其能够模拟系统的并发和

2、冲突行为以及反映系统动态特性而受到了广泛关注。1970至1975年，MIT的计算结构研究小组积极参与Petri网相关的研究。1975年7月在MIT举行了第一次Pelri网和相关方法的研讨会。1981年Peterson出版了第一本Petri网方面的书，1985年出版了第二本Petri网专著，到现在己出版了包括高级网在内的许多Petri网专著。从1980年召开第一次Petri网理论和应用的国际研讨会以来，每年一次的国际研讨会连续不断，到今年已经是26届。Petri网理论和应用的研究成果大部分集中在会议论文集中。从1985年起，关于Petri网和性能模型的国际研讨会也开始

3、召开，这个研讨会每两年召开一次。近年来，Pelri网的论文己大量出现在各种学术年会和期刊上。Petri网的理论也在不断地充实和完善。Petri网研究的系统模型行为特性包括：状态的可达性(reachability)、库所的有界性(boundedness)、变迁的活性(1iveness)、初始状态的可逆性(reversibility)、标识之间的可达(reachability)、变迁之间的坚挺(persistence)、事件之间的同步距离(synchronicdistance)和公平性(faimess)等。Petri网的抽象、描述能力不断地向纵向和横向发展。它的纵向扩展

4、表现为从基本的条件／事件(cIB)I网，经过库所／变迁(P／T)网，发展到高级I碉(HEN)(包括谓词，变迁网和着色网)。它的横向扩展表现为从没有参数的网，发展到时间Petri网和随机Petri网；从一般有向弧发展到禁止弧和可变弧；从自然数标记个数到概率标记个数：从原子变迁发展到谓词变迁和子网变迁。Petri网作为一种数学方法，在离散事件系统建模、分析、性能评价和控制设计中得到了广泛的应用。柔性制造系统作为一种典型的离散事件系统是Petfi网理论应用较早的一个领域，也是较成功的～个领域。2～类Petri网中基本信标的快速求解算法柔性制造系统是由统一的信息控制系统、物

5、料储运系统和一组数字控制加工设备组成，能适应加工对象变换的自动化机械制造系统(FlexibleManufacturingSystem)，英文缩写为FMS。随着社会对产品多样化、低制造成本及短制造周期等需求日趋迫切，FMS发展颇为迅速，并且由于微电子技术、计算机技术、通信技术、机械与控制设备的发展，也促使柔性制造技术日臻成熟，80年代后，制造业自动化进入一个崭新时代，即基于计算机的集成制造(CIMS)时代，FMS已成为各工业化国家机械制造自动化的研制发展重点。在柔性制造系统中，各种工件在离散时间点上进入系统，系统对它们进行并行加工处理，各加工进程共享一定数量的资源，如

6、机床、机器人、夹具、托盘等，各种工件有自己的特殊加工路径，即资源需求序列。在加工过程中，各种工件的并行处理流竞争着有限的资源，从而可能会导致系统运行和控制的许多问题，其中最为突出的问题是FMS的死锁问题。FMS的死锁是制约系统控制和调度实现的关键因素，因此对FMS死锁的研究是FMS目前研究的热点之一。死锁是由于并发执行的任务中不适当地资源分配造成的，因此，要分析死锁现象，很有必要对系统中任务和资源之间的模型做一个分析，将一个带有共享资源的交互系统称为资源分配系统RAS(ResoureeAllocationSystem)，即一系列并发运行的任务需要资源共享。死锁最先是

7、由计算机科学家在研究操作系统的资源分配过程中提出来的，Coffman[7]给出了死锁发生的四个必要条件：1互斥：资源只能分配给某个确定的任务或是空闲资源不能同时为两个任务占据。2非抢占：资源不可抢占，只能被占用它的任务自愿释放(任务完成了相应工序)。3占用并等待：占据某些资源的任务请求另外的新资源而这些资源为其它任务所占据。4循环等待：存在一组资源请求{Pl，P2⋯．，Pn}，其中P1等待P2占据的资源，P2等待P3占据的资源⋯．，Pn等待Pl占据的资源。由此可见，只要保证其中的某个条件不成立，就可以消除死锁问题。通常专家学者通过控制系统资源的分配来破坏不同进程