（计算机应用技术专业论文）基于petri网的job_shop动态调度问题的模型和仿真.pdf

1，；il，：， 舢删舢 6 4 近年来随着市场竞争的加剧和客户需求的个性化，现代企业生产模式正在朝着“品 种多样、批量变小、注重交期、减少库存”的方向发展。车间作业调度是解决现代企业 生产过程中工件在机器上的调度和资源分配问题极其重要的一环，成为企业效益增长的 瓶颈，是目前亟待解决的问题之一。 在对j o b动态调度问题分析的基础上，本文采用带有抑制弧的着色网对其shop p e a l 进行分析和建模，并用c p nt o o l s 对模型进行了仿真和验证。本文主要完成的内容如下： ( 1 ) 对j o bs h o p 调度问题的特点和分类等进行了描述，并分析了其存在的问题；( 2 ) 详细阐述了p e a l 网的基本理论，介绍了基于c p n 的建模和仿真分析工具c p nt o o l s ，以及 在该工具下如何来对系统进行建模和分析；( 3 ) 通过将着色p e a l ( c p n ) 与带抑制弧的 p e t r i 网相结合，提出了带抑制弧的着色p e t r i 网c p n i a ( c o l o r e dp e a ln e tw i t hi n h i b i t o r a r c s ) ，并建立了基于c p n i a 的j o bs h o p 动态调度模型，该模型充分考虑了机器故障、 设备维护、优先级变化等动态扰动因素，并从不带时间的角度，用c p nt o o l s 对一个具 体实例进行建模和仿真；( 4 ) 从带时间的角度，用c p nt o o l s 对实例再次进行建模和仿 真。 仿真结果表明该模型对于机器故障、设备维护、优先级变化等动态扰动因素，可迅 速的做出反应，及时对生产计划做出调整，同时也证明了该模型的有效性和正确性。 关键字：p e t r i 网；j o b _ s h o p 动态调度；抑制弧；c p nt o o l s lir i i a b s t r a c t i nr e c e n t y e a r s ，w i t h t h em a r k e t c o m p e t i t i o na g g r a v a t i n g a n dt h e c u s t o m e r sv a r i o u sn e e d si n c r e a s i n g ，t h em a n u f a c t u r i n gm o d eo ft h em o d e m e n t e r p r i s e i sd e v e l o p i n gt o w a r d st h ed i r e c t i o nt h a ti s b r e e dd i v e r s i t y , s m a l l b a t c h e s ，s h o r td e l i v e r yd a t ea n dl o wi n v e n t o r y j o bs h o ps c h e d u l i n gw h i c h s o l v e st h e p r o b l e m so fs c h e d u l i n g a n dr e s o u r c e sd i s t r i b u t i o nb e c o m e sa n i m p o r t a n tp a r t o ff a c t o r ym a n a g e m e n ta n dp r o d u c tm a n u f a c t u r i n g ，a n dt h e b o t t l e n e c kw h i c hi st h er e s i s t a n c eo fe n t e r p r i s e sg r o w s n o w a d a y s ，i ti so n eo f t h e s ep r o b l e m sn e e d e dt ob es e t t l e dp r o m p t l y i nt h i sp a p e r , b a s e do nt h ea n a l y s i so ft h ejo bs h o pd y n a m i cs c h e d u l i n g p r o b l e m ，t h r o u g hu s i n gt h ec o l o r e dp e t r in e tw i t hi n h i b i t o ra r c s ( c p n i a ) ，t h e m o d e lo ft h ejo bs h o pd y n a m i cs c h e d u l i n gi sp r e s e n t e d ，a n di ss i m u l a t e da n d a n a l y z e du s i n gc p n t o o l s t h i sp a p e rm a i n l yf o c u s e so nt h ef o l l o w i n ga r e a s ：( 1 ) d e s c r i e st h ec h a r a c t e r i s t i c sa n dt h ec l a s s i f i c a t i o no ft h ejo bs h o pd y n a m i c s c h e d u l i n g ，p o i n t so u tt h ee x i s t e n c eq u e s t i o n s ；( 2 ) i n t r o d u c e st h eb a s i ct h e o r yo n p e t r in e ta n das i m u l a t i o nt o o l ，c p nt o o l s ，w h i c hi sb a s e do nc o l o r e dp e t r in e t ( c p n ) i ti si n t r o d u c e dh o w t om o d e la n da n a l y z eu s i n gc p n t o o l s ；( 3 ) t h r o u g h i n t e g r a t i n gc p na n dp e t r in e tw i t hi n h i b i t o ra r c s ，ap e t r in e tn a m e dc p n i a ( c o l o r e dp e t r in e tw i t hi n h i b i t o ra r c s ) i sp r e s e n t e da n du s e dt om o d e lt h ej o b s h o pd y n a m i cs c h e d u l i n g ，i nw h i c ht h r e ec a s e sa r ef u l l yc o n s i d e r e d ，s u c ha s d e v i c em a i n t e n a n c e ，d e v i c eb r e a k d o w na n dw o r k p i e c ep r i o r i t y ；t h em o d e lo fa c o n c r e t ee x a m p l ei ss i m u l a t e da n da n a l y z e db yc p nt o o l sw i t h o u tt i m e ；( 4 ) t h e m o d e lo fac o n c r e t ee x a m p l ei ss i m u l a t e da n da n a l y z e db yc p nt o o l sw i t ht i m e t h es i m u l a t i o nr e s u l ts h o w st h a tt h em o d e lh a ss t r o n gd y n a m i cr e s p o n d i n g c a p a b i l i t yt od e v i c em a i n t e n a n c e ，d e v i c eb r e a k d o w na n dw o r k p i e c ep r i o r i t y a t t h es a m et i m e ，i ts h o w st h a tt h em o d e lh a se f f e c t i v e n e s sa n dc o r r e c t n e s s k e yw o r d s ：p e t r in e t ；j o b _ s h o pd y n a m i cs c h e d u l i n g ；i n h i b i t o ra r c ：c p nt o o l s l ，jjj￥。p， t 目录 第一章绪论l 1 1 研究背景1 1 2 国内外研究现状2 1 3 论文研究的意义3 1 4 研究内容3 1 5 章节安排4 第二章j o bs h o p 调度问题和p e t r i 网理论5 7 2 1j o bs h o p 调度问题5 2 1 1j o bs h o p 调度问题的描述5 2 1 2j o bs h o p 调度问题的特点5 2 1 3j o bs h o p 动态调度问题的分类。6 2 1 4j o bs h o p 调度问题的建模方法描述6 2 1 5j o bs h o p 调度存在的问题与发展趋势8 2 2p e t r i 网理论介绍9 2 2 - 1p e t r i 网简介9 2 2 2 基本p e t r i 网的概念9 2 2 3p e t r i 网变迁的发射规则1 0 2 2 4p e t r i 网的基本性质1 1 2 2 5 缓冲区模型与p e t r i 网的抑制弧1 2 2 2 6 着色p e t r i 网1 3 2 3c p nt o o l s 的简单介绍l4 2 4 本章小结1 5 第三章基于c p n i a 的j o b _ s h o p 调度模型。1 7 3 1 带有抑制弧的着色p e t r i 网1 7 3 2 模型的建立1 8 3 3 模型仿真2 0 3 3 1 实例2 0 3 3 2 仿真结果分析2 4 3 4 本章小结2 8 第四章基于时间约束着色p e t r i 网的动态调度模型3 1 v 4 1 基于时间约束的着色p e t r i 网3 1 4 2 模型的仿真和分析3 1 4 2 1 仿真模型的建立31 4 2 2 仿真结果分析3 4 4 3 本章小结3 5 第五章总结与展望3 7 参考文献3 9 致谢4 3 附录4 5 攻读硕士期间发表的论文5 3 v i 第一章绪论 第一章绪论 1 1 研究背景 近几十年来随着经济和社会的发展，市场环境有了翻天覆地的变化，传统的大批量 生产方式不再适应市场需求。现在用户对产品的质量以及品种的要求越来越高，希望得 到按照自己要求定制的产品，不再满足于从市场购买标准化的产品。这些变化导致产品 生产方式有了新的特征：面向订单、多品种、中小批量、高质量、交货期短以及低成本 等，这种生产方式即所谓的j o bs h o p 型生产方式。这种生产方式要求针对可分解的工作 ( 如产品制造) ，使其在尽可能满足约束条件( 如交货期、工艺路线、资源约束等) 的前 提下，安排其组成部分( 操作) 使用哪些资源、开始加工时间及加工的先后顺序，以获 得产品制造时间或成本等指标的最优化。 j o bs h o p 型生产方式最大的特点就是能够比较灵活地适应市场的多样化需求，但同 时也带来了诸多困难，如产品生产计划和调度控制难度加大，相应的作为调度问题核心 之一的模型的建立也成为研究的热点问题。作为制造系统的建模方法，主要有活动循环 图、关键路径法、组合网络、p e t r i 网、g r a i 网等【l 】，而其中p e t r i 网作为一种图形建模工 具，能形象地表示和分析生产调度中的并发、冲突、优先权和资源共享等特征，以其独 特的优势广泛应用在制造系统的设计、分析与仿真中。 目前，用p e t r i 网对j o bs h o p 调度问题进行的建模和分析，大部分仅限于静态的层次， 且在建模过程中设置过多的约束条件。生产系统固有的复杂性，以及生产过程中各种扰 动的随机发生，对生产系统的正常运行产生了极大的影响，甚至导致生产系统停止运行。 在这种产品更新快、生产系统稳定性差且复杂多变的制造环境下，企业不仅要能快速生 产出市场所需求的产品，还要能够快速、准确地应对生产过程中频繁发生的各种扰动， 这无疑对整个车间的生产过程控制提出了更高的要求。然而，传统的静态调度方法，只 能利用当前所能获得的有限的工况信息对现有工件进行局部调度，而且缺乏对生产系统 在近期变化的预见性，无法胜任动态的生产系统 2 - - 4 。或者当扰动发生时，仅凭借生产 调度人员的经验进行随机调度，这种调度方式导致产品生产周期长，在制品占用量大， 机器利用率低等，从而影响了生产效益，早已无法满足现代制造模式的要求，亟需改善。 针对这一实际现状，本文采用带有抑制弧的着色p e t r i 网( c p n i a ) 对j o bs h o p 动态 调度问题进行建模和分析。在建模过程中充分考虑了生产调度过程中随机出现的不确定 性问题，如机器维护、机器故障、工件优先级变化等，其目的在于为j o bs h o p 车间生产 系统进行科学合理的生产计划制定和控制活动提供充分的科学理论基础，提高生产系统 1 基丁p e t r i 网的j o b _ s h o p 动态调度问题的模础和仿真 在不确定生产环境下的自适应能力和生产调度的敏捷性，降低由于各种不确定性因素给 企业带来的生产上的损失。 1 2 国内外研究现状 j o bs h o p 调度问题的研究涉及到计算机科学知识、优化理论、图论、系统科学、管 理科学、运筹学理论等，由于其存在“组合爆炸”而被公认为n p h a r d 问题。鉴于其在 生产过程中的重要性，国内外学者对其进行了广泛而深入的研究，产生了大量研究成果。 在国际上，自1 9 5 4 年j o h n s o n 发表两台机床的流水车间调度问题以来，已有2 0 0 0 0 多 篇论文被发表，有m u t h 并t l t h o m p s o n 、c o n w a y 、b a k e r 、f r e n c h 、r i n n o o yk a r l 、c o f f m a n 、 b l a z e w i c e 、m o r t o n $ 1 p e n t c o 版的八本专著【5 】os t e p h e n 6 1 等人在总结以往经验的基础上 对调度问题重新进行了考察，对未来的发展趋势做出了大胆的预测，认为今后发展的趋 势必将是理论与实际的结合。这一极富挑战性的课题吸引了诸多领域的学者参与其中， 许多跨学科的方法也被应用到研究中。其中最具代表性的是以c a m e g i e m e l t o n 大学的 m f o x 。7 】为代表的学者们开展的基于约束传播的i s i s ( i n t e g r a t e ds c i e n t i f i ci n f o r m a t i o n s e r v i c e ) 研究，它是人工智能开始真正应用于调度问题的里程碑。w i l l i a mg 8 1 等，提出 了一种人机交互的决策支持系统，它将顾客和任务的属性作为系统的重要参数，使用了 一种集成数学模型、专家系统和数据库的综合性结构，利用知识库为决策者提供多种调 度方案，并由决策者确定最终方案。s a n a yv t 9 】等提出在工序间适当的插入一段时间用 来吸收出现的随机扰动，以降低系统受动态扰动的影响，但是插入的空闲时问会导致后 续工序开始加工的时间延后，从而存在延长整个加工过程的完工时间的可能性。h e n g l i t l o 】等针对j o bs h o p 调度过程中产生的动态扰动提出了一种重调度仿真专家系统，该系 统综合运用了专家知识、分派规则、仿真技术和人工神经网络等技术和方法。虽然基于 知识的重调度方法可以为实时动态调度问题提供一种解决方案，但获取知识和推理速度 较慢。 国内的学者也对车间调度问题进行了大量的研究，在管理科学学报、计算机学报、 小型微型计算机系统、计算机集成制造系统、机械工程学报、中国机械工程、高技术通 讯、自动化学报等知名学术刊物发表了一系列研究成果。弦光男、王凌、唐恒永等出版 了相关著作，1 9 9 0 、1 9 9 3 、1 9 9 6 并1 1 9 9 9 年分别在上海、武汉、郑州和长沙召开了全国排 序学术交流会，清华大学、沈阳师范大学等已开设了相关的研究生课程【1 1 】。陈维民【1 2 】 等提出了一种基于扩展时间p e t r i 网的单亲遗传算法，并利用该算法对j o bs h o p 调度问题 进行了求解，所提出的算法与其他调度算法相比，具有较高的通用性；王笑蓉l l3 l 等利用 受控赋时p e t r i 网对柔性生产线调度总的离散事件建模，并采用两级递阶进化优化方法求 2 第一章绪论 解柔性生产过程的优化调度问题。但以上研究成果只是针对j o bs h o p 调度问题的前期， 即制定工件的计划加工工序，没有考虑生产过程中的扰动问题。雄禾根1 1 4 j 等提出一类考 虑工序相关性的、工件批量到达的动态j o bs h o p 调度问题。在对工序相关性进行了定义 和数学描述的基础上，迸一步建立了动态j o bs h o p 调度问题的优化模型，并设计了一种 组合式的调度规则鼬州( f c f s ，o d d ) ，并提出了基于规则的启发式算法以及该类动态 j o bs h o p 调度问题的算例生成方法。该文对于j o bs h o p 动态性的体现仅限于工件的批量 到达，而没有涉及到一些异常或随机情况的处理。乐晓波【l5 】等以带有约束条件的p e t r i 网为动态车间调度问题建模，同时提出一种针对动态车间调度问题的编码粒子群算法， 对调度序列进行优化，并且考虑了机器故障、紧急加工两种情况。 就目前的情况来看，国内外对静态j o bs h o p 调度理论的研究比较成熟，对于将根据 加工过程中出现的异常情况实时对加工工序做出调整的动态调度研究相对薄弱，有待于 进一步的研究。 1 3 论文研究的意义 车间作业调度是实现生产高效率、高柔性和高可靠性的关键。有关资料表明，机械 制造过程中9 5 的时间消耗在非切削过程中【i 。7 1 ，及时准确的调度可以提高资源的利用 率，均衡生产，减少在制品的资金占用。 我国制造业与工业发达国家的差距主要表现在制造装备落后和生产组织管理技术 落后，尤其在生产组织管理技术方面。国内企业的生产组织管理技术落后主要体现在生 产管理和调度以手工和经验为主，没有采用科学技术对生产过程进行充分的优化。针对 我国的具体情况，提高制造工艺水平和自动化程度，完善调度管理体系、采取有效的调 度方法和优化技术，协调、调度好企业生产过程中出现的各种问题，才是我们急需解决 的问题，这对提高我国企业的市场响应能力具有十分重要的现实意义。 针对生产过程中实际存在的问题，本文采用p e t r i 网理论对j o bs h o p 动态调度问题 进行建模和研究，所建模型充分考虑了机器故障、设备维护、工件优先级等动态扰动情 况，即可用于制定生产计划又可对存在的常见的动态扰动及时做出响应，重新调度产生 新的调度方案，因此具有一定的理论价值与实用价值。 1 4 研究内容 在对j o bs h o p 动态调度问题进行分析的基础上，给出带有抑制弧的着色p e t r i 网的 定义和运行规则的形式化描述，建立j o bs h o p 动态调度问题的模型。该模型充分考虑 了机器维护、机器故障和工件优先级三种情况。最后，以c p nt o o l s 为工具，结合一个 3 基于p e t r i 网的j o b _ s h o p 动态调度问题的模删和仿真 j o bs h o p 调度问题实例，对模型进行了仿真研究，并对结果进行详细的分析。本文完成 的主要工作有： ( 1 ) 对j o bs h o p 调度问题进行分析，确定目前存在的问题及本文所要解决的问题； ( 2 ) 对p e t r i 网理论进行研究，给出带有抑制弧的颜色p e t r i 网的定义和运行规则的 形式化描述； ( 3 ) 在对j o bs h o p 动态调度问题进行分析的基础上，采用带有抑制弧的颜色p e t r i 网对其进行建模； ( 4 ) 以c p nt o o l s 为工具，结合一个j o bs h o p 调度问题实例，从带时间和不带时 间两个角度对模型进行仿真研究，并对结果进行详细的分析。 1 5 章节安排 本论文共分为五章，具体安排如下： 第一章绪论：本章主要介绍本论文的研究背景，以及国内外有关生产调度的研究现 状，然后相应地确立本文的研究内容及研究的意义。 第二章j o b调度问题和p e t r i 网理论：本章首先对度问题的特点和分s h o p j o bs h o p i 周 类等进行了描述，并分析了其存在的问题及发展趋势；详细阐述了p e t r i 网的基本理论和 着色p e t r i 网；介绍了基于c p n 的建模和仿真分析工具c p nt o o l s 。 第三章基于c p n i a 的j o bs h o p 调度模型：本章首先给出了带有抑制弧的着色p e t r i 网的形式化定义和运行规则，并据此对一个实例进行建模，然后从不带时间的角度用 c p nt o o l s 对模型进行了仿真，并对仿真结果进行了分析。 第四章基于时间约束着色p e t r i 网的动态调度模型：从带时间的角度，用c p nt o o l s 对实例再次进行建模和仿真，并对仿真结果进行了详尽的分析。 第五章总结与展望：总结了本文的主要研究工作，并阐明了本文的不足和今后的研 究方向。 4 第二章j o b _ s h o p 调度问题和p e t r i 网理论 第二章j o bs h o p 调度问题和p e t r i 网理论 2 1j o bs h o p 调度问题 从2 0 世纪5 0 年代起，生产调度问题因其实用性和重要性，一直被作为研究的热点， 近年来也随之成为运筹学和工业工程等学科中一个独立的分支。 2 1 1j o bs h o p 调度问题的描述 j o bs h o p 调度问题具有复杂性、多约束的特点，属典型的组合优化问题，很难获得 最优的解决方案。j o bs h o p 调度问题主要包含两方面的问题：( 1 ) 生产计划的制定，即 工件加工工序的制定；( 2 ) 针对生产过程中出现的异常问题，及时调整计划，保证生产 计划任务的完成。前一个问题是在生产之前进行，属于静态调度问题，其实质是通过将 工件的加工工序和加工机器进行优化组合达到某个性能指标最优，如加工时间最短，是 一个典型的n p 问题；后一个问题是在生产过程中进行，属于动念调度问题。与静态调度 问题不同，动态调度问题是根据加工过程中出现的异常情况重新对工件的加工工序和加 工机器进行优化组合，实时性要求比较高。 典型的j o bs h o p 动态调度问题可描述为：一个加工系统有m 台机器和刀个待加工工 件，每个工件包含一道或多道工序，工件的工序是预先确定的，工件的每道工序可由册 台机器中的多台机器加工，同时考虑生产过程中出现的设备故障、设备维护、工件交货 期的变化、紧急订单等动态扰动因素。动态调度的实质就是针对这些动态因素做出及时 正确的响应，对事先已经制定好的生产加工计划进行修改，使得车间的生产能够顺利、 有序的进行，并使得加工时间最短。 2 1 2j o bs h o p 调度问题的特点 车间作业调度是将生产任务分解，将任务安排到加工设备，实现最优加工的过程， 其主要特点有1 1 9 2 1 】： ( 1 ) 复杂性：j o bs h o p 调度的复杂性主要体现在建模复杂性、计算复杂性和生产 环境复杂性三个方面。首先，车问调度问题有大量的模型，但随着生产的发展，模型的 约束条件不断变化，新的调度模型不断替代旧的调度模型。其次，由于各种外界条件的 影响，j o bs h o p i n 度从计算时问复杂度看是一个n p h a r d m 题_ ，且随着调度规模的增大， 不可避免的面临严重的维数灾问题，导致在模型表达和分析计算上过于复杂。最后，生 产环境复杂性主要体现在生产过程中既要考虑工件的工艺路线、加工时间等还要考虑机 器、操作人员和运输系统之间的协调。 ( 2 ) 约束性：首先，工艺路线约束，每道工序必须等待其所有的前序工序加工完 5 l 基t - p e t r i 网的j o bs h o p 动态调度问题的模型利仿真 加工此道工序；其次，设备和人力资源约束，如加工机器、操作人员、搬运工具以 它辅助生产工具等是有限的。 ( 3 ) 多目标性：在实际的j o bs h o p 调度中，有很多待优化的性能指标，比如完工 、设备利用率、生产成本等，而且这些性能指标之间往往会产生矛盾，具体选择何 化性能要根据实际情况的要求而定。 ( 4 ) 离散性：j o bs h o p 调度具有典型的离散性，比如工件加工的_ 歼始时间、任务 达、操作人员的失误、订单的更改、机器故障的出现等都是随机发生的离散事件。 3j o bs h o p 动态调度问题的分类 s u r e s h l 2 2 2 3 1 等将动态扰动因素分成以下4 类： ( 1 ) 与工件相关的：包括工件随机到达、加工时间不确定、更改交货期、插入紧 单、工件优先级的变化和取消订单等情况； ( 2 ) 与机器相关的：包括机器故障、机器维护、负载有限、机器阻塞死锁和生产 冲突等情况； ( 3 ) 与工序相关的：包括工序延迟、质量问题和产量不稳定等情况； ( 4 ) 其它：如操作人员缺勤、原材料延期到达、原材料有缺陷、动态加工路线等 情况。 本文主要考虑设备维护、机器故障和工件优先级三种情况。 2 1 4j o bs h o p 调度问题的建模方法描述 类似于连续变量动态系统( c v d s ：c o n t i n u o u sv a r i a b l ed y n a m i cs y s t e m s ) ，在离散事 件动态系统( d e d s - d i s c r e t ee v e n td y n a m i cs y s t e m s ) 的研究中，建模问题仍然是研究的 重点。对于离散系统的建模和分析，基于所采用工具的不同，已形成了多种方法。对这 些不同的方法从不同角度进行分类，主要有以下几种分类方法： ( 1 ) 基于时间层面的分类。包括物理时间层面方法和逻辑时间层面方法。物理时 间层面的方法包括排队网络方法、摄动分析方法、极大极小代数法、有限递归过程方法、 通信序贯过程方法和仿真方法等，其特点是模型中可赋时，并能分析系统行为的时序化 过程；逻辑时间层面的方法包括有限自动机形式语言方法和p e t r i 网方法等，其特点是 模型中不可赋时，只能反映和分析表征系统行为的符号的顺序关系。 ( 2 ) 基于问题层面的分类。包括逻辑层面的方法、代数方面的方法和统计性能层 面的方法。逻辑层面的方法包括有限自动机形式语言方法和p e t r i 网方法等，用于研究 以符号顺序关系为特性的问题的建模、分析和控制；代数层面的方法包括极大极小代数 法、有限递归过程方法、通信序贯过程方法等，用于研究确定性时序化问题建模和分析； 6 第二章j o b _ s h o p 调度问题和p e t r i 网理论 统计性能层面的方法包括排队网络方法、摄动分析方法等，用于研究不确定系统性能与 优化问题的建模和分析。 ( 3 ) 基于模型属性层面的分类。包括确定性层面的方法和随机性层面的方法。确 定性层面的方法包括p e t r i 网方法、极大极小代数法有限递归过程方法、通信序贯过程 方法和有限自动机形式语言方法等，只能处理结构和参数为确定性的系统；随机性层面 的方法包括排队网络方法、摄动分析方法和仿真方法等，可对结构和参数为不确定性的 系统进行处理。 上述分类只是从整体和主流的角度进行的一种分类，并不是绝对的和一成不变的。 下面简单的介绍几种有代表性的建模方法。 ( 1 ) 排队网络方法 排队网络方法在d e d s 的建模和分析方法中，是形成较早和应用较多的一种方法。 对于一个排队网络模型，常可采用如下的特征对其特征进行描述：顾客相继到达系统 的间隔时间的分布；服务时间的分布；服务台的个数。这些特性构成了分析排队网 络过程性能的出发点。 排队网络方法的优势是能够考虑系统中的各种随机因素，并能较为细致的描述系统 内部的各种复杂关系，基于排队网络模型，易于从概率和统计的角度分析和优化d e d s 的过程性能。但其也有一定的局限性，主要表现在对所研究的排队系统引入的假设条件 过强，这大大限制了它的应用范围；另外，对系统参数的随机性假设通常也是和实际情 况具有较大的距离；再次，排队网络分析方法一般只能用在描述系统的稳态特性和分析 系统的平均性能，这对理论研究和某些工程应用同样是一个主要的局限性。 ( 2 ) 摄动分析方法( p a ) 摄动分析方法是1 9 7 9 年由何毓琦( y c h o ) 教授等人提出并发展起来的，它是 计算机仿真和排队论分析相结合的一种混合型方法。它以一次计算机仿真的数据为基 础，可有效克服在随机d e d s 计算机仿真中需要进行多次重复仿真而导致的大量仿真机 时问题。但该方法现在也存在定的不足之处：一是对相当多的实际问题，确定性相似 性条件往往难以满足；二是在随机排队系统的优化分析中，更有意义的是均值性能的梯 度而不是样本性能梯度的均值。 ( 3 ) 自动机形式语言方法 自动机形式语言方法是由r a m a d g e 和w o n h a m 开创的研究d e d s 的一种方法，这 种方法的核心是基于自动机形式语言的d e d s 监控理论，着重于研究d e d s 在逻辑层 次上的控制问题。基本特点是，采用自动机分别作为被控对象、监控器和闭环离散事件 7 基y - p e t r i 网的j o b _ s h o p 动态调度问题的模型和仿真 过程的逻辑层次模型，采用形式语言作为分析系统行为和综合监控器的基本工具。 相对而言，基于自动机形式语言的离散事件动态系统的监控理论，在处理标准逻辑 规范范围内的监控问题上已经形成了较为系统和较为完善的理论与方法，但在处理实 时、并发等更为复杂的规范范围内的监控方面则还有待于系统和成熟。 ( 4 ) p e t r i 网方法 p e t r i 网是一种以图形形式研究系统组织结构和动态特性的理论，尤其适合于对异步 并发系统的建模和分析。一个d e d s 的p n 模型的结构元素包括：用圆表示的库所 ( p l a c e ) 、用长方形或粗线条表示的变迁( t r a n s i t i o n ) 及带箭头的弧( a r c ) 。库所描述 d e d s 的可能状态，变迁代表d e d s 的可能的事件，通过弧建立局部状态与事件之间的 联系。 相比较于d e d s 的其他建模和分析方法，p e t r i 网在理论研究和实际运用中具有不可 比拟的优势，主要表现为：所建模型具有直观性和概括性；其可达性、活性、死锁、有 界性、安全性等属性具有明显的现实意义；分析过程兼顾定性和定量的领域；研究领域 可覆盖d e d s 的建模、分析、控制和综合的全部方面；应用方面具有对处理时间层次、 随机因素和复杂结构等工程问题的可扩展性。但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 网、有色p e t r i 网、随机p e t r i 网等，使其依然成为描述、 分析及控制d e d s 最有效的方法。 2 1 5j o bs h o p 调度存在的问题与发展趋势 虽然对车间调度领域的研究已有几十年的历史，但至今仍未形成一套系统的理论和 方法，主要存在的问题总结如下： ( 1 ) 研究的大多数问题只是针对较小的规模，大规模问题仍然比较棘手，应从理 论上更深入研究其模型简化问题。 ( 2 ) 目前对j o bs h o p 调度问题的研究很多，但大部分仅限于单一目标的优化。应 建立包括生产成本在内的多目标j o bs h o p 调度模型，充分考虑企业对成本的关注，使 得调度模型更好的反映实际情况。 ( 3 ) 大部分的模型是针对具体问题建立的，随着约束条件的变化，缺乏一定的通 用性，因此对一般性j o bs h o p 问题的框架、模型的研究具有更重要的现实意义。 8 第二章j o bs h o p 调度问题和p e t r i 网理论 ( 4 ) 大部分都是针对静念j o bs h o p 进行的建模和分析，建模时附加了过多约束条 件，与实际应用有定的差距。实际的生产环境是动念的，由于机器故障、工件优先级 的变化、设备维护等原因，往往需要重新调度。重新调度问题的实质是在系统受到扰动 后，重新安排工件在机器上的加工工序，产生新的调度方案。重新调度的目标是以尽量 短的时问完成对原有调度方案的修改，原方案与新方案之问实现合理的衔接，使对系统 性能的影响降到最低，保证实时生产的高效性与动态扰动反应的灵活性。 今后在对车间调度进行研究的时候，可从以下几个方面进行深入的研究： ( 1 ) 更紧密的联系实际，找出车间管理与调度诸多因素的内部关系，建立最能反 映生产需要的调度模型。 ( 2 ) 更深入的研究车间计划与车间调度之间的关系，建立计划与调度的集成模型， 从整体上进行优化研究。 ( 3 ) 对先进制造系统模式进行深一步的研究，以实现优化目标之间的平衡。 总之对j o bs h o p 调度领域这一具有n p h a r d 特性的研究，随着社会的进步和科学 的发展，其发展趋势必然是集成化、多目标化、动态实用化和高度次优化。 2 2p e t r i 网理论介绍 2 2 1p e t r i 网简介 - p e t r i 网是由德国学者c a r l a p e t r i 博士于1 9 6 2 年提出【2 4 】，近些年来，随着理论上的 不断完善和应用上的不断扩大，这种方法已成为在逻辑层次上对离散事件动态系统进行 建模和分析的主要方法之一。本质上，p e t r i 网方法是一种以图形形式研究系统组织结构 和动态特性的理论。作为图形工具，p e t r i 网除了具有类似流程图、框图和网图的可视描 述功能外，它还可通过托肯( t o k e n ) 的流动模拟系统的动态和活动行为，所以可以说， 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 网、面向对象p e t r i 网等高级 p e t r i 网。 2 2 2 基本p e t r i 网的概念 定义1 一个基本p e t r i 网表示为一个六元组，即刚= ( p ，t ，f ，m ，j ) p = 局，) 为有限库所的集合，m 为变迁数量一r m 0 ； t = t i ，2 ，乙) 为有限变迁( t r a n s i t i o n ) 集，n 为变迁数量且刀 0 ； 尸n t = a ( 集合p 和集合t 不想交) ，pu t o ( 集合p 和集合t 不同时为空) ； ，( p xt ) l ) ( t xp ) ( 关系f 只存在于集合p 和集合t 之间) 为节点流关系集， o 基丁p e t r i 网的j o bs h o p 动态调度问题的模型利仿真 即为有向弧集，其中p t 为连接库所到变迁的有向弧，t p 为连接变迁到库所的有向 弧： w ：f 一 1 ，2 ，) ( 关系集f 到自然数的映射) 为有向弧的权函数； m ：p 专 o ，1 ，2 ， ( 集合p 到非负整数的映射) 为状念标识( m a r k i n g ) ； 眠：p - - + o ，l ，2 ， ( 集合p 到非负整数的映射) 为初始标识( i n i t i a lm a r k i n g ) 。 p e t r i 网图是对p e t r i 网的六元组的一种图形化 表示，在p e t r i 网图中，p 代表“库所”节点集，t 卜q 卜_ c 卜十叫3 代表。变迁，节点集，f 代表节点间的有向弧集， p 1t lp 2 t 1 p 3 代表以有向弧的“权 为元所构成的向量。 f i g 2 1p e t dn e t 标识p e t r i 网图的组成和形式可用如图2 1 所示 的例子来说明。 ( 1 ) 库所节点和变迁节点。图中库所节点集尸采用符号“o ”( 圆圈) 表示；“变 迁 节点集丁采用符号“l ( 粗线段) 表示。 ( 2 ) 有向弧。从库所节点p 指向变迁节点，的一个有向弧为( p ，t ) ，且称此库所p 为 变迁珀勺一个输入，此变迁f 为库所p 的一个输出。从变迁节点r 指向库所节点p 的一个 有向弧表示为( f ，p ) ，且称此库所p 为变迁f 的一个输出，此变迁t 为库所p 的一个输入。 ( 3 ) 有向弧的权。为简化标识p e t r i 网的图的结构表示，把多重输入或多重输出的 有向弧表为加权有向弧，当权重为l 时常省略不写。 ( 4 ) 库所中托肯数的表示。在标识p e t r i 网图中，采用在库所节点中标注相应的黑 点数，以表示此库所所包含的托肯数。 ( 5 ) 状态标识。网图的状态标识m 定义为如下的一个行向量： m = m ( a ) ，m ( ) 】。图2 1 所示例子，现在的状态标识为：m = 【2 ，1 ，0 】。 ( 6 ) 初始标识。初始标识对应于状态标识m 的初始设置，网图的状态标识定 义为如下的一个行向量：= 【m o ( 届) ，m 。( ) 】。 2 2 3p e t r i 网变迁的发射规则 1 ) 变迁使能条件 在标识m 下，对v t t 被认为是具有发射权的，即变迁t 为使能，则其满足如下条 件： b t ，若( p ，) f ，贝0m ( p ) w ( p ，) ，其中，= pi ( p ，f ) f 2 ) 标识变化规则 若v t t 在标识m 下使能，则按照如下规则变化到新的状态标识m ： 1 0 第二章j o b _ s h o p 调度问题和p e t r i 网理论 v p p ，m ( p ) = m ( p ) 一w ( p ，f ) i f p 。f m ( p ) + w ( t ，p ) i f p ， m ( p ) 一( p ，f ) + w ( t ，p ) i f p f 。n 。， m ( p ) e l s e 其中，f 。= pi ( f ，p ) 日，。，= pj ( p ，f ) f 。 2 2 4p e t r i 网的基本性质 p e t r i 网的基本性