（机械制造及其自动化专业论文）基于petri网的fms调度问题研究.pdf

摘要 摘要 随着市场竞争的加剧和客户需求的多样化，计划与调度在现代制造系统中扮 演着越来越重要的作用。由于柔性制造系统中存在异步、并发、资源共享、路径 柔性等关系，因此对该类系统的调度是十分复杂的问题。本文从系统的p e t r i 网建 模方法与调度算法两方面入手，对柔性制造系统调度中的有关问题进行了深入研 究，提出了一些模型和算法。主要成果有： 1 以f m s 的p e t r i 网模型的可达图为对象，在b f b t 搜索算法的基础上，与 动态搜索窗技术结合，提出了一种混合启发式搜索调度算法。使用b f 法可以保证 调度质量，使用b t 可实现快速回馈，使用动态搜索窗可以控制系统规模，提高运 行速度。实例计算表明该算法可快速获得较好的调度结果，可用于较大规模f m s 的调度问题。 2 研究了具有交货期的f m s 的调度问题。基于p e t r i 网建立了一种以总拖期 最小为目标的调度模型，在动态分解交货期理论的基础上，建立了以各工件总拖 期最小为指标的启发函数，引导b f 算法完成调度过程。 3 采用无向p e t r i 网对a g v 系统路径布局进行建模，与t i m e 谢n d o w 结合建 立基于时间的可达状态图。将调度的方法用于双向通行的多a g v 系统的路径优化， 并以b f 搜索方法为基础，以下一步路径的状况作为确定目前状态的依据，提出了 时间最短的路径优化算法。研究了在存放工作站和设备停靠点两种驻留方式下多 a g v 系统的最优路径算法，并提出了一种基于d u e 一缸e 的a g v 选择及路径优化 算法。 4 针对a g v 采用随行分派、分散分派与分布共享分派策略，分别建立了工件 与a g v 同步调度的f m s 的p 嘶网模型，建立了分布共享策略下选择a g v 的p e t r i 网模型，以实现对a g v 分派与路径的优化控制。使用混合启发式搜索算法对各种 策略下的实例进行了计算，并分析比较了采用各种策略的调度效果。 5 、在集成a g v 的f m s 的基础上，进一步研究了考虑a g v 系统路径交通状 况下的调度问题。对于a g v 采用不同的分派策略，相应地建立了考虑路径系统的 集成的f m s 的p e t r i 网模型。重点研究了a g v 采取分布共享分派策略下考虑路径 系统的f m s 调度问题。分别以最优路径算法和基于d u e d a t e 的a g v 选择及路径 优化算法为基础，提出了两种不同的调度方法，并分析比较了不同情况下两种算 法的调度结果。 关键词：柔性制造系统，调度，模型，启发式搜索，p e t r i 网，a g v ，交货期 a b s t r a c t a bs t r a c t d u et os t i f rc o m l ) e t i t i o ni i lt o d a y sm a r k e t p l a c ea n dd i v e r s l f i e dc u 咖m e rd e m 锄d s s c h e d u l i n ga r ep l a y i n gm o r ci i i l p o r t a n tr 0 1 e s i nm o d e ma u t o m a t e dm a i l u f a c 嘶n g s y s t e m s ，n l es c h e d u l i n gp r o b l e m so fn e x i b l em 锄u f a c 缸n gs y s t e m s ( f m s ) a r ev e 巧 c o m p l e xb e c a u s eo fs o m ec 0 m p l i c a t e dr e l a t i o n s h i p se x i s t i i l gi i l as y s t c ms u c h 雒 a l s y n c h r o l l i s m ，c o n c u r r e n c e ，r e s o u r c es h a 血1 9 ，a n d f l e x i b l er o u t e s s t a n i l l g 、) r i t l ln l e m o d e l i l l gm e t l l o d s 锄ds c h e d u l i n g2 l 1 9 0 r i t l l i n so fp “n e ts y s t e m s ，也er e s e a r c hm a k e s 觚i n t e n s i v es t u d yo ns e v e r a jp r o b l e m si i lt 1 1 es c h e d u l m gp r o c e s so ff m sa i l dp r o p o s e s s o m em o d e l s 锄da l g o r i n u n s t h em 萄o rr e s u l t sa r es u m m a r i z e da sf o l l o w s ： 1 b yt h er e a c h a b i l 时铲印ho f t h ep e t r in e tt h a tm o d e l sa l lf m s ，ah y b r i dh e 埘s t i c s e a r c hs c h e d u l i n ga j g o r i n l i ni sp r o p o s e db a s e do n 廿l eb f b ts e a r c ha l g o r i t h ma n d d ) ，i l a 而cs e a r c h 谢n d o wt e c h n o l o 夥n l eb fa l g o r i t h mc a i le n s u r et 1 1 em o d e l i n gq 叫i 妙 n eb t a l g o r i t l l l l lc a l lr e a l i z eq u i c kf e e d b a c k n l ed y n 锄i cs e a r c h 晰n d o wc 锄c o n 仃0 l t h es y s t e ms c a l e 锄di n l p r o v eo p e r a t i o ns p e e d t 1 1 i sa l g o r i t l l i nc a i la c l l i e v eb e t t e r m o d e l i n ge 疏c t sq u i c l d ya s s h o w ni i l 趾e x a l t l p l ea i l dc a i lb eu s e dt 0d e a l 诵t h l a r g e s c a l e df m s ss c h e d u l h l gp r o b l e m s 2 t h es c h e d u l i n gp r o b l e mo ff m s 晰t 1 1d u e d a t ei ss t u d i e d 1 1 1 i sr e s e a r c h e s t a b l i s h e sas c h e d u l i n gm o d e lb a s e do np e t r i n c t s 、) ，i lt l l eg o a lo fm i i l i m i z i n gt 0 词 t a r d i n e s s b a s e do nd y n 锄i cd e c o m p o s e dm l e - d a t e 也e o r y ，ah e u r i s t i c 如【n c t i o ni s p r o p o s e d 诹m 也et o t a lt 莉i n e s so fe a c hj o b 嬲t l l ei n d i c a t o rs o 嬲t 0r e n d e rb f a l g o r i t mt oc o m p l e t es c h e d u l i n gp r o c e s s 3 u n d i r e c t e dp e t r in e t sa r ea d o p t e dt 0m o d e lt 1 1 er o u t el a y o u to fa na g vs y s t e m a t i m e - b a s e dr e a c ha _ b l es t a t e 舯p hi sc o n 鲫m c t e dw i t ht l l ec o m b i i l a t i o no ft i m e w i n d o w t h es c h e d u l i n gm e t h o di su s e dt 0o p t i i l l i z em er o u t eo fb i d i r e c t i o n a lm u l t i p l ea g v s y s t e m s as h o n e s t - t i m er o u t i n ga l g o r i t l l m i sp r o p o s e db a s e do nb fs e a r c kw 1 1 i c h d 酏册i n e st h ep r e s e n t 曲蕾t ed e p e n d i n go n 廿1 ei o m l a 矗o no fi t sn e ) ( ts t c pp a m t h e s t u d ya l s os t u d i e sr o u t i n ga l g o r i t l l m so fn l es y s t e m 、) i ，i n lm u l t i p l ea g v s i i lt v 旧d w e l l m o d e s ：w o r ks t a t i o np a r l ( i n ga n de q u i p m e n tp a r k i n gm o d e s ad u e - d a t ea g vs e l e c t i o n m e t l l o da n dr o 矾n g 柏g o r i t h l i la 1 ed i s c u s s e d 4 f o ra c c o m p a l l i e d ，d e c e n t r a l i z e d ，a i l dd i s t r i b u t i n ga 1 1 ds h 撕n gd i s p a t c h e da g v s ， m ep “n e tm o d e l sf o rf m sw h o s e j o b sa r en e 鲫e d 谢ma g v s 撇b u i l t a p e t r in e t m o d e lf o rs e l e c t i n ga g v s 、) l ，i t l l i nd i s t r i b u t i n ga n ds h a r i n gd i s p a t c l n e n t 鲫r a t e g yi s e s t a b l i s h e dt 0o p t i m i z et l l ec o n 仃o lo v e ra g vd i s t p a t c b j n g 砌dr o u t i n g w i 也也eh y m d 基于p e t r i 网的f m s 调度问题研究 h e 嘶s t i cs e a r c ha l g o r i m m ，e xa i ：n p l e sa r eu s e dt od e m o n s t r a t eo fm lt 1 1 es t r a t e g i e s t h e s c h e d u l i i l ge a e c t so fa l ls 仃a t e g i e sa r e 锄a l y z e da n dc o m p a r e d 5 b a s e do nt l l ef m s 、) l ，i mi n t e 黟a t e da g v s ，n l es c h e d u l i n gp r o b l e mc o n s i d e r i n g t 1 1 e p a t l lt r a 硒ci n 锄a g vs y s t e mi s f 盯c 1 1 e rd i s c u s s e d f o rd i f r e r e n td i s t r i b u t i o n s 啾e g i e s ，m ec o r r e s p o n d i n gi n t e g r a t e df m sp 鲥n e tm o d e l sc 0 n s i d e r i n gr o u t es y s t e m s a r ee s t a b l i s h e d w ef o c u so nf m ss c h e d u l i i l gp r o b l e m sb yc o n s i d e 血gr o u t es y s t e m w h e na g v sa d o p tt 1 1 ed i s t r i b u t i l l ga n ds h 撕n gd i s t r i b u t i o ns n a t e g y b y 锄o p t i m a 】r o u t e a l g o r i t h i 玛d u e - d a t cb a s e da g vs e l e c t i o i l ，a 1 1 dr o u t i i l ga l g o 枷1 r i l ，铆od i 恐r e m s c h e d u l i l l gm 甜l o d sa r ep r o p o s e d t h es c h e d u l i i l ge 能c t so ft l l et w om e 廿l o d su 芏l d e r d i f 王i e r e n tc i r c u m s t 锄c e sa 1 ea n 出y z e da n d c o m p a r e d k e yw o r d s ： f l e ) 【i b l em 锄u 觚i i r i n gs y s t e m s ( f m s ) ，s c h e d u l i n 岛h e 嘶s t i cs e a r c h ，m o d e l ， p e t r in e t s ，a u t o m a ：c e dg u i d e dv 曲i c l e ( a g v ) ，d u e - d a t e 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包 含其他人已经发表或撰写过的研究成果? 也不包含为获得西安电子科技大学或其 它教育机构的学位或证书而使用过的材料与我一同工作的同志对本研究所做的 任何贡献均已在论文中做了明确的说明并表示了谢意 本人签名：日期：卯f ，f 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：学校有 权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部 分内容，可以允许采用影印、缩印或其他复制手段保存论文( 保密的论文在解密 后遵守此规定) 本人签名： 导师签名： 日期：加f 口! ! 日期：纱f _二 第一章绪论 第一章绪论 1 1 研究背景及意义 随着市场竞争加剧，企业对生产能力最大化、在制品和库存最小化以及尽可 能满足交货期等的要求越来越强烈，因而计划与调度在现代制造系统中扮演着越 来越重要的作用1 。生产调度主要考虑的是资源对于时间的有效分配。调度的目的 就是在满足生产约束的情况下，确定何时使用何种资源加工何种工件，以实现生 产目标，降低生产成本，提高生产效率，满足客户需求。 近年来，柔性制造系统( f l e x i b l em a n u f a 曲l r i n gs y s t e m s ，简称f m s ) 的生产 调度问题持续地吸引着人们的兴趣，无数的工业和研究团体一直致力于开发各种 方法能快速地解决现实的调度问剧厶川。但由于f m s 调度问题的复杂性，至今还未 找到一个能解决所有问题的完美方法。f m s 的调度问题属于一类n p 困难组合问 题h 。7 ，一般情况下用多项式算法不可能求得最优解p 1 。人们在研究制造系统的调度 问题时采用了多种方法，如数学规划、邻域搜索、启发式派遣规则法以及人工智 能掣圳。但是当问题的规模变大时，计算时间将呈指数上升，因此很难用这些方法 获得结果。同时由于f m s 中存在制造路径的柔性，使用传统的方法来求解调度问 题将变得非常复杂。p e t r i 网( p e t r in e t ，简称p n ) 作为一种强大的图形化的建模 工具，能对f m s 的约束和特征进行系统地建模，还能通过数学分析的方法提供f m s 的信息，并能引导调度过程，是一个理想的f m s 调度建模工具。因此利用p n 建立f m s 调度模型，再利用优化算法根据模型信息搜索最优解，是近年来解决f m s 调度问题极具前途的方法。通常情况下将p n 与启发式调度规则、搜索算法、遗 传算法等结合用于f m s 调度问题，力求在适当的计算时间内，获得优化的调度结 果。以此为基础，可以将调度问题扩充为包括安装时间、批量、交货期等多种因 素的调度问题，以满足生产系统的需求。 对于实际f m s 而言，其模型规模较大，系统更为复杂，可达图的规模急剧增 大。要在图中枚举所有的发射序列，确定最优序列，需要花费非常多的时间，甚 至是无法实现的。因此科学地建立准确表述生产系统的p n 模型，合理应用搜索算 法，产生必要的部分可达图，从而确定最优或者次优的方案，对于快速安排组织 生产、降低生产成本、满足客户需求等具有十分重要的作用。同时，研究以自动 导引车( a u t o m a t e dg u i d e dv e l l i c l e ，a g v ) 为代表的物料传输系统的调度与管理， 建立物料传输系统与物料加工处理系统的集成模型与调度算法，实现f m s 的综合 调度，对于探索建立真正实际f m s 的计划、调度与控制方法具有重要的理论意义 和工程应用价值。 2 基于p e 倒网的f m s 调度问题研究 1 2 基于p e t r i 网的f m s 调度问题的研究进展 柔性制造系统是将尖端制造设备与先进计算与信息技术结合，提供制造操作 的柔性，以满足客户需求不断变化的制造模式，是一个可较方便地重构以生产多 品种小批量产品的生产系统u 到。f m s 通常由各种类型的c n c 设备、计算机、机器 人以及a g v 组成，并按需要设计生产不同种类的产品。由于f m s 本质上是异步 并发系统引，致使对系统的计划、设计、调度与控制等是十分复杂的问题。 在解决调度问题时，人们引入了许多方法，如数学规划、邻域搜索、启发式 派遣规则以及人工智能等纠。然而由于制造系统中的一些实际的约束，如材料处理 系统、资源共享、路径柔性等很难用数学方法描述，数学规划方法在应用于复杂 调度问题中会受到许多限制，数学模型经常会严重依赖于假设和简化。另外，通 过数学方法建立的方案在遇到系统环境发生变化时将会失效，对于实际的生产问 题，往往不能得到可行的方案1 1 引。启发式派遣规则经常用有限的系统信息，在复 杂系统调度中还是不够的。基于人工智能技术能产生可行的方案，但是很难告诉 我们什么方案更接近于优化方案。 近年来，人们将p n 用于f m s 的建模与分析，并与相关方法结合求解调度问 题，取得了良好效果。主要是通过将优化问题转化为可达图中寻找最优路径问题， 通过部分枚举可达图，确定一个从初始标识到可达的目标标识的合理触发序列。 目前关于f m s 调度问题的研究有许多方面，但本文主要围绕基于p n 的调度 问题的搜索方法、不同的调度评价标准、以及与f m s 密切相关的a g v 系统的建 模与调度等主线来展开。 1 f m s 调度问题的搜索算法 ( 1 ) 将p n 与图形搜索法结合 从p n 的角度来看，不同的调度优化问题可以表示为求解p n 的优化触发序列 问题引。目前大多数的研究是将优化问题转化为从可达图中寻找最优路径问题。 但是当对实际的f m s 进行建模时，产生的可达图将是十分巨大的。在一些情况下 适当降低优化的标准，将会使搜索的工作量大大减少。因此，在适当的计算量下， 找到一个可行方案、次优方案，在计算工作量与优化目标之间取得一个平衡将是 研究的一个方向i 川。 l e e 与d i c e s a r e 的研究首次将p n 与全局搜索结合，并以a 方法为基础建 立了一个启发式搜索算法l 1 。l l 算法遍历部分可达图一直到最终标识。一旦抵达 了最终标识，通过追踪指向父节点的指针就可以建立优化的路径。变迁的触发序 第一章绪论 3 列就提供了行动的次序。l l 算法就是在启发信息的帮助下，搜索可达树中那些最 有希望的节点来尽快获得一个优化的结果。为了减少搜索可达图的工作量，许多 研究人员以l 1 算法为基础又提出了许多的改进方法。s u i l 等人卅通过选择性删除 一些没有希望的分枝来限制可达图的扩展；x i o n g 和z h o u 叫将l l 法与可控的回溯 法相结合，分别研究了l 1 处于前端回溯法处于后端和回溯法处于前端l 1 法处于 后端等两种混合启发搜索算法，并将它们用于多品种、大批量的半导体制造系统 调度中，大大降低了计算量，取得较好的调度效果。该混合方法也可根据计算量 的要求方便地转变为l 1 算法。以上这些方法将深度优先搜索与分枝定界技术结合 以减少计算工作量并获得次优的调度方案。m o r 0 等人叫提出了一个基于p n 的混 合调度算法，称为动态有限选择有限后向追踪算法( d l s s ) ，并使用了后代产生 器，控制子节点的产生。目的是减小搜索的工作量而最大化可接受程度。m e j i a 与 o d r e y 在2 0 0 3 年工作u 的基础上进一步扩展形成了带束a 木搜索算法( b a s ) ，该 方法具有可选择性的分枝过滤器、优先扩充、新的评价函数以及可控的搜索深度 等优点“川。j e n g 等瞄州提出了一种改进的l 1 算法，并将该算法用于由普通的同步网 与异步网建模的f m s 中。一个异步网被定义为由一些具有替代工序的工件构成的 网，而同步网的加工步骤中没有替代工序。该算法用了一层回溯法以避免死锁。 古天龙等钏讨论了基于有序二叉决策图的有界p n 符号分析，建立了f m s 调度问 题的符号有序二叉决策图求解算法。该算法在求解过程中通过对状态空间及其搜 索过程中相关数据的有序二叉决策图表示，避免了状态和搜索的全部枚举，改善 了算法的计算性能。 以上工作主要是通过搜索方法的变化来改进调度效果，但同时启发函数对于 调度运算的速度与调度质量具有重要作用。一些研究在这方面进行了探索。l e e 与 d i c e s a r e 分别以初始标识到当前标识的最低成本、当前标识的深度、最小剩余时 间以及它们的结合为基础引入了四个启发函数来引导搜索1 1 。e l i i l e 娜与 e l m a r a 曲y p l 分别以平均操作等待时间和调度规则函数为启发函数，计算了以平均 流时间最小为目标的调度问题。调度规则函数就是在使用某种调度规则产生工件 的排序后总的流时间为下界，乘以补偿系数作为启发函数。这两种方法经过简单 修改就可以用作以其它标准作为目标的调度问题。y u 等人p 1 从专门的p n 模型的特 性出发建立了资源成本可达矩阵，推导产生了表示机器利用率最小和并发任务最 大的启发函数，引导工件沿着堵塞最小的路径进行加工。该启发函数对于避免机 器长时间处于空闲状态具有明显效果。j e n g 与c h e n u 叫使用p n 的状态方程将整数 规划问题转为矩阵计算，并用触发向量的总成本作为启发函数来搜索。在此基础 上进一步扩展，基于状态方程建立启发函数引导搜索过程。由于该启发函数包含 了足够的全局信息，可以有效地产生最优或者次优的方案“。 ( 2 ) 将p n 与启发式派遣规则结合 4 基于p e t r i 网的f m s 调度问题研究 启发式算法就是寻求一种能产生可行解的启发式规则，以找到一个次优解。 对生产任务进行调度最传统的方法是使用调度规则，已经有许多调度规则被应用， 因其简单、易于实现、计算复杂度低等原因，能够用于动态实时调度系统【1 1 】。将 不同的调度规则用于基于p n 的模型中，主要是解决调度过程中资源分配和零件排 序出现的冲突。h 巩m o 掣邛1 使用了随机p n 描述f m s 中的不确定事件，如机器工 具的故障、修理时间、加工时间等。他们开发了一个基于规则的在线调度系统， 产生适当的优先规则以从冲突的变迁中选择一个触发。c 1 1 i n c h o l k a r 与c h e t t y m 叫提 出了一个启发规则用于固定路径和柔性路径的两种情况下f m s 动态调度中，并比 较了几种不同的优先规则的运行效果。l i l l 与l e e p 叫提出了一种分层的控制与调度 机制。上层是调度层而下层是控制层，使用着色时间p n 来指示单元中的托盘流， 将分派规则与p n 结合进行车间层面的调度。 在一个变化的车间配置和操作条件下，没有哪一个分派规则可以完全一致地 比其它所有规则最优p 。因此将调度规则按照某种方式组合建立知识库，可用于 多目标调度问题。m a r 血e z p 叫将知识库调度系统融入f m s 的设计中建立了p n 模型。 n a k 锄嗽p 刘提出了一个基于p n 的模拟方法，当变迁出现冲突时，可由知识库产生 的优先规则解决。g r a b o t 等人p 钏基于模糊逻辑提出了方法将这些分派规则结合起 来，模糊的规则可在满足几个不同评价标准上达成妥协。x i o n g 等p 纠基于模糊逻辑 引入了一个模糊分派规则，该规则可以描述多变量和f m s 调度目标特征的语义形 式，并通过解释算法将这些规则用于调度中。w 抽g p 刨提出了一种在逻辑控制中合 成了调度分配知识的面向对象p n 模板。 ( 3 ) 利用p n 结构的特点 一些研究在调度过程中充分利用p n 结构自身的特点，降低模型规模或者产生 无死锁的调度。对死锁现象的控制保证调度有效性的基础。对于死锁的控制主要 集中在三个方面p ：第一是将活性p n 合成到制造系统中以产生一个无死锁的p n 控制器；第二是运行过程中死锁发生，然后检测并消除：第三是在系统中动态分 派资源以预防死锁现象发生，实现无死锁。事实证明预防死锁技术在提高系统生 产率上是优于其它技术的。 e z p e l e d 邛1 等首次将p n 信标的特性用于具有资源的简单顺序加工的f m s 中， 作为避免死锁的策略。用清空的信标来描述死锁的状态，而通过在p n 中加入控制 库所来建立活性的充分必要条件，以避免信标被清空。a b 蹴l a l l 掣怕1 使用时间p n ， 针对一类具有共享资源的顺序系统( s 4 r ) 提出了有效的无死锁调度算法，根据p n 信标的结构特点提出了一种修剪技术，以产生最小的部分可达图。c h u 与x i e p 刈 基于线性规划提出了一种判定信标及系统死锁的充分条件，并通过混合整数规划 法检查p n 有无产生空信标。a b d a l l “删等人提出了一种发现最小不可控信标的有 效方法。为了控制死锁，许多方法需要添加过多控制库所和连接弧，使得p n 控制 第一章绪论 5 器比原先建立的网模型复杂得多。李志武与周孟初p u 提出了基本信标的概念，不 仅能极大地减少附加控制库所和连接弧的数目，而且能达到同样或更好的控制效 果。胡核算等心1 基于基本信标和混合整数规划法提出了f m s 的死锁预防策略，应 用该算法可在多项式时间内计算出控制库所需要的初始t 0 k e n 数。李志武掣 1 提 出了利用p n 对设备发生故障的f m s 建模和死锁控制的一种方法，用故障库所、 故障变迁和恢复变迁描述设备故障、修复以及重新投入工作的整个过程，并研究 了一种死锁控制策略：通过对每个基本信标添加控制库所，保证其不产生新的可 被清空的信标，通过调整基本信标的控制深度变量来实现对从属信标的控制。在 此基础上，通过对添加的控制库所冗余性的分析，去除了冗余的控制库所，得到 了许可状态更多、结构更为简单的p n 控制器一1 。 为了减小调度问题的复杂性，研究人员将分解方法引入到了p n 中。一个p n 被分解为几个子网，分别重复求解每个子网的最优变迁触发序列以获得可行的方 案。然而分解产生的子网并不是唯一的，y o s m e 等一叫提出了一种有效的过程可将 p n 分解为多个适当结构的子网，以获得最优的变迁触发顺序。每个子网的状态数 量被限制在多项式数量级。l e e 一叫使用的p n 中控制流是基于t 0 k e n 流的原理，通 过基本并发单元的概念将系统网分解为机器操作的子网，并分析了每一个调度的 可行时间。在此基础上，文献 4 7 】根据机器的操作将f m s 划分为一些子系统，将 p n 模型展开成一些子模型。h e 等1 开发了一种方法可以自动将制造系统的i d e f 3 模型转变为p n 模型，并根据资源的类似性将模型分解成多个子模型，通过将各子 模型的调度汇总形成总的调度结果。f r e y 一川则用t 一不变式的特性来缩减模型规 模，并建立代数方程来获得调度结果。由于系统规模变小，避免了状态空间爆炸， 降低了系统复杂度。 ( 4 ) 将p n 与遗传算法等结合 n p 难题的本质已经使解决方法从系统、确定性方法到局部、随机、优化的方 法如遗传算法( g e n e t i ca l g o r i t h m ，简称g a ) 、模拟退火算法等p 1 。人们也将p n 与这些方法相结合用在了f m s 调度中。h 啪g 等p w 将队列着色p n 模型与g a 结 合寻找不同启发策略的优化组合。郝东、蒋昌俊等p u 用p n 模型的激发序列作为染 色体，而交叉和变异都是对p n 模型中的元素进行操作，与问题空间中的元素无关， 因此，具有较高的通用性。刘维来等p 司将g a 与p n 结合用于解决柔性装配系统的 设备调度问题。算法使用的染色体是由p n 型中的部分选择库所名称排列而成，每 个染色体都代表一种设备调度方案。c h e n 掣 1 用c t p n 对一个半导体装配线建模， 提出了一个g a 调度器，可以为每一个工作站动态搜索合适的调度策略。其中染 色体记录着装配线上每个工作站采取的调度策略信息。吕文彦与党延忠p 4 将g a 与 p n 结合用于解决可重入生产系统的调度问题。王笑蓉与吴铁军p 刈在p n 仿真运行 获得调度性能评价的基础上，提出了加工路径蚁群优化和作业排序遗传算法优化 6 基于p e t r i 网的f m s 调度问题研究 的两级递阶结构。将一种基于蚁群种子集的蚁群优化算法用于解决加工路径选择 问题。在加工路径确定后，采用g a 对分配在同一机器上加工的作业排序进行优 化。潘全科等p 叫针对绿色制造模式中的车间调度问题，建立了反映加工时间、生 产成本、资源消耗和环境影响等信息的p n 模型，采用g a 与模拟退火算法相结合 求解优化调度结果。马敏等p 将p n 与模拟退火遗传算法相结合用于并行测试系统 的任务优化调度问题中。在搜索过程中，将能激发的变迁序列作为染色体进行处 理。为了防止算法过早收敛，陷入局部最优解的现象，还要对个体进行模拟退火 操作，最后得到测试完成时间最短的任务调度序列。 2 特殊情况下的f m s 调度问题 ( 1 ) 拆卸系统的调度问题 绿色制造是一个综合考虑环境影响和资源消耗的现代制造模式，其目标是使 产品从设计、制造、包装、运输使用到报废处理的整个生命周期中，对环境的影 响极小，资源利用率极高p 引。拆卸是绿色制造中最为重要的环节，是确保单个部 件、配件或者材料可重用的必要过程。由于系统结构与部件情况的不确定性，因 此对拆卸过程的建模与计划比装配过程更具挑战p w 。人们先后使用了部件一构件 图、有向图、与或图等作为描述拆卸过程的工具。这些方法具有各自的优点，但 也存在一些问题p 9 】1 6 0 】【6 1 1 ：部件一构件图可以直接从c a d 图获得，使用图搜索算法 可以得到优化的拆卸顺序，但是该方法不能对拆卸的任务进行建模；有向图可以 表述所有的拆卸顺序的几何，但需要较大的搜索空间；与或图可以与启发算法结 合，但在构建图的过程中需要部件与构件的信息，且很难与资源模型结合。通常 情况下，使用p n 可以很容易地表述拆卸与装配操作。l 锄b e r t 等巾纠提出了拆卸图 的概念，用于确定产品的优化拆卸顺序，又以线性规划为基础提出了产生优化拆 卸顺序的方法p 引。z u s s m a i l 与z h o u 畔1 将装配p n 扩展为拆卸p n ，提出了基于p n 的拆卸模型。m o o r e 等坤纠从产品的c a d 模型中产生基于几何图形的拆卸优先关系 矩阵，随后又产生了拆卸p n ，使用可达树和启发式方法可产生一个次优的拆卸业 务计划。j o h n s 0 n 和w 抽g m l 将经济因素结合到了拆卸操作的调度之中，提出了一 种以最大化材料重用利润为目标产生的优化拆卸顺序的系统化过程。文献 6 7 】以该 方法为基础，通过p n 建立了拆卸业务的优先关系，以成本最低、浪费最少为目标， 与启发式方法结合，提供了搜索部分可达图产生优化或者次优拆卸顺序的有效方 法，并通过删除拆卸树和对可达图进行有选择追踪两个方面来缩减搜索空间。 n e u e n d o r f 等p 驯将具有时间图章的p n 应用到了每个普通零件有多个可选货源的情 况的产品的拆卸调度问题中，取得了较好效果。目前的大多数研究是基于装配信 息进行的，事实上一些产品的特征并不知道，使得这些预先确定的计划也是不现 实的。未来的研究应该考虑如何在不确定和意外情况下的动态拆卸系统的问题。 第一章绪论 7 文献【6 9 】在这方面进行了尝试，虽然使用拆卸p n 与b a y s i a n 网结合提出了一些很 好的想法，但是对实际拆卸系统而言依然缺乏有效的算法。 ( 2 ) 带有安装时间与批量的f m s 的调度问题 在实际的j o b s h o p 调度中，批量和安装时间是两个重要的因素。但以前的 研究并没有考虑安装时间或者只把它看作加工时间的一部分，近来有许多研究工 作将注意力集中在了安装时间上。z h a i l g 与g u l 1 使用时间p n ，对包括了批量和预 定的由顺序决定的安装时间的调度问题建立了模型。觚i g u e s 与r o u b e l l “儿1 建立了 具有多资源需求和安装时间的j o b s h o p 在线调度的p n 模型，该模型标记了在线与 离线调度的状态、决策和事件的准确特征。通过计算发生图为实时的调度决策提 供建议。y i m 与l e e 副研究了考虑设备安装时间的f m s 的调度问题，这里的设备 安装时间是指由于更换工具而花费的时间。 在批量系统制造过程中为了最大程度地共享资源，经常会发生多个加工过程 竞争相同资源的现象。如果不对系统进行很好的分析和控制，很容易导致死锁现 象的发生川。g u 与b 砌v 训开发了一个基于时间p n 的建模方法用于多产品的批量 生产调度中。a z z o p 砌与l l o y d p 纠对多产品的批量加工系统建立了p n 模型，基于 回溯机制和分枝定界算法获得了优化的m a l ( e s p 孤。近来人们又将u m l 与p n 结合 来对批量系统进行建模和分析。文献【7 6 】使用元建模方法将顺序图转变为p n 。文 献【7 7 】将用顺序图表示的系统初始需求转变为一个表示系统全局行为的p n 模型。 对于包含冲突的p n 片段，可通过线性逻辑连续计算来获得生产和消费的时间，并 通过算法来避免冲突。y u 和l l o y d i 缁1 研究了批量生产系统中加工时间间隔的扰动 对批量m a l ( e s p a i l 的影响，并使用关键路径分析法启动了批量事件顺序的调度，以 校正波动。 许多研究人员认为混合批量连续系统的调度是一个十分重要的问题p 咒甜1 。但 批量系统的生产调度目标与连续系统略有不同。在连续生产系统中，问题简化为 选择生产率，而在批量系统中，调度的目标简化为在什么时间选择加工哪个批次 的产品。g h a e l i 等p u 提出了一种时间混合p n 作为一个混合批量连续系统的建模 与调度工具，与传统方法相比，该工具可以明显降低系统复杂度，取得较好的调 度效果。吴亚丽等垆卅针对批处理过程动态调度问题的特点，以着色时间h p n 为工 具，建立了批过程动态调度的模型。根据动态规划原理，以最短生产周期为调度 目标，提出了一种求解变迁的最优激发序列的方法。李慧芳与李人厚p 州以设备为 核心将整个过程操作划分为若干个子进程。用时间p n 建立以子进程表示的批处理 过程，并用启发式动态优化算法对过程进行控制。 ( 3 ) 循环生产系统与非循环生产系统的调度问题 通常情况下将制造系统分为两种类型，即生产率固定不变的循环制造系统和 根据顾客需求进行优化决策的非循环制造系统。p r o t h 与s a u e r 畔1 提出了一种叫做可 8 基于p e t r i 网的f m s 调度问题研究 控输出网的特殊p n 用于非循环制造系统建模，并将调度算法分为两个阶段：第一 个阶段主要是在设备资源间进行负载的配置，第二个阶段是从资源负载中产生调 度结果。k o r b 矩等峭别分别针对非循环调度和循环调度提出了基于p n 的两种方法， 指出当产品需求量小时采用循环方法，而当需求量较大时采用非循环办法更为有 效。h s u 等p 1 研究了以在制品最少的同时生产周期最短为目标的循环生产调度问题， 采用了两步方案：第一步建立了生产过程的p n ，并通过分析解决了由于系统柔性 而带来的一些不可预计的事件，并使在制品处在一个较低的范围内；第二步以调 度问题的正式模型为基础，通过遗传算法而获得了一个满足目标的优化方案。 g a v o 珂等人p 叫研究了具有线性约束关系的循环调度问题。用p n 建立循环任务之 间的线性约束关系，使用遗传算法建立机器上工件的优先顺序以便在调度过程中 解决资源的冲突。s o n g 与l e e p 川研究了设备缓冲区容量有限，易造成拥塞情况下 的循环调度。提出了一个顺序缓冲区控制策略指引工件按照专门的顺序进入下一 个缓冲区，在该策略下将模型转化为无缓冲区且可变为时间标识图的模型。 3 扩展p n 及其在f m s 调度中的应用 为了更好地对f m s 进行建模，人们对p n 进行了不同的扩展，这极大地增强 了它们的建模能力。有一些研究在求解调度问题时采用了各种扩展p n 。文献 8 8 】 提出了模块p n 可对单元中的不同资源进行建模。当用于实时调度时，可以解决资 源间的冲突。h u a i l g 等p 叫在着色时间p n 的基础上，与排队系统结合形成了队列着 色p n ，使用该模型可以较为有效而准确地预测在不同调度策略下产品的交付时间。 r e y e s 与y u l8 1 0 8 9 1 等人建立了p n 的一种子类b u 毹r 网来描述f m s ，对于较难建模 的系统来说，增强了建模的能力。y u 掣1 开发了一种工具可以将这些b u 疏r 网进 行合成，并将p n 模型与基本人工智能( a n i f a i c a li n t e l l g e n t ，舢) 技术结合建立了 启发式调度算法。薛雷和郝跃p 叫在普通p n 模型中加入了测试弧，可对设备维护以 及设备与操作的优先级进行建模，并利用新模型的特性结合广度优先法结合形成 了搜索算法。 d a v i d 与舢l a p u 提出了由连续部分与离散部分共同组成的混合p n ( h y b r i dp 嘶 n e t ，简称m ) n ) 的概念。硒m 等邮1 针对大规模的生产系统，建立了一种包含连续 p n 和时间p n 的分层混合模型，连续p n 处于上层描述每个子系统的生产速度和 生产线传输速度，时间p n 处于下层描述离散状态下的制造环境。s 枷e h 等p 川将 时间与弧关联提出了时间弧h p n 。针对每个连续的操作，该p n 模块都能发现优 化的批量调度。b a l d u z 五等人l 驯使用了一阶混合p n ，建立了线性代数方程的框架 来研究模型的连续行为，并表明对行为的控制可看作是优化特定的对象函数。文 献 9 5 】提出了一种层次扩展h p n ，用于生产过程的调度与监控。韩赞东与熊道权m 针对大批量制造系统，使用h p n 来建模，其中连续节点被用来表示大容量库所和 第一章绪论 9 短时变迁，解决了传统的p n 在仿真过程中存在的可达状态爆炸和仿真时间过长的 问题。 近年来，越来越多的人将p n 与面向对象方法相结合，以吸纳面向对象的抽象、 封装、继承等特性，目的就是处理p n 的状态爆炸问题。文献【9 7 】利用面向对象方 法对f m s 和有色时间p n 进行了描述，并根据最小下次事件时间推进原理建立了 f m s 动态调度仿真系统。郭晓泉与徐心和p 驯采用多环面向对象p n 结合启发式算 法，研究了装配系统的调度问题。w 撕g 与w u 一1 通过加入着色t o k e n ( 托肯) 扩充了 o o p n ，用于自动制造系统的建模与分析，并使用修改的l l 搜索算法产生一个次 优的调度。j i a l l g 等叫在面向对象p n 的基础上提出了可变结构面向对象p n 用于 生产系统建模。f u n g 等1 将o p n c s