(机械电子工程专业论文)基于eopn和启发式搜索算法的fms仿真平台研究.pdf_第1页
(机械电子工程专业论文)基于eopn和启发式搜索算法的fms仿真平台研究.pdf_第2页
(机械电子工程专业论文)基于eopn和启发式搜索算法的fms仿真平台研究.pdf_第3页
(机械电子工程专业论文)基于eopn和启发式搜索算法的fms仿真平台研究.pdf_第4页
(机械电子工程专业论文)基于eopn和启发式搜索算法的fms仿真平台研究.pdf_第5页
已阅读5页,还剩64页未读, 继续免费阅读

(机械电子工程专业论文)基于eopn和启发式搜索算法的fms仿真平台研究.pdf.pdf 免费下载

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

南京航空航天人学硕+ 论文 摘要 柔性制造系统( 1 7 1 e i b l em a n u f a c t u r i n gs y s t e m ) 是一类极其复杂的离散事件动 态系统i s c f b t ee v e n td y n a m i cs y s t e m ) 。针对f 惦的研究涉及很多方向,其中f m s 调度问题是最基本的研究方向之一。f m s 生产的高柔性和高效率在很大程度上取决于 f m s 调度的水平。f m s 调度的实质就是作业任务与资源的优化匹配,这类调度问题属 于n p h a r d 问题。国内外很多学者提出了很多调度理论用于f m s 调度,但是迄今为止 还没有通用而高效的调度方法。 本文围绕f m s 优化调度问题,对f m s 建模、调度和仿真进行了较为深入的研究。 在文中,首先发展了扩展对象p e t r i 网( e x t e n d e do b j e c t o r i e n t e dp e t r in e t ) 模型 用于进行f m s 建模,提出了基于e o p n 的四个步骤的f m s 建模方法论:接着实现了基 于启发式图搜索的f m s 车| 白_ j 调度算法,算法结合p e t r i 网和基于人工智能的启发式搜 索算法,通过生成并搜索调度p e t r i 网的可及图来寻找最优的调度方案:实现了一体 化f m s 仿真实验平台的系统原型,它能够为用户提供一个类似于实际f m s 的仿真环境, 其中集成了建模软件、实验设计软件、仿真执行软件、结果分析软件等功能软件;最 后在仿真平台上实验了基于调度p e t r i 网模型和启发式搜索算法的f m s 调度算法。 关键词:柔性制造系统:车阳j 调度:p e t r i 网;启发式搜索算法 基 :e o p n 和启发式搜索算法的f m s 仿真平台研究 a b s t r a c t f l e x i b i em a n u f a c t u r i n gs y s t e mi sa t y p i c a lr e a l t i m ed y n a m i cd i s e r e t e e v e n ts y s t e mc o m p o s e do fan u m b e ro fc o m p u t e r c o n t r o l l e dm a e h ir l e s a u t o m a t e d m a t e r i a lh a n d l in ga n ds t o r a g ee q u i p m e n t s t h e s ep h y s i c a le 1 3 t i t i e so p e r a t ea s a n i n t e g r a t e ds y s t e mu n d e rt h ec o n t r o lo ft h ec o m p u t e rs o f t w a r es y s t e r n f h e g r o w i n gd e m a n df o rh i g h e rp e r f o r m a n c ea n df l e x i h i 1i t ya n dt h ei n t e r i o c k i n g f a c t o r so fc o n c u r r e n c y ,e v e n t d r i v e na c t i v i t i e s ,r e a l t i m ed e c i s i o n m a k i n g p o s e sas i g n i f l c a n tc h a i l e n g et of m sd e s i g n ,e s p e e i a i i yi nt e r m so fc o n t r 0 1 a n ds c h e d u l i n g t i l ec e m b i n a t i o no fp e t r in e t sa sa n a n a l y s i s t o o l f o rd i s c r e t e e v e n t d y n a m i cs y s l e m sa n da r t i f i c i a li n t e l l i g e n c eh e u r i s t i cs e a r c hh a sb e e ns h o w n t ob eap r o m i s i n gw a yt os o l v ef m ss c h e d u l i n gp r o b l e m s h o w e v e r t h en ph a r d n a u r eo ft h ep r o b l e mo b s c u r e st h ep e t r in e tc a p a b i l i t y0 fy e a s o l l i n ga h o t l t t h e ) e h a v i o ro ft h es y s t e m s , i nt h i sp a p e r ,e x t e n d e do b j e c 卜o r i e n t e dp e t r in e ti sd e v e l o p e df o rm o d e l j n g f m s a f t e rf m sm o d e l i n gp h a s e ,h e u r is t i cs e a r c hf o r m u l a t e st h es c h e d u l i n s p r o b l e mb a s e do np e t r in e tm o d e l t h e n 。i tg e n e r a t e sa n d s e a r c h e sap a i 、t i a l r e a c h a b i l i t yg r a p ht o f i n da no p t i m a lo rn e a ro p t i m a lf e a s i b l es c h e d u l ei n t e r m so ft h ef i r es e q u e n c eo ft h et r a n s i t i o n so ft h e p e t r in e tm o d e l s o m e h e u r is t i cf u n c t i e l - i sf o re f f i c i e n ts e a r c ha r ee x p l o r e da n dt h ee x p e r i m e n t a l r e s u lt sa r ep r e s e n t e d a tt h ee n do ft h i sp a p e r ,a ni n t e g r a t e df m ss i m u l a t i o n p l a t f o r mi sp r e s e n t e d t h i sp l a t f o r mi n t e g r a t e st h ew h o l es e q u e n c eo fm o d e i i n g a n ds i m u l a t i o np r o c e d u r e t h es c h e d u l ea l g o r i t h mb a s e do n h e u r i s t i cs e a r c h a n dp e t r ib e ti st e s t e di nt h i ss i m u l a t i o np l a t f o r m k e yw o r d s :f l e x i b l em a n u f a c t u r i n gs y s t e m ;j o bs h o ps c h e d u i n g :p e t r i n e t h e u r is t i cs e a r c ha l g o r i t h m 南京航空航天人学硕十论文 第一章绪论 1 1 课题的研究背景和意义 1 1 1 柔性制造系统概述 柔性制造系统( f 1 e x i b l em a n u f a c t u r i n gs y s t e m ) ,通常简称f m s ,是从6 0 年代 丌始发展起来的- - 4 十自动化制造系统。f m s 是指在计算机控制下的,由自动化物料运 送系统连接起来的一组数控加工设备,用以制造一族零件。世界上公认的第一条柔 性制造系统是英国m o l i n s 公司1 9 6 7 年建立的“m o l i n s 2 4 ”。8 0 年代以来,f m s 在世 界范围内得到了广泛的应用,f m s 技术渐渐成熟。 f m s 拥有流水车间( f 1 0 ws h o p ) 的高效率和作业车阳j ( j o bs h o p ) 的高柔性,特别 适用于多品种、小批量产品的生产。f m s 能够以较高的设备利用率、较低的生产成本、 较高的生产质量、较短的生产周期适应快速变化并且竞争激烈的市场需求。 f m s 同时也是一个非常复杂的系统,它的复杂性主要体现在: ( 1 ) 离散性:在f m s 的生产过程中,系统的状态变化都在离散时刻发生,而传 统的以差分方程或者微分方程为基础的数学模型不适用于描述这种离散系统。另外, f m s 离散的状态空间所导致的组合复杂性以及人造系统的“组织有序”的不确定性在 f m s 的运行中得到了充分的体现。 ( 2 ) 柔性:柔性是f m s 的根本特征和优点同时也造成了f m s 比传统制造系统 在控制和调度上更为复杂。f m s 可以同时加工多个类型的产品,每个产品的在f m s 中 可以有多个不同的加工路径。f m s 所具有的这种加工柔性,使得基于f m s 的调度计算 复杂性大为增加。 ( 3 ) 集成:软硬件资源的高度集成是f m s 高效率的基础。但是,集成度的提高 使得系统各个部分之1 - b j 的关联非常紧密,从而造成各种生产活动相互之问的复杂关 系,比如并发、冲突、异步、资源共享等。对于f m s 而言,系统中各个资源的协调非 常关键。 ( 4 ) 资源约束:一个f m s 中的各种资源,比如托盘、央具、缓冲站、机床等都 存在着容量或者应用范围的限制,所以在f m s 的设计过程和运行过程中必须考虑各种 资源约束条件。 ( 5 ) 不确定性:由于f m s 运行过程中,各种外部干扰( 比如生产任务的更改) 、 内部干扰( 如机床故障) 和人为因素的存在,使得系统具有很多不确定性。某些不确定 性很难通过概率统计的方法来描述。 基丁e o p n 和启发式搜索算法的f m s 仿真平台研究 1 1 2 f m s 建模、调度、仿真的意义 由于f m s 的丌发和建造需要大量的投资和时| 1 白j 的消耗,所咀在建造系统之前, 必须进行有效的规划设计,建立符合实际的系统模型,预测系统的经济效益,得到系 统的性能指标,从而避免因为设计不妥而造成的重大损失,保证所设计的系统在较优 的状态下运行,以达到预期的要求,缩短建造系统的周期,降低风险。建立能够真实 的反映f m s 运行情况的模型是f m s 研究、规划设计、运行管理和生产调度的关键。 f 她的建模是一项困难的工作,尤其是针对复杂的f m g 。 同时,为了保证将来系统能够实现最优化的生产调度,必须进行f m s 生产调度 方案的寻优研究。一般束说,理论上研究的车间调度问题都是对实际生产环境中的复 杂的、动念的、随机的、多目标的调度问题的简化和抽象。目前为了解决车侧调度 问题,有两大类比较常用的生产调度方法:一类是基于规则的调度,这种调度方法根 据一定的规则和策略来确定生产系统中的下一步操作:另一类是基于模型的调度,即 首先定义调度问题,然后为调度问题建立调度模型,依据模型运用特定的调度算法求 解优化值,确定调度方案。 车阳j 调度问题是在等式或者不等式约束下寻求性能指标的优化,在计算量上通 常是n p 完全( n o n d e t e r m f n f s t f cp o l y n o m f c a l b o u n d e r sc o m p l e t e ) 问题“。”,郎随着 渊度问题规模的扩大,寻求最优解的计算量呈指数规模膨胀,很难在多项式的有效时 斛内求解出最优值。最初,解决车间调度阃题的研究方法主要集中于整数规划、简单 舰则的应用等,但是随着调度问题规模的扩大,这些方法往往难以取得理想的结果。 近年来,相关学科的发展和交叉催生了许多全新的车间调度领域的优化方法,比如遗 传算法、神经网络、模拟退火算法、禁忌搜索、p ec r i 网算法等。这些新的研究方法 的出现加上r 益强大的计算机计算能力的配合能够更好韵解决这类复杂的k p 完全问 题。 f m s 是一个复杂的动态离散系统,系统运行时产生的复杂的相互约束关系和资源 冲突以及信息的交流使f m s 动态特性分析工作变得异常困难。对于f m s 进行i j 念特性 的分析,采用一般的规划和设计方法不是难以得到最优的分析结果,就是费用太过高 昂。随着计算机性能以及动画技术的发展,动态系统的计算机仿真技术渐渐成熟”1 。 计算机仿真技术通过对已经建立的系统模型进行大量仿真实验来获得系统的各种动 态信息,展示系统长期运行将会产生的各种现象。通过计算机仿真技术对于模型进行 动态仿真,能够进行各种方案的优化和论证,以达到合理设计、减少投资和提高效益 的目的。 南京航空航天人学硕+ 论文 1 1 3f m s 建模、调度的国内外研究现状 f m s 属于典型的离散事件动态系统( d i s c r e t e e v e n t d y n a m i cs y s t e m ,简写为 d e d s ) 。d e d s 的系统状态由一些具有离散值的数字量、逻辑量或符号量表征,而且状 态的变化仅在离散时刻发生。在d e d s 的研究中,最为迫切需要解决的问题就是如何 建立简明、有效和通用性强的d e d s 模型。目前,用于d e d s 的建模方法可以分为三大 类:分析法、仿真法、图模型法。 ( 1 ) 分析法:分析法足以数学模型为基础,利用数学工具进行模型求解的方法。 6 0 年代,排队论被用于描述f m s 的某些问题,如1 9 6 1 年l i t t l e j d c ”1 教授提 出l i t t le 定律。7 0 年代以来,数学规划被用于制造系统建模。e b a l a s ”1 教授使 用整数舰划来解决f m s 中的任务分派问题,v g r i n iv a s & n ”1 教授提出用动态规划法 ,采解决f 螨运行中的问题。同时,以哈佛的y c t i o 。1 等为首研究者们刨立了扰动 分析法,利用扰动分析法对d e d s 进行建模和分析。这类方法具有孥实的数学基础, 所得的模型通常比较精巧,求解过程也比较简洁快速,但是缺点是为了简化模型假设 过多,使得模型的f 确性和结论的准确性有所下降。 ( 2 ) 仿真法:通常况的仿真是以排队论为基础对系统的统计模型进行数字动态 仿真,它将系统运行看作一系列事件的集合,用事件的产生和消失来描述系统状态的 变化。s c h r i b e r t j ”3 等研究者们于7 0 年代就开始使用专门的仿真语言g p g s 来描述真实系统,仿真系统运行。仿真方法比较灵活,可以根据想要达到的研究目标 柬设计模型的复杂程度,以实现模型f 确性和建模费用之间的平衡。 ( : ) 图模型法:以p e t r i 网为代表的图模型法8 0 年代以来被广泛的应用于f m s 建模。1 9 6 2 年,德国c a p e t r i 。”博士在他的博士论文中提出p e t r i 网理论t 它 以图形方式描述同步和异步并发系统,形象地表示了离散事件动态系统中的各种事件 以及状态变化之削的关系。几十年来,p e t r i 网理论得到很大发展,m a r s a n 、b a l b o 、 c o n t e 1 提出了广义随机p e t r i 网,允许p e t r i 网中存在两种不同性质的变迁发送 一立即变迁( h n m e d i a t et r a n s i t i o n ) 和指数变迁( e x p o n e n t i a lt r a n s i t i o n ) 。j e n s e n “:提出了着色p e t r i 网,将多个相似的库所( 或变迁) 合并成革个库所( 或变迁) ,并 给合成的库所和变迁赋予不同的颜色,有效减少了p e t r i 网的库所和变迁的数目。 利用p e t r i 网建立f m s 模型有如下特点: ( 1 ) p e t r i 网可以用直观的图形来描述复杂的控制结构和系统行为以及状态变 化的动态过程。 ( 2 ) 利用p e t r i 网描述带有随机、并发和异步性质的事件2 _ 1 白j 的前后关系和相 互作用,研究任务调度和工作排序的操作策略; ( 3 ) 利用p e t r f 网模型的可执行性实现评价各种控制和调度策略的仿真工具; f 4 ) 利用p e t r i 网的分析能力解决死锁的探测和系统性能评价。 基于e o p n 和启发式搜索算法的f m s 仿真平台研究 f m s 综合了传统的j o bs h o p 的高柔性和流水线生产的高效率。在f m s 中,一台 机床可以选择加工多种不同的工件,同时工件也可以选择多个不同的机床进行加t , 加1 二路径的选择和资源的调度对于系统运行性能的优劣起到至关重要的作用。几十年 束,国内外的学者们从不同的角度发展出不同的调度方法。从双机调度的j o h n s o n 方法到排队论( q u e u e i n gt h e o r y ) 、整数规划( i n t e g e rp r o g r a m m i n g ) 、扰动分析法 ( p e r t u r b a t i o na n a l y s i s ) 、计算机模拟( c o m p u t e rs i m u l a t i o n ) ,研究方法不断深入, 研究列象趋于复杂。近些年来,由于多学科的交叉,基于神经网络( n e u r a ln e w o r k s ) 、 模拟退火算法( s i m u l a t i o na p p e a l ) 、遗传算法( g e n e t l ca i g o r i t h m s ) 、禁忌探索( t a b u r e s e a r c h ) 以及p e t r i 网等的调度理论和方法层出不穷。针对f m s 调度的研究趋于多 元化。 p e t r i 网理论非常适用于f m s 的动态调度。由于p e t r i 网用图形方式精确的表示 出了系统中的活动、资源、约束,因此设计者可以更好的理解和分析调度问题。l a r s o n 和o d o n i ”详细的论述了图形化调度模型的优点。 经过多年的发展,p e t r i 网应用于解决调度问题取得了一定的进展。o n a g a1 。“在 p e t r i 网建模的基础上,用线性规划法来生成生产系统的阶段调度方案。s h e n ”综 合分枝定界法和p e t r i 网理论柬寻求最优的调度方案。z h a n g “使用 p r e d i c a t e t r a n s i t i o n 网络模型柬表达生产系统的规则,同时应用人工智能算法来 寻求最优调度。d o oy o n gl e e “”将p e t r i 网和启发式搜索综合起来研究调度问题。 1 2 课题的主要研究内容 本文对于f m s 建模、调度、仿真进行了较为深入的研究。使用扩展对象p e t r i 网( e o p n ) 理论针对f m s 进行建模,提出了基于e o p n 模型的四个步骤的f m s 建模方法 论;利用p e t r i 网为f m s 调度问题建立调度模型,通过基于人工智能的启发式搜索算 法搜索调度p e t r i 网模型的可及图来寻找一条最优或者近似最优的路径,从而获得最 优的调度方案;在e o p n 建模基础上实现了一体化f m s 调度仿真平台,并且在仿真平 台上实验了基于调度p e t r i 网模型和启发式搜索算法的f m s 调度算法。本文的主要内 容以及章节安排如下: 第一章介绍了柔性制造系统的基本概念,结合国内外的研究指出了f m s 建模、 调度、仿真的意义,提出了论文的主要内容。 第二章中首先简要的介绍了p e t r i 网的基本理论,在指出p e t r i 网用于f m s 建 模的缺点的同时给出对象p e t r i 网( o b j e c t o r i e n t e d p e t r in e t ) 的定义,并且在对 象p e t r i 网( o p n ) 基础上进行了适当的补充,提出了扩展对象p e t r i 网( e x t e n d e d o b j e c t - o r i e n t e dp e t r in e t ) 模型。 南京航空航天大学硕十论文 第三章中提出了基于扩展对象p e t r i 网( e o p n ) 模型的四个步骤的f m s 建模方法 论,利用实例详细论述了基于扩展对象p e t r i 网( e o p n ) 的f m s 建模过程。 第四章中利用调度p e t r i 网模型对f m s 调度问题进行建模,在此基础上实现了 基于启发式搜索的f m s 车间调度算法,算法通过对调度p e t r i 网的可及图搜索来寻找 最优的调度结果。 第五章中实现了基于扩展对象p e t r i 网( e o p n ) 模型的一体化f m s 调度仿真平台, 并在仿真平台上验证了第四章提出的基于调度p e t r i 网和启发式搜索的f m s 调度算 法。 1 3 本章小结 柔性制造系统的建模、调度、仿真经过多年的发展,已经取得了相当显著的成 绩。但是现有的f m s 建模技术,在模型的描述能力以及理论分析上仍存在这样或那样 的缺陷。本章在对于f m s 建模、调度和仿真技术进行总结和分析评价的基础上r 提出 了本文的主要研究内容。 基te o p n 平启发式搜索算法的f m s 仿真平台研究 第二章扩展对象p e t r i 网模型 2 ip e t r i 网的基本理论 p e t r j 网是德国学者c a r la d a mp e t r i 在他的博士论文+ 中首先提出来的。作 为一种图形和数学建模工具,p e t r i 网既能够对并行( p a r a l l e l i s i n ) 、并发 ( c o n c u r r e n c y ) 、同步( s y n c h r o n iz a t i o n ) 、资源共享( r e s o u r c es h a r in g ) 等特性建立 模型并使之形象化,又能够对系统的动念性质( 有界性、安全性、活性、可达性、可 逆性等) 进行分析。经过几十年的发展,p e t r i 网理论得到了极大的丰富,并被广泛 的运用于许多领域”。 2 1 1p e t r i 网的基本定义 对一个离散事件动态系统建模,首先需要考虑系统的状态以及状念转移。p e t r i 网包含了两种集合,一种是库所( p l a c e ) 表示系统状态,另一种是变迁( t r a n s i t l o n ) 表示系统转移。库所和变迁分别以圆圈和短直线表示,库所与变迁之问用加权流动关 系( w e i g h t e df 1o wr e a t i o n ) 联系。 定义2 1一个p e t r i 网是一个4 元组( j d ,t ,f ,w ) ,其中: j d = p l ,p :,p 。) 是库所的集合 t = ,! ,一,。,) 是变迁的集合; ,n7 1 = o ,库所和变迁是分离的集合 f c p 7 1 ) u ( t p ) 为有向弧的集合: 表示有向弧的权。 定义2 2p e t r i 网可分解为一个4 元组p ,t ,i n ,o u t ) ,其中 p = p l ,p :,p ,) 为库所集; t = ,! ,一,。) 为变迁集; p 【j7 1 巾;p n r = 巾; 南京航空航犬人学硕十论文 j 为非负整数集合,i n :( p x7 ) 斗为输入函数 j 为非负整数集合,o u t :( p t 1 _ 为输出函数。 可以用影响矩阵( i n c i d e n c e l a t r i x ) 来表示输入矩阵倒和输出矩阵优7 兀对于一 个具有m 个库所和门个变迁的p e t r i 网,其刷和0 0 t 均为x 门的矩阵。 对于输入矩阵讹( i n ) ,= i n ( p ,f ,) : 对于输出矩阵倒l ( o u r ) ,= 0 u t ( p 。,t ,) ; 图2 1p e t r i 网例图 图2 1 所示的p e t r i 网的输入和输出矩阵分别是: n = 11 o1 0o 0o 0 0 o 00 0 00 10 0 o1 o1 o 0 0 u 7 1 = o o 0 o 0 0 0 0 oo 1o0 o o oolo1 0010 0 o1ol0 输入矩阵和输出矩阵用数学方法完全描述了p e t r i 网。 定义2 3 如果p e t r i 网不存在自环,则称这个p e t r i 网为单纯p e t r i 网( p u r e p e t r in e t ) 。单纯p e t r i 网可以用一个矩阵完整的描述称为单影响矩阵( s i n g l e i n c i d e n c em a t r i x ) ,定义如下: c = 0 u t i n 单影响矩阵f 中,如c ,为:_ f ,则9 ,为0 的输出:如巳为负,则p r 为t j 的输出。 g ,的绝对值为相应的弧的权值。 图2 1 所示的p e t r i 网的单影响矩阵为: 基丁e o p n 和启发式搜索算法的f m s 仿真平台研究 一1一l 0一l 10 oo o0 o1 00o o0o 一100 111 110 011 定义2 4 对于库所n 和变迁t ,分别定义: ,n 输入变迁:i t ( p ,) = r ,7 1 ,o u t ( p ,t ,) o ; 卢,输出变迁:o t ( p ,) = f ,t :i n ( p ,t ,) o : f ,输入库所:伊0 ,) = p ,p :,r ,) o ) ; ,输出库所:o p ( ,) = p ,尸,o u r ( p ,r ) o ) 。 定义2 5p e t r i 网使用标记g ( m a r k i n g ) 来进行动态描述,p e t r i 网的标记, 4 i 是 由p e t r i 网中每一个库所的一个非零令牌( t o k e n ) 数组成的向量。如果p e t r i 网有月 个库所,则标记为一个n x i 向量。标记的第j 元素m ( i ) 表示库所p ,的令牌数。 标记就是p e t r i 网所描述的离散动态系统的状态向量。 m = 1 4 ( 1 ) ( 2 ) m 0 1 ) m 0 ) , 2 1 2p e t r i 网激发规则 定义2 6 对于给定的p e t r i 网标记腻如果变迁t j 的每一个输入库所的令牌数 不少于输入弧的权,即 印,胪0 ,) ,v ( p ,) 删b 。t ) 则称变迁t ,使能( e n a b t e d ) 。 定义2 7 当一个标记中的使能变迁t ,发送,则生成一个新的标记7 。 印,e 尸,肘( j ! ,) = m ( p ,) + 0 u t ( p ,) + 切,) ; 称7 是可及的( r e a c h a b e ) 。标记为m 与m 。 定义2 8 对于系统的初始状态,若同时有多个变迁使能,则发送不同的变迁, 由腻而可及的标记自然不同,将可及的不同的标记的集合称为可及集 l 。r e a c h a b i 、i t ys e t ) 记稀r j 。 定义2 9 对于初始标记为此的p e t r i 网,可及图表示了p e t r i 网中所有可能可 8 南京航空航天人学硕士论文 及的标记。可及图为一个有向图( v ,e ) 其中v = r i m 。 是有向图节点的集合,而f 是有向弧的集合。 2 1 3p e t r i 网的基本性能定义 对于所有的m r m 。1 和其中的一个变迁“如果可及集中某一标记可使f 将来 使能( e n a b l e d ) ,则称f ,为活的( l i r e ) 。如果p e t r i 网中的全部变迁都是活的,则称 此网为活的。 p e t r i 网的活性( l i v e n e s s ) 与p e t r i 网所表示的离散动态事件系统的有无死锁是 相互关联的。如果p e t r i 网为活的,则表示系统在运行时无死锁:反之,系统在运行 时有可能进入死锁状态。 如果满足v m r i m 。】,3 k 0 ,m ( p 。) k ,则称库所p ,在初态中为k 界限a 如果k = 1 ,则称库所n 是安全的。如果在腻中的所有库所均为k 界限( 或者安全) t 则称p e t r i 网在腻中是有界限的( 或者安全的) 。 界限( b o u n d e n e s s ) 表征了p e t r i 网状态空问的有限性。如果p e t r i 网为有界限, 则p e t r i 网所表示的系统不会发生溢出。比如,在制造系统中的一个有限容量的缓冲 区( b u f f e r ) 只能表示为一个有界限库所,有了界限的限制,可以保证系统在运行时不 会出现过载。 安全( s a f e n e s s ) 表示一个库所中仅有小于等于1 的令牌数。如果p e t r i 网中某个 库所表示了实际系统中的某个操作,而且此库所是安全的,则表示在进行此操作的同 时不能同时丌始进行另一操作。比如,一个库所如果代表一个同时只能加工一个工件 的机床,则此库所安全。库所的安全性保证了此机床在当前工件的加工没有结束之前, 不能同时加载另外一个工件进行加工。 如果满足v m 尺【m 。】,m 。r i m ,则称具有初始状态的p e t r i 网是可往复 的( r e 。e r s i h le ) 。往返性保证了系统能够从任何状态( 包括失败状态) 回复到初始状 念。 2 1 4p e t r i 网的可及图 p e t r i 网的可及图( r e a c h a b i li t yg r a p h ) 表示了网中所有可及的标记( m a r k i n g ) 的组合。从初始标记丌始,激发一连串的使能的变迁,将会产生一系列新的标记, 这些新的标记可以按照变迁激发的顺序组成一个以初始标记脱为根的有序的树状结 构,这个标记结构被定义为可及图。 9 基丁e o p n 和启发式搜索算法的f m s 仿真平台研究 j ,j t f 、,0 、斗。- 。j , ) 黔毒 : 。手 ;、 i? 图2 2p e t r i 网图 图2 2 所画的p e t r i 网的初始标记m 。= 0 010 0 0 o r ,同时使能的 变迁为t ,t 。f ,。 图2 3 可及图 通过可及图,清楚的看到p e t r i 网系统由初始状态通过激发链 ,t ,t 。 ,经 过标记集 掘膨,枷,运行完毕。而通过激发链 “,如 和 胡,则会产生死锁( 双圆坏 表示死锁状态) ,系统运行中止。 p e t r i 网的界限和活性很难进行定量的计算,所以基本的p e t r i 网分析方法就是 分析可及图。可及图中的每个节点都代表了网络的可及标识。如果p e t r i 网中每个节 点都是可及标识而且节点的数目有限,则p e t r i 网有界限;而p e t r i 网在运行中是否 可能发生死锁可以从可及图中标记树的生成情况清楚看出来。 氐缈 u 、 , , f一 j b岁。 ,、, 南京航空航天大学硕士论文 2 2 对象p e t r i 网 2 2 1 p e t r i 网建模的缺陷 由于p e t r i 网有坚实的数学基础作为依据,能够比较精确地描述离散并发系统的 结构,系统事件之问的顺序或并发关系、资源的约束、事件发生的条件以及引起的后 果,并能够进行有效的系统分析和仿真,因而被广泛的应用于f m s 这类复杂离散系统 的建模和仿真。但是利用普通的p e t r i 网来描述f m s 有以下几点不足”“: 第一:“封闭”问题:p e t r i 网系统是一个封闭的网系统,对外没有明确的输入和 输出,它的动态行为是由它们内部状态的各种可能变化以及这些变化之间的关系刻画 的。但是实际的f m s 系统之间相互联系,而且肯定拥有输入和输出。用p e t r i 网对 f m s 建模,当然不能将f m s 描述成一个没有输入和输出的封闭系统。 第二:状态空间的“指数爆炸”问题:p e t r i 网模型在f m s 建模应用中的另外一 个困难是网系统中节点太多,而状态空间的规模随着网节点的增加而呈指数增长。利 用计算机软件分析拥有庞大的状态空间的系统动态特性和输入输出都非常的困难。因 此在对f i s 进行建模时,应当考虑对p e t r i 网方法进行简化。 第三:模型的转化非常困难:前两个问题都是系统建模和分析的问题,而模型的 转化就是指系统p e t r i 网模型建立之后,如何将系统的p e t r i 模型转化为f m s 的计算 机控制系统,或者如何根据模型进行计算机控制系统程序的设计,这是一个系统的实 施问题。目前p e t r i 网还没有解决该问题的好办法,而往往是重新进行程序系统设计。 这些问题的解决需要对基本p e t r i 网系统进行扩展和改造。在本小节以及下一小 节中在对象p e t r i 网( o p n ) 的基础上引入扩展对象p e t r i 网( e o p n ) ,基本解决了p e t f i 网的“封闭”问题并部分缓解了状态空间膨胀过快问题,在第三章中,通过将系统 e o p n 模型映射为u m l 模型为解决模型转化困难的问题提供了一个新的思路。 2 2 2 对象p e t r i 网定义 普通p e t r i 网面向加工流程建模,对于系统和流程有很大的依赖性,进行规模较 大的f m s 建模时,容易导致网规模膨胀过快,而且不具备现代制造系统控制模型所需 的模块化、可重用、易维护等特征。 面向对象的建模方法是一种围绕真实世界的概念来组织模型的全新的思考问题 的方式,它将系统看成是一系列离散的对象集合。在这些对象中既包括数据结构,也 包括实体行为。面向对象的建模方法能很好的解决复杂系统的建模问题,而且建好的 模型具有良好的可重用性。w a n g 综合了p e t r i 网和面向对象技术,提出了对象 p e t r i 网的概念。 l l 基 e o p n 利启发式搜嘹算法的f n s 仿真平台研究 为了解决模块化和可重用性问题,对象p e t r j 网技术得到了关注”“。它面向制 造系统的物理布局建模,将目标系统映射为一个个相互协作的对象,将离散动态事件 系统中存在的同步约束从对象内部分离出来,同时为了提高模型的可维护性和可重用 性,对象p e t r i 网利用了信息隐藏机制使得每个对象的内部实现细节不为外界所知, 而只对外提供其调用接口。 从面向对象方法学的角度来看,制造系统由一系列的实体对象以及对象之间相交 互的关系组成。系统可以为定义如下二元组: 7 s = ( o s ,r ) : 其中: o s = 0 1 ,0 2 ,p , 为对象p e t r i 网o p n ( o b j e c t o r i e n t e dp e t r in e t ) 模型的集 合; 口为对象p e t r i 网o p n 模型; 斤为对象p e t r i 网o p n 模型之间的信窟、交互。 o p k 被定义为个六元组: 0 = ( 只,i ,i n ,o u r , ,o m 小 其中: p = ( p ,p 。,p 。) 是o p n 的有限库所集合: z = o l ,。) 是o p n 的有限变迁集合: j e ) u t 中;p n t = 中; 删:( p t ) _ + ,是输入函数,描述了从库所指向变迁的有向弧一1 为非负整数, 表示弧的权: o u t :( t p ) 呻n ,是输出函数,描述了从变迁指向库所的有向弧: 删是信息输入库所的有限集台: 俐是信息输出库所的有限集合。 系统中物理资源的动态行为由资源内部的状态转移和资源外部的信息传送组成。 在对象p e t r i 网o p n 模型中,使用库所和变迁来表示资源的状态转移。 在实际的f m s 系统中,各个实体资源之白j 存在着信息流。信息流是由物料在加工 过程中与加工设备、运输设备等相结合时产生的,比如加工设备“忙”、“闲”等加工 状态的转换信息以及各个资源之怕 、资源同上层控制系统之间的信息交互。普通的 p e lr i 网比较“封闭”,不能反映各个资源之间的信息流动。在o p n 中引入信息输入 输出库所和信息令牌来表示资源之侧的信息传送。 南京航空航天大学硕士论文 信息传递关系见,被用来表示不同对象口和口之间的信息交互。尼,为一三元组 r 。= ( o m ,g ,a 其中:咧为o p n 模型臼的信息输出库所; 瑞为o p n 模型谚的信息输入库所: g 。、昌:为o p n 模型口和e 之间的门( g a t e ) 。 g l l 图2 4o p n 之间的信息令牌交互 各个o p n 模型之削传递的令牌被定义为信息令牌( m e s s a g et o k e n ) 。信息令牌由 信息输出库所流出,从信息输入库所流入,其流通由门的激发与否来控制。 o p n 模型在引入了信息输入输出库所之后,模型内部变迁的激发改由这个变迁 的内部输入库所和信息输入库所共同决定:当这个变迁的每个内部输入库所和信息输 入库所的令牌数大于等于输入弧的权,则变迁激发使能;同理,当一个内部变迁激发, 则于其相连的内部输出库所和信息输出库所同时获得令牌。如图2 4 所示,当日的 信息输入库所删和库所n 同时拥有令牌,则变迁t 。使能并激发;如果门蜀。使能, 信息令牌可以从织的信息输出库所绷流向毋的信息输入库所删。 2 3 对象p e t r i 网的扩展:e o p n 根据第2 2 小节对对象p e t r i 网的定义,o p n 中的库所只表示实体资源的状态, 变迁f 表示实体资源的活动即状态的转移,输x 输出信息库所埘,渊表示不同o p n 单元之间的信息交互。 但是实际生产系统中,物料流和信息流是并行的。物料流主要是工件根据加工工 艺的要求,按照一定的时间、空间顺序与加工设备、运输设备相结合,完成其加工过 程,实现在f m s 中各个设备之间的流动。 在o p n 模型中,通过输入输出信息库所和信息令牌来反映各个模型之间的信息 流动,但是无法表示出各个实体资源之间的物料流动。因此本文提出了扩展对象 p e t r i 网( e x t e n d e do b j e c t o r i e n t e dp e t r in e t ) 理论,对o p n 模型进行适当的扩展, 基t e o p n 和启发式搜索算法的f m s 仿真平台研究 在模型中另外增加工件输入输出库所和工件令牌来表达各个实体资源之阳j 的物料流 动。添加了工件流之后的e o p n 模型基本上解决了p e t r i 网的“封闭”问题,基于e o p n 的系统模型中各个模块之间的输入和输出表达清晰。 扩展对象p e t r i 网仍然被定义为一个六元组: e o r = ( e e , ,r ,e i n ,e o u t , ,o m ) ; 对o p n 模型中的库所、输入函数、输出函数进行了扩展。其中: e 尸= ( 尸,俨f ) 为e o p n 的库所集合,其中: p = ( p p :,a ,p 。) 是e o p n 的内部状态库所集合,同原定义相同: 川= ( 皿”1 肥”“。) 是e o p n 的工件的输入输出库所集合,指明了工件流入和流出; 。垆是工件输入库所( j o bi n p u tp l a c e s ) ; 肥。“是工件输出库所( j o bo u t p u tp l a c e s ) ; e ,= i n ,删 是e o p n 中从库所指向变迁的有向弧集合,其中: n :( p t ) 呻,是输入函数,描述了从内部状态库所指向变迁的有向弧,为 非负整数,表示弧的权; ,_ ,为从工件输入库所只到内部变迁的有向弧,定义为工件输入弧; e o u t , = 0 呱,j o u t ) 是e o p n 中从变迁指向库所的有向弧集合,其中: o u t :( t x p ) 斗n ,是输出函数描述了从内部变迁指向内部状态库所的有向弧: 倒盯为内部变迁指向工件输出库所肥“的有向弧,定义为工件输出弧; 删是信息输入库所的有限集合; 渊是信息输出库所的有限集合。 在扩展对象p e t r i 网e o p n 定义中,为了表达各个实体资源之间的物料流动所以 增加了工件输入输出库所、工件输入输出弧的概念。如图2 5 所示,库所刷为工 件输入库所胛”,库所o u t 为工件输出库所卯”“,库所m 到变迁一的激发弧

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论