（计算机应用技术专业论文）基于petri网和pso算法的jsp优化调度方案的研究.pdf

摘要 生产调度是对生产过程进行作业计划，在生产制造、交通运输等系统中起着重要的 作用。车间调度是一类典型的生产调度，从数学规划的角度看，车问调度问题可以表达 为：在等式或不等式约束下，优化目标函数。车间调度的核心问题是模型和算法，其中 有效的调度模型是车间调度问题的重要研究内容。有效的车间调度模型，可以大大提高 生产效益和生产资源的利用率，可以在设计之初，发现并克服车间调度系统模型可能存 在的致命错误。p e t r i 网不仅能描述资源的共享、冲突、互斥、并发和不确定性，而且 能进行定量分析和定性分析。p e t r i 网作为一种图形化和数学化的建模工具，与传统的 建模、分析和控制方法相比，能够提供一个集成的建模、分析和控制环境，它能较好地 描述离散事件的动态过程，为车间调度的设计提供便利。目前，p e t r i 网建模理论己成 为车间调度系统中建模与分析的主流技术之一。粒子群算法是一种基于群智能的进化类 算法，也是一种模拟鸟群觅食的仿生算法，具有显式的计算模型，操作和实施也很简单。 本文以p e t r i 网和粒子群优化算法为工具，对具有多条加工路径的车间调度问题进 行研究。通过算例的验证，同时与其他学者提出的相关算法进行比较，证明了该算法的 优越性。 本文的主要研究工作和取得的成果概括为以下几个方面： 1 、所研究的p e t r i 网调度模型可适用于加工多种工件。每种工件有多条加工路线， 要求制定一个生产方案，为每个工件决定一条加工路线，同时保证目标函数的最优，即 生产周期最短，根据以上要求建立了相应的p e t r i 网模型。 2 、根据目标函数和p e t r i 网模型，提出一种针对车间调度问题的改进的编码粒子群 算法，并分别对静态和动态调度进行了优化。 3 、最后以具体的车间调度系统为例进行求解，以懈t l a b 为工具，实现所提出的算 法，对比不同算法的结果，用实验数据检验算法的优越性。 关键词：粒子群优化算法；车间调度；p 删网 a b s t r a c t s c h e d u l i n gi sma ：i 【i n gt h ep l 锄f o rt 1 1 ep r o d u c t i o np r o c e s s ，w h i c hp l a y st h el e a d i n gr o l ei n t l l em 籼f a c t u r ea i l d 仃a n s p o r t a t i o n j o bs h o ps c h e d u l i n gi sal 【i n do ft y p i c a lp r o d u c t i o n s c h c d u l i n g ，f 而m l em a t h 锄a t i c a lp r o 伊猢i n gp o i n to fv i e w j o bs h o p 毗e d u l i n gp r o b l 锄 c a i lb ee x p r e s s e da s ：i nm ee q u a t i o no ri n e q u a l i t yc o n s 仃a i n t s ，t l l eo p t i m i z a t i o no ft l l eo b j c c t i v c 劬“o n t h ek e n l e lp r o b l 锄o fj o bs h o ps c h e d u l i n gi sm em o d e l 锄dt l l ea 1 9 0 r i t m ，觚d e 胁i v es c h e d u l i n gm o d e li s t l l ei i i l p o n 咖p a no ft l l ej o bs h o ps c h e d u l i n 吕e 仔撕i v e s c h e d u l i n gm 劬o d sc 肌g r e a t l yi i i l p r 0 v e l ep r o d u c t i o nb e 6 ta n d “l i z 撕o nf a c t o r b y m o d e l i n g 锄da i l a l y z i i l gj o bs h o ps c h e d u l i n g ，w ec 锄f i n dm es y s t e m s f - a u l t sa n dc 锄d i a g n o s e 孤dr c c o v e rm 锄i i lm ep r o c e s so fr e a l - t i m ec o n t r o lm o 他e 觞i l y n o w ，b e c 钒塔ep 舐n e t s 锄 d e s c r i b et l l es h a r c ，c o n n i c t n l u t 既，c o n c u r r 印c ea n d 岫c 碱n t ) ro fr e s o u 髓a n dt l l c i rm o d e l c 觚b c 锄a l y z e dq 啪t i t a t i v e l ya n dq u a l i 伽v e l y w i t l l 叫i t i o n a lm o d e l i n g 锄a l y s i sa n d c o n t r o lm e m o d s ，p “n e t s 嬲t l l e 乎a p l l i c a l 觚dm a m 锄a t i c a lm o d e l i n gt o o l s ，c a np m d e 锄 i r l t e f a t e dm o d e l i n 吕锄a l y s i s 锄dc o 曲r o l 翎啊m n m e l l t i tc 觚b e t t e rd e s 嘶b et l l e d i s c r e t e e v 饥t sd y n 锄i cp r o c e s s ，t l l ed e s i 印f o r 圮s h o ps c h 。d u l i n gi sc 0 n v e i l i 锄c e s “e r a ll 【i n d so f p e t r in e t sh a v eb e c o m et l l e i n l p o r t a mm e l o d so fm o d e l i n g 锄ds c h e d u l i n gj o bs h o p s c h 。d u l i n g p a n i c l es w a mo p t i m i z a t i o ni s t l l e e v o l u t i o n a d ，a l g o r i m mb a s c do ns w 锄 i n t e l l i g e n c ea i 】【dt h eb i o i l i ca l 鲥m mn l a ti m i t a t 岱m eb i r ds w 锄t os e e kt 1 1 ef o o d p a r t i c l e s w 锄o p t i m i z a t i o nh 勰l eo b v i o 憾c o m p u t “o nm o d e l ，锄di se 弱yt 0b e 而e do u t 姐dh 雒 9 0 0 do p t i m i z a t i o np e 而n i l 锄c e t h ep r e s e n td i s s e r t a t i o nu s 骼p e t r in e t sa n dp a r t i c l es w 砌o p t i m i z a t i o n 勰at 0 0 lt 0 s t i l d yt l l ej o bs h o ps c h e d u l i n gp r o b l 锄s 、) i r i mm u l t i p l ep r o c e s sp l a n t s t h ea l g o r i l i i li s c o m p a r e dw i t l lo l e rs c h e d u l i n ga l 鲥l m sa n di st 髓t c db ys t 锄d a r db e n c h m a 呔s c h 。d u l i n g p r o b l 锄t h er e s u l th a ss h o 、nt h a tt h ep r o p o s e da 1 9 0 r i t l l mi se x c e l l 锄t t h e 砸n c i p a lr e s e 鲫c hr e s u l t s 锄dc o n t e n t sc 觚b e0 u t l i n e d 嬲f o l l o w i n g ： 1 t l l es c h e d u l i n gp 嘶n e t sm o d e lc o u l d b ea p p l i e dt op r o c e s s i n gav 撕啊o f j o b s t l l e m o d e ls t u d yap r o d u “o np l 锄f o r c hj o bw i mm u l t i p l ep r o c e s sp l a i l t s ，州l ee 1 1 s 谢n g s e l e c t i n gm eo p t i m a lr e s u l t so ft l l ep r o d u 吐i o nc y c l e ，访a c c o r d 觚c ew i t l lt h er e q u i 懈n 伽临t 0 c s t a b l i s hm ec o 仃c s p o n d i n gp 嘶n e t sm o d e l 2 b a s e do nm a t i l 锄a t i c a la 1 1 dp 嘶n 就m o d e l ，访吣c e d 觚i m p r o v e dc ( d i n gp a n i c l e s w 锄a l g o r i t l l i i lb 嬲c ds h o ps c h e d u l i n g 邮b l 锄t l l es t a t i c a i l dd ”锄i cs c h c d u l i n ga r e o p t i m i z o d 3 f m a l l y a c l l i e v e dt l l ep r o p o s e da l g o r i t h mo f j o bs c h c d u l i n gp r o b l e mw i lm a t l a b r i l e a l g o r i t h mi sc o m p a r o dw i t l lo t l l e rs c h e d u l i n ga l g o r i m m s t h er c s u l th 鹤s h o w nm a tt l l e p r o p o s e da l g o r i t l l l l li se x c e l l e n t k e yw o r d s ：p a n i c l es w a r mo p t i m i z a t i o na l g o r i t h m ；j o bs h o ps c h e d u i i n g ；p e t r in e t i i i 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究 所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包 含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出 重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到 本声明的法律后果由本人承担。 作者签名：寿柳f日期：年月幻日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同 意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许 论文被查阅和借阅。本人授权长沙理工大学可以将本学位论文的全部或 部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制 手段保存和汇编本学位论文。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“”) 作者签名：看硐f日期：m ) 年月阳日 导师签名d 忆砖 醐：呼瑚堋 第一章绪论 信息技术的发展推动了企业结构的不断变革，促进了生产自动化水平的进一步提高。 生产的自动化和灵活化已经成为了改造传统企业和发展新兴企业的基本目标。随着计算 机自动化技术的发展，为了实现企业的生产灵活化和自动化，产生了一类新的企业生产 系统。车间调度系统是一类非常复杂的离散事件动态系统，因此需要对车间调度系统有 一个全面而又准确的了解，再为其建模，并对其模型进行深入的研究。 1 1 课题背景及研究意义 车间调度问题( j o bs h o ps c h e d u l i n gp r o b l e m ，j s p ) 是一类典型的生产调度问题， 实质上就是一种离散的事件动态系统( d i s c r e t ee v e n td y n 锄i cs y s t e m ，d e d s ) ，即由 异步发生的、离散的事件按照一定的运行规律，而且这些运行规律相互作用，最后导致 系统状态演变的一类动态系统。如何根据企业生产产品的信息和企业的制造能力进行生 产计划与调度的优化，如何对j s p 中的信息和流物合理有效的安排，从整体上提高车间 调度的效率和性能都是车间调度问题的关键。车间调度问题所研究的主要内容可归结为 j s p 建模和j s p 优化调度性能分析这样两个核心内容。 目前对于j s p 从应用范围和建模方法上大体可划分为三个层次：1 ) 逻辑层次，在逻辑 时间层次上来研究车间调度系统中的时间符号和状态符号的序列关系，一般在这个层次 上采用的建模方法有：形式语言有限自动机，时态逻辑，p e t r i 网。2 ) 代数层次，在物 理时间层次上来研究车间调度系统的运动过程和代数特性，在这方面应用最多的是极大 极小代数法和赋时p e t r i 网。3 ) 统计性能层次，在统计性能的层次上研究随机情况下车 间系统的各种平均性能及其优化，主要的数学工具有排队论，广义m a r k o v 链和随机 p e t r i 网。它这些方法的侧重点和描述的手段都不相同，但是其中各式各样的p e t r i 网 已经成为j s p 中建模与分析的主流技术之一。 1 9 6 2 年，德国的c a r la d 硼p e t r i 博士提出了p e t r i 网理论，发展到现在，已经成 为具有多种抽象层次和严密数学基础的建模工具，并在自动控制领域和计算机科学技术 领域得到广泛的应用，如并行程序的分析设计、系统可靠性分析、网络性能分析、分布 式系统的分析和控制、人工神经元网络、决策模型、软件工程和知识推理等领域陋1 0 1 。 与传统的系统建模分析方法相比，p e t r i 网作为一种数学化和图形化的建模工具，能提 供一个集成的建模和分析环境，为系统的设计提供便利。它尤其能够较好地描述离散事 件的动态过程，并能够精确的描述事件的并发、冲突和顺序关系。有关p e t r i 网的相关 概念和定义参见文献 1 1 。 粒子群算法( p a r t i c l es w a r mo p t i m i z a t i o na l g o r i th i l l ) 简称p s 0 ，也称为微粒群算 法。美国的k e n n e d y 博士和e b e r h a r t 博士别于1 9 9 5 年提出了一种基于群智能的优化算 法，目前该算法已经有效的应用在神经网络训练、模糊系统控制、函数优化。该算法主 要用于求解连续空间域的优化问题，在连续空间域的优化问题中所表现出来的良好性 能，促使很多研究者展开了该算法在离散空间域的优化问题的研究，目前，将这种连续 空间域的p s 0 算法用于解决离散空间域的优化问题，如组合优化问题，已成为p s o 算法 的重要研究方向。 j s p 则是属于一类典型的组合优化问题。调度系统所需解决的是作业的次序问题以 及资源的分配问题，调度问题属于离散空间的非数值优化问题，随着调度规模的增加， 如资源数量的增加，调度问题的求解也越来越困难，难于用一般的优化方法，比如枚举 的方法或整数规划的方法去求解，基于启发式规则的优化法也很难得到较好的调度解。 展开j s p 中的p s 0 方法的研究是p s 0 算法研究领域的一项重要内容。对j s p 中的p s o 方 法进行研究，一方面探讨了p s o 方法在离散空间领域优化问题的研究，拓展了p s 0 方法 的研究和应用领域，为求解其他的组合优化问题提供了思路和经验；另一方面，也拓展 了一种新的智能优化方法。 近年来，国内外对p e t r i 网在j s p 中的研究取得了一定的进展，对p e t r i 网做了改 进和补充使p e t r i 网适用于复杂的j s p 分析和建模，但由于在j s p 的p e t r i 网方法还存 在着可达图中可能会含有大量不确定点及可能分支的问题，为模型的判断和求解带来困 难，因此在描述较复杂的j s p 时，用p e t r i 网建模的方法易出现网规模急剧增加而无法 对p e t r i 网模型分析求解的现象。k i b r a h i m n 3 1 等用赋时、有色的p e t r i 网建模并应用 到j s p 中，使确定性的赋时有色p e t r i 网模型与启发式算法有效结合，解决目标函数为 生产周期最短的j s p ，该文献没有分析比较p e t r i 网模型和其它算法相结合的优劣。 在车间调度的p e t r i 网模型中，为寻找最优的调度，必须在p e t r i 网的可达图中找到 对应的从开始状态的节点( 表示系统的初始状态) 到目的状态节点( 表示系统的终止状 态) 的变迁触发序列。随着系统的变迁与位置的数目的增加，可达图的规模急剧膨胀， 所以要在可达图中举出所有的触发序列，来比较相应的目标函数( 如所有工件的加工时 间) ，从而确定最优的变迁触发序列，需要花费很长的时间，甚至是没有办法实现的。 因此，可以采用p s o 算法，产生必须的部分可达图，从而确定最优或次优的路径。另 外在p e 仃i 网的可达图中进行调度搜索时所存在的缺陷，也可以通过改进的p s o 算法得 到弥补，从而提高其收敛度。所以，研究p e t r i 网技术以及p s 0 算法的综合优化技术具 有较大的实际意义。 综上所述，p e t r i 网技术以及p s 0 优化技术均为调度优化策略提供了有效的解决方 法，然而鉴于两种方法各自的特点及不足，研究两种技术的综合优化处理技术，使之互 相弥补，从而寻求一种更为有效的调度优化处理方案有着较大的理论及实际意义。 1 2 研究动态及现状分析 目前，p e t r i 网在j s p 中的研究主要集中在以下的几个方面： ( 1 ) 基于p e t r i 网的j s p 建模与仿真。p e t r i 网最适合用于j s p 建模，在j s p 的建模 与仿真应用得最为普遍。j s p 的参数不但多而且复杂，难以描述，p e t r i 网的应用则可 以使其描述变得简单，从p e t r i 网中的标识的变迁情况，可以清晰地观察到有关活动及 其各个要素间的相互关系。p e t r i 网给程序设计带来了很大的方便，大大的节省了仿真 软件的开发时间。n a r a h a r iy 和n v i s w a n a d a h a m 运用p e t r i 网对j s p 进行建模和分析 n ；b e c k 和k r o g h 运用p e t r i 网对由两个机器人组成的装配系统进行了建模n 朝；江志 斌等在高级的面向对象的p e t r i 网的基础上提出了适合现代先进j s p 建模的变结构 p e t r i 网 1 6 ，1 们。 ( 2 ) p e t r i 网控制器。利用p e t r i 网模型，在硬件设备和软件条件的辅助下可以直接 生成p e t r i 网控制器，在经过算法转换或者编译后，可以直接生成系统的控制代码或者 数据。v a l e t t er 提出了p e t r i 网在设计和实现系统控制中的作用，并且在欧洲首次提 出了应用于工业加工控制中的标准的p e t r i 网n 引；w a n gl 等人运用面向对象p e t r i 网 为一个自动单元制造系统建立了控制构架n 钔等。 ( 3 ) 基于p e t r i 网模型的j s p 分析。根据p e t r i 网模型的信息，可对j s p 进行全面 的分析。从p e t r i 网模型出发，可以分析出车间调度系统的生产能力、生产率、机器利 用率和完好率、制造提前期等情况。比如，通过对p e t r i 网模型中标记( t o k e n ) 情况的 考察，可以看出正在加工的工件的情况；利用时间p e t r i 网模型，可以考察j s p 的生产 率和周期生产等情况。 ( 4 ) 基于p e t r i 网模型的j s p 生产调度。生产调度系统的两个关键问题是调度的算 法和调度的模型，基于p e t r i 网的调度模型使我们可以高效地实施车间作业的调度计 划；可以缩短调度计划所需要的时间；当调度系统遇到干扰时，还可以迅速且可靠地做 出反应，及时改变调度计划；可以根据事先给定的规则对任何调度序列进行优化；可以 产生调度系统的备用加工序列；可以增强调度系统的功能，可以将机器设备的维修保养 等问题考虑在内，提高车间调度系统的柔性。 在p s o 算法中，粒子的位置和速度都用连续的参数形式表示，速度和位置的更新也 是在实数域中连续的变化。这种连续的实数域中的速度、位置计算模型限制了p s o 算法 在离散组合优化问题领域的应用。p s 0 算法在连续空间领域的函数优化问题( 比如数值 优化问题) 已得到了非常有效的应用，但是该算法在生产调度系统中的研究还很少。从 查阅的国内外文献来看，近几年p s o 算法才开始被用于求解组合优化问题，主要涉及旅 行商题( t r a v e ls a l e s 帆np r o b l e ，t s p ) 汹2 1 1 和车辆路径优化问题( v e h i c l er o u t i n g p r o b l e m ，v r p ) 挖1 等。 国内的p s 0 算法的研究还处于起步阶段，王奕首、杨志鹏乜町等人对p s o 算法进行 了综述，武志峰矧、赵秋亮、寇保华乜7 1 、z h a n gw e n 啪3 等人在p s 0 算法的改进方面做 了一定的工作，在神经网络训练汹1 、平面选址啪1 、函数优化口等领域，国内学者也展开 了相关的研究。 拓展p s o 算法在j s p 中的应用是非常有意义的工作，p s o 算法是一类基于群智能的 进化类算法，目前已有相关文献展开了p s 0 算法和遗传算法的比较，而对于p s o 算法与 进化策略算法的比较，目前还缺乏相关的研究成果。 1 3 本课题的内容 本论文的研究内容主要是基于p e t r i 网建模技术及p s o 算法的车间调度优化综 合处理的方案，并利用该优化方案针对j s p 的调度序列进行优化处理，最终获得最 优或次优的调度结果。主要工作及贡献如下： 1 、数学模型的建立：所研究的调度模型是加工多种工件，每种工件具有多条加工 路线，要求制定一个生产计划，为每个工件决定一条加工路线，并满足生产周期最短 这个目标函数； 2 、建立p e t r i 网模型：根据数学模型( 目标函数和约束条件) 和具体的生产系统 中的加工工件的信息建立p e t r i 网模型； 3 、并结合所建立的p e t r i 网模型，提出并设计出一种针对j s p 问题的粒子编码方 法，优化调度结果，最后以具体的车间调度系统为例，用m a t l a b 工具实现所提出的 算法，用实验数据验证算法的有效性。 本课题的创新点体现在以下两点： l 、先进性：对p s 0 算法进行了改进，并提出一种有效的车间调度系统中作业的优化 调度综合处理的方案； 2 、实用性：利用本文所提出的p e t r i 网模型分析方法以及改进的p s o 算法的优化策 略能够得出调度车间的最优调度解；该方法适用于一般的j s p 组合优化问题。 1 4 本课题的组织 第一章阐述了该课题的研究背景及其意义、分析了国内外研究动态及现状，并提出 了作者对该课题的研究内容和创新点。 第二章阐述了p e 仃i 网关键理论与技术和p e t r i 网对车间调度建模的基本思想。 第三章研究了车间调度系统及p e t r i 网和粒子群优化算法在车间调度系统中的应用。 第四章研究了粒子群优化算法，并提出了一种改进的编码粒子群优化算法。 第五章通过仿真实验，对p 嘶网建模和粒子群优化算法分别在静态车间调度和动态 车间调度中的优化结果进行了分析。 第六章是总结与展望，对全文所做的工作进行了总结并提出进一步的展望。 4 第二章p e t r i 网关键理论与技术 1 9 6 2 年，德国的博士，c a r la d a mp 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 网模型，可对将要开发的系统进行评价和改进。各 种形式的p e t r i 网，已经成为j s p 分析与建模的主流技术之一。 2 1p e t ri 网的定义 p e t r i 网，是由变迁、库所( p 1 a c e ) 、托肯( t o k e n ) 和有向弧组成的一种网，p e t r i 网是一种有向网。库所是用于描述系统的状态，变迁是用于描述修改系统的事件。 定义2 1p e t r i 网的结构描述为： ( 1 ) p = ( 尸，r ，d ，眠) ( 2 ) p = a ，) 是位置的有限集合，册为位置的个数， 棚 o ( 3 ) 丁= ， 是变迁的有限集合，刀为变迁的个数，一 o ，丁n p = ( 4 ) j ：p r 一是输入函数，定义了从p 到z 的有向弧线的重复数或者权的集合， 这里的f o ，l l 是非负整数集 ( 5 ) d ：r p 寸是输出函数，定义了从丁到p 的有向弧线的重复数或者权的集合 ( 6 ) 眠：系统的初始状态标识，即初始时，标记各位置中的分布 在表示p e t r i 网结构的有向图中，圆表示位置；长方形或粗实线段表示变迁；从位 置p 到变迁丁的输入函数取值为非负整数，记为j ( p r ) = 功，用从尸到丁的一条有向 弧线表示，并旁注国；从变迁r 到位置p 的输出函数取值为非负整数缈，记为d ( p ，f ) = 国， 用从r 到p 的一条有向弧线表示，并旁注国。若力= 1 ，则不必标注缈。，和d 均可以表 示咒聊的非负整数矩阵，称为伴随矩阵。 2 2p e t ri 网的基本性质 2 2 1 可达性 定义2 2 如果从初始的标识眠出发，触发一个变迁序列，产生标识鸠，则称m ，是 5 从m 。可达的。所有的m 。可达的标识的集合，都称为可达标识集或者可达集，记为 尺( m 。) 。p e t r i 网的可达性，可以用来描述车间调度如下两个问题： 1 、车间调度系统是按一定的规则来运行的，系统是否能实现一定的状态或者不要 出现我们不期望的状态，是车间调度系统运行的关键问题。车间调度计划的验证是典型 的问题，即如果我们按照一定的调度计划进行生产，我们的生产任务是否能够完成。 2 、达到一定的状态是车间调度系统的要求，系统的运行规则如何确定，是一个典 型的问题。 2 2 2 有界性与安全性 定义2 3 给定p = ( p ，r ，d ，m 。) ，以及它的可达集r ( 眠) ，对于位置p p ，如果 v m 尺( 眠) ：m ( p ) 后，则称p 是七有界的，此处的七是正整数；如果p e t r i 网的所有 位置都是尼有界的，则称p e t r i 网是尼有界的。七= l 时，即当某位置或p e t r i 网是有界 的，则称该位置或p e t r i 网是安全的。 一般的，位置是用于表示车间调度系统中的工具、工件等，还可以用于表示资源的 利用等情况。确认这些存放区是否满出，或者资源的容量是否满出是非常重要的。p e t r i 网的有界性，是检查p e t r i 网所描述的系统是否存在满出的有效办法。当位置用于描述 一个操作时，该位置的安全性，能够确保系统不会重复启动某一正在进行的操作。 2 2 3 活性与死锁 定义2 4 对于变迁f 丁，在任何一个标识m 尺下，如果存在某一个变迁序列墨， 这个变迁序列的触发，可以使这个变迁f 可触发，则称该变迁是活的。如果一个p e t r i 网中的所有的变迁都是活的，我们就称该p e t r i 网是活的。 死变迁与死锁，都从反面描述了p e t r i 网的活性。如果v m 尺，不存在从m 开始 的变迁序列，使该序列的触发可以让f 触发，则变迁f 为死变迁。若存在m 尺，在m 下， 没有任何变迁可以触发，则称p e t r i 网包含死锁，这个标识就是死标识。 不合理的资源分配策略，或者某些资源的消耗完毕是出现死锁的原因。在j s p 系统 中，许多资源( 如机器、缓冲区存放空间等) 都是共享的，在资源共享的系统中，下列 四种情况中，只要满足某一种情况时，就会导致系统的死锁。 1 、互斥：系统中的两个或两个以上的过程不能同时使用系统中一个资源，系统中 每一个过程，都是排斥系统中的其他的过程，对该资源的占用。 2 、占用且等待：如果系统中的某一个或者某些资源已经被一个过程占用，同时， 这个过程又还在请求占用系统中的其他资源。 3 、无抢占：系统已经分配给某一过程的资源，别的过程不能从这个过程中抢走， 除非这个过程使用完了，而且释放了系统中的这个资源。 4 、循环等待：系统中，两个或者更多的过程排成一个链，这个链上的每一个过程， 都在等待链上的下一个过程占用的资源。 6 p e t r i 网的活性，意味着p e t r i 网在从初始状态眠可达的任意标识肘下，总是可 以通过逐步触发某变迁序列，来使任意的变迁可触发。因此，如果p e t r i 网是活的，则 该系统就不存在死锁的问题。 2 2 4 冲突 冲突，反映的是系统资源的竞争情况，一个p e t r i 网的结构冲突是指，一个至少具 有两个变迁的变迁集合，集合中的变迁具备公共的输入库所p 。一个有效冲突是指，存 在一个结构冲突和一个标识，在这个标识下，处于结构冲突中的变迁的共同输入库所p 的标识数，少于被该标识使能的p 的输出变迁的加权数。 图2 1 中，两个加工过程都需要资源阢，进行它们各自的操作，这是一典型的冲突 问题。像前面提到的，与厶同时使能，但是两者中，只能有一个可以被激发，所以必 须做出决策，以决定谁先被激发。最简单的方法是随机确定。要么激发f l ；要么激发。 假设f l 在冲突中获胜，就被激发并消耗儿中的托肯，最后乞被激发，将一个托肯放回 儿，资源得以释放。 2 3 分层p e t ri 网 图2 1 资源竞争 分层p e t r i 网的描述和构建，建立在“细化”的基础上的，“细化 ，实际上就是变 换前后两个p e t r i 网之间的映射，p e t r i 网之间的映射描述了p e t r i 网之间的节点以及 连接弧线的对应关系。在文献 3 2 中，给出了分层p e t r i 网的形式化描述，在这里，本 文将引用文献 3 2 中相关的基本概念。 定义2 5 设= ( s ，r ；，) 是一个p e t r i 网，j = su r ，z x 是中元素的子集。 则有： 1 、x 在中的边界定义为： w ，( x ) 工x y 砂x x ：( z ，y ) ，v ( y ，工) ，) ( 其中符号“一代表集合间的 7 差运算) ，x 在中的环境定义为：阴( x ) ：= 耐( x x ) 2 、设l = ( 墨，石；e ) 和2 = ( 最，互；五) 是p e t r i 网，：五专五是一个映射，则 ( 2 ，l ，厂) 称为一个网射，当且仅当： ( 1 ) 厂( e ) e u 识 ( 2 1 ) 耐，表示五中的单个元素； ( 2 ) v f 乃v j 八j 广：厂o ) = 厂o ) v ( 厂o ) 石 厂( s ) 墨) ( 2 2 ) 其中厂( ( x ，j ，) ) = ( 厂( 工) ，厂( y ) ) 式( 2 1 ) 表明，映射厂保持了除节点标识外的网结构；式( 2 2 ) 表明，映射厂尽 可能保持了节点的类型( 位置或者变迁) 。 3 、在网射( 2 ，m ，厂) 中，2 称为是l 的一个细化，而l 称为是2 的一个抽象。对 x 五，是2 的子网，如果满足x = 厂_ 1 ( 工) ，且有f = e 厂、x ”，则称是石的细化， x 是的i i 辈( p r e d e c e s s o r ) 。 4 、一个网射( 2 ，i ，厂) 称为一个商，当且仅当厂在节点和弧上是满射，即： ( 五) = 五，互厂( 互) = 0 定义2 6 设i ，m 为p e t r i 网，在映射z ，正一。下，( 川小m ，z ) ，f = l ，万，是 商。则称y = ( m ，石，z ，m ) 为一个细化序列。 如果在每个细化序列中，都增加一个新网，从l 到新网的映射为厶，而新网中只包 含单一的元素“上 ，则网络映射厶，z 一。，在节点集合4u 上) 上就形成了一个树型 结构，其中树根为上。树结构是节点集合的偏序。“ 表示“前辈 关系导出的树上的 偏序，即工 y 表示“工是y 的前辈”；x ) ，：x y vz = ) ，。树根上总是在偏序关系下 的最小元素，树上的叶子节点，是最大的元素。则以x 为根节点的子树的叶子节点的集 合是：跆矽( 工) 车 j ，工+ j ，+ = y ，其中工+ 芦 z z z 为x 的子树上的节点集合。 定义2 7 设( s ，r ；f ) 是一个p e t r i 网，映射厂：x 专x u 上 ，x = s u 丁。称 删= ( s ，r ；，厂，上) 是一个分层p 州网，当且仅当： ( 删1 ) 无向图g 删= ( x u 上 ， ( 工，j ，) 厂( z ) = y v 厂( y ) = x ) 是连通的； ( 删2 ) f s 彪矿( 上) 拓矿( 上) ； ( 删3 ) 坛s ：6 九( 彪旷( 工) ) 互s ；坛r ：6 九( 彪矽( 石) ) 丁。 其中( 肼1 ) 表明，映射厂在节点集合x u 上 中形成了一个树结构，“上”是树根。 通过“细化，我们建立了分层p e t r i 网，用一个子网替换p e t r i 网的一个位置节点( 或 变迁) 是一种典型的p 缸网细化方法，子网能保持被该子网替换的元素的后置集和前 置集的连接。一个细化过程，由两部分组成：一个是对应关系，该对应关系是建立p “ 网中的元素和其细化子网元素：另一个是连接关系，该连接关系是建立一个元素的后置 集和前置集与其细化子网。 定义2 8 一个p 嘶网细化系统，定义为一个五元组，h = ( 眠，m ，p ，矽，少) 。其中： 是一个带有初始标识的变迁网，眠= ( 瓯，瓦；昂，聊。) ；m 是带有标识的子网集合， m = ( m i 一，m k ) ：p 是细化函数，将瓯中的元素和瓦中的元素与m 中的子网对应起来， p ：& u 瓦一 1 ，后 ；每个位置s 岛a 被细化为子网m 刖，如果f 如，l ( p ) ；和缈是 接口函数，定义了每个位置的后置前置集与其细化之间的连接关系。对每个s & ，如 果j 如所( p ) ，则矽( s ) ：写一2 且有沙( j ) ：瓦一2 ；相同的，对每个f r ，如果 f 如聊( p ) ，则矽( f ) ：品专2 钾，且有沙( f ) ：瓯专2 钾。 2 4 基于p e t ri 网的车间调度建模的基本思想 车间调度系统是并发的系统，系统的活动存在合作关系、竞争关系、并发等多种关 系。因此车间调度系统的建模工具应具备有以下能力：能够反映车间调度系统的复杂的 并发特征；具备系统分级建模的能力；具备定量的和定性的进行系统分析的能力：具备 动态决策系统的能力；具备适应系统变化的柔性的特性。由p e t r i 网的理论知识可知， p e t r i 网理论具备上述特征，所以p e t r i 网适合用于车间调度系统的分析和建模。 一般的，有两种方法对系统进行综合分析，即自上而下的方法和自下而上的方法。 而对于复杂的系统，通常都要混合相结合，使用这两种方法。 1 、先自上而下 首先是要建立作为系统最顶层的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 、再自下而上 通过自上而下的分析后，每一个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 网模型子系 统之间的共享资源库所，并决定其初始令牌数。 尽管上面这两种方法在理论上是可行的，但在实际的操作中，却并不容易。实际的 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 网模型合并的方法在理论上虽然也可行，但是在处理 一个的复杂系统时，由于库所的结点数目众多，工作量有可能太大，而使这种手工合并 方法变得并不可行，需要开发相应的工具。最关键的一点就是这样建立的p e t r i 网模型 可维护性差，对子系统的p e t r i 网的改变将会导致整个p e t r i 网系统的重建。 9 2 5 小结 车间调度系统是一个典型的离散事件的动态系统，离散事件研究的基本问题是系统 的建模问题。本章研究把对象模块化，使用p e t r i 网建模，建模层次清晰，减小了建模 的复杂性。 1 0 第三章生产车间调度 随着科学技术的飞速发展，生产的规模是越来越大，复杂性也是越来越高，企业对 生产过程也提出了更高的要求。在激烈的市场竞争中，为了确保生产高效、稳定的运行， 来获得最大的经济效益，原来局部、常规、简单的控制已不能满足现代企业生产的要求 了，企业所面临的问题是：如何根据市场上产品需求的变化进行决策经营：如何在企业 生产计划改变的情况下对企业的生产过程加以控制，以便最大限度地发挥企业生产的柔 性。为了解决上述的问题，1 9 7 3 年，博士h a r r i n g t o n 提出了计算机集成制造的概念， 它借助计算机硬件和软件，综合运用现代制造技术、信息技术、管理等技术将企业生产 过程中的要素与信息流有机地集成，并且优化运行，以实现产品的低耗、高质，从而使 企业赢得市场竞争。在自动化程度较高的企业生产系统中，要使企业生产高效、合理的 运行，调度问题就会变得非常的复杂，需要建立有效的调度控制策略，因此，研究调度 问题具有重要的现实意义。 3 1 调度概述 调度是一个过程，存在于人们的生活、科研和生产等各种生产和生活活动中。比如 在一个生产汽车工件的车间里，有若干个客户，下了若干张订单，一共需要生产十八种 工件。车间中，一共有加工这些工件的设备六台。问题是：如何安排工件的生产过程， 满足不同的用户、不同的产品，完成生产任务，还要应尽量的满足机器的利用率高、占 用的流动资金尽量少等一些指标要求。 调度问题，来源于各种不同的生产领域，计算机设计领域、电力传输领域、生产计 划领域、军队作战领域、后勤及通信领域、交通运输等领域中都存在调度的问题。调度 的一般性的定义是，为了在一段时间内，完成一组特定的或规定的工作，而相应地分配 一套资源。典型的调度问题有工程调度( p r o j e c ts c h e d u l i n g ) 、生产调度( p r o d u c t i o n s c h e d u l i n g ) 、铁路时刻表( r a il w a yt i m e t a b l i n g ) 和电力调度( e l e c t r i cp o w e r s c h e d u l i n g ) 等。所有的调度问题的共同特性是，它们都没有一个有效的算法，能够在 采用多项式的形式下，求出它的最优